List Implementation

Today, we implement a sorted linked-list and try to feel how to write beautiful code.

Question

Implement a sorted linked-list with max possible value known and following declaration:

Class SortedList {
    public SortedList(int maxValue) {
        //...
    }

    public void insert(int i) {
    }
}

Simple Version

What comes to my mind, at the beginning, is some code like the following:

public SortedList0(int max) {
}

public void insert(int i) {
    if (head == null) {
        head = new ListNode(i, null);
    } else {
        ListNode prev = null, next = head;
        while (next != null && next.getVal() < i) {
            prev = next;
            next = next.getNext();
        }
        if (prev == null) {
            head = new ListNode(i, head);
        } else {
            prev.setNext(new ListNode(i, next));
        }
    }
}

This version works, but we can see there are some special cases need to handle which make our code not so clean. And the following version is from Programming Pearls.

With Sentinel

First, we define a sentinel element which will save the comparison between null when iterating the list.

public SortedList(int max) {
    sentinel = head = new Node(max, null);
    head.next = sentinel;
}

public void insert(int t) {
    Node succ = head, prev = null;
    while (succ.val < t) {
        prev = succ;
        succ = succ.next;
    }
    final Node node = new Node(t, succ);
    if (prev == null) {
        head = node;
    } else {
        prev.next = node;
    }
}

This for loop is simpler, but still with some special case. What author give us is a recursive version like the following:

public void rInsert(int t) {
    head = insertAndReturnHead(head, t);
}

private Node insertAndReturnHead(Node h, int t) {
    if (h < h.val) {
        return new Node(t, h);
    }
    h.next = insertAndReturnHead(h.next, t);
    return h;
}

Although author blame recursive version causing some performance penalty after some micro-benchmark, this code is so simple and clean.

With Header

When dealing with linked-list, a fake header can always make code cleaner. So let’s try with it.

public SortedList2(int max) {
    sentinel = new ListNode(max, null);
    head = new ListNode(max, sentinel);
    size = 0;
}

public void insert(int t) {
    ListNode prev = head, next = prev.getNext();
    while (next.getVal() < t) {
        prev = next;
        next = next.getNext();
    }
    prev.setNext(new ListNode(t, next));
    size++;
}

Here, we can see no special cases any more, we just to find a previous element and next element, insert and it’s all done. So simple.

Ref

• source code

Written with StackEdit.