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.
Programming Praxis 
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:
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); } } }