Deletion From A Cyclical List

December 8, 2017

A cyclical list has no beginning and no end; Chez Scheme writes it like this:

#0=(1 2 3 . #0#)

Your task is to write a program that removes an item from a cyclical list; if the item is not present in the cyclical list, it should remain unchanged. When you are finished, you are welcome to read or run a suggested solution, or to post your own solution or discuss the exercise in the comments below.

Advertisements

Pages: 1 2

2 Responses to “Deletion From A Cyclical List”

  1. Daniel said

    Here’s a solution in Java.

    public class CyclicalList<T> {
      public static class Node<U> {
        U value;
        Node<U> next;
      }
      
      Node<T> last = null;
      
      public void insert(T value) {
        Node<T> node = new Node<>();
        node.value = value;
        if (last == null) {
          last = node;
          node.next = node;
        } else {
            node.next = last.next;
            last.next = node;
        }
      }
      
      /**
       * Removes the *first* occurrence.
       */
      public void remove(T value) {
        if (last == null) return;
        Node<T> node = last;
        Node<T> next = last.next;
        do {
          if (next.value.equals(value)) {
            if (node == next) {
              last = null;
              break;
            }
            node.next = next.next;
            if (next == last) {
              last = node;
            }
          }
          node = node.next;
          next = node.next; 
        } while (next != last.next);
      }
      
      public String toString() {
        StringBuffer sb = new StringBuffer();
        if (last == null) {
          sb.append("()");
        } else {
          sb.append("#0=(");
          Node<T> node = last.next;
          while (true) {
            if (node != last.next) {
              sb.append(" ");
            }
            sb.append(node.value);
            node = node.next;
            if (node == last.next) {
              sb.append(" . #0#)");
              break;
            }
          }
        }
        return sb.toString();
      }
      
      public static void main(String[] args) {
        CyclicalList<Integer> list = new CyclicalList<>();
        for (int i = 3; i > 0; --i) {
          list.insert(i);
        }
        System.out.format("List:\n  %s\n\n", list);
        // 1 removed twice, to show effect of removing an item not present
        for (int i : new Integer[]{1,3,1,2}) {
          list.remove(i);
          System.out.format("Remove %d:\n  %s\n\n", i, list);
        }
      }
    }
    

    Output:

    List:
      #0=(1 2 3 . #0#)
    
    Remove 1:
      #0=(2 3 . #0#)
    
    Remove 3:
      #0=(2 . #0#)
    
    Remove 1:
      #0=(2 . #0#)
    
    Remove 2:
      ()
    
  2. Daniel said

    I had a bug in my code. I was missing a “break” statement in the remove method. Without this, multiple elements could be removed on a call to remove, whereas my intent was to remove a single element (as indicated in my comment).

    Here’s the updated code.

    public class CyclicalList<T> {
      public static class Node<U> {
        U value;
        Node<U> next;
      }
    
      Node<T> last = null;
    
      public void insert(T value) {
        Node<T> node = new Node<>();
        node.value = value;
        if (last == null) {
          last = node;
          node.next = node;
        } else {
          node.next = last.next;
          last.next = node;
        }
      }
    
      /**
       * Removes the *first* occurrence.
       */
      public void remove(T value) {
        if (last == null) return;
        Node<T> node = last;
        Node<T> next = last.next;
        do {
          if (next.value.equals(value)) {
            if (node == next) {
              last = null;
            } else {
              node.next = next.next;
              if (next == last) {
                last = node;
              }	
            }
            break;
          }
          node = node.next;
          next = node.next; 
        } while (next != last.next);
      }
    
      public String toString() {
        StringBuffer sb = new StringBuffer();
        if (last == null) {
          sb.append("()");
        } else {
          sb.append("#0=(");
          Node<T> node = last.next;
          while (true) {
            if (node != last.next) {
              sb.append(" ");
            }
            sb.append(node.value);
            node = node.next;
            if (node == last.next) {
              sb.append(" . #0#)");
              break;
            }
          }
        }
        return sb.toString();
      }
    
      public static void main(String[] args) {
        CyclicalList<Integer> list = new CyclicalList<Integer>() {{
          insert(0);
          insert(0);
          insert(3);
          insert(2);
          insert(3);
          insert(3);
          insert(2);
          insert(1);
        }};
        System.out.format("List:\n  %s\n\n", list);
        for (int i : new Integer[]{1,3,1,2,0,0}) {
          list.remove(i);
          System.out.format("Remove %d:\n  %s\n\n", i, list);
        }
      }
    }
    
    List:
      #0=(1 2 3 3 2 3 0 0 . #0#)
    
    Remove 1:
      #0=(2 3 3 2 3 0 0 . #0#)
    
    Remove 3:
      #0=(2 3 2 3 0 0 . #0#)
    
    Remove 1:
      #0=(2 3 2 3 0 0 . #0#)
    
    Remove 2:
      #0=(3 2 3 0 0 . #0#)
    
    Remove 0:
      #0=(3 2 3 0 . #0#)
    
    Remove 0:
      #0=(3 2 3 . #0#)
    

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: