## 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.

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#)
```