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.

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 )

Google+ photo

You are commenting using your Google+ 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 )

Connecting to %s

%d bloggers like this: