# Sorted Linked List

I spent some time today coming up with a simple algorithm for traversing of; and inserting in a sorted linked list. I'm posting this here in case I ever need it again.

```
public class Container {
private static class Node {
int key;
WeakReference wr;
Node next;
Node() {
key = 0;
next = this;
}
Node(int key, Object o, Node next) {
this.key = key;
this.wr = new WeakReference(o);
this.next = next;
}
}
public void add(int key, Object o) {
Node node = head;
while (node.next.key < key && node.next != head) {
node = node.next;
}
// Don't overwrite existing values, to avoid an object allocation
if (node.next.key != key) {
node.next = new Node(key, o, node.next);
}
}
public Object find(int key) {
Node node = head;
while (node.next.key < key && node.next != head) {
node = node.next;
}
Object o = null;
if (node.next != head && node.next.key == key
&& (o = node.next.wr.get()) == null) {
// Object GCd, remove the node
node.next = node.next.next;
}
return o;
}
private Node head = new Node();
}
```

Note that I'm using a sentinel Node at the head. This avoids a lot of null checks and makes the algorithm much simpler. When adding a Node, it's always added *after* something and *before* something, even if those two happen to be the same sentinel. By the same logic, when removing a Node, there is always a *previous* and a *next* node, so we simply link them. In all these cases we don't need to think about nulls.