Deletion From A Cyclical List
December 8, 2017
We begin with functions to create a cycle, which must have at least one item:
(define (last-pair xs)
(if (null? xs) (error 'last-pair "empty list")
(if (null? (cdr xs)) xs (last-pair (cdr xs)))))
(define (cycle . xs) (set-cdr! (last-pair xs) xs) xs)
Our solution is in two parts. First, rotate the list so the item to be deleted is at the head of the list; if the item is not found, return the list unchanged. Second, run all the way around the list to the item before the item to be deleted, and snip the item out of the list. That sounds wasteful, because it requires an extra loop around the list once the item to be deleted has been found. But it eliminates a special case where the item to be deleted is the first item in the list. Here’s the code:
(define (remove-cycle eql? x xs)
(let loop ((ys (cdr xs)))
(if (eql? x (car ys)) (remove-head ys)
(if (eq? xs ys) xs (loop (cdr ys))))))
(define (remove-head xs)
(let loop ((ys (cdr xs)))
(cond ((eq? xs (cdr ys))
(set-cdr! ys (cddr ys)) ys)
(else (loop (cdr ys))))))
Here we see the function in action:
> (set! xs (cycle 2 3 5 7 11 13 17 19 23 29)) > (set! xs (remove-cycle = 2 xs)) > (set! xs (remove-cycle = 11 xs)) > (set! xs (remove-cycle = 19 xs)) > (set! xs (remove-cycle = 21 xs)) > (set! xs (remove-cycle = 23 xs)) > xs Warning in pretty-print: cycle detected; proceeding with (print-graph #t) #0=(17 29 3 5 7 13 . #0#)
That looks right. But the function fails to remove the last item from a singleton cycle:
> (set! xs (cycle 3)) > (set! xs (remove-cycle = 3 xs)) > xs Warning in pretty-print: cycle detected; proceeding with (print-graph #t) #0=(3 . #0#)
I guess that makes sense, since we defined a cycle as having at least one item. But I still think it’s wrong.
You can run the program at https://ideone.com/Y1tnVv.
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); } } }