/ programming

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

Read more posts by this author.