Sentinel Node

哨兵节点相当于一个哑单元，或者一个傀儡，作用是防止首节点为空时（first == null），出现无法指向下个节点情况。哨兵节点指向的下个单元为首节点。

public class SLList {
    public class IntNode {
        public int item;
        public IntNode next;
        public IntNode(int i, IntNode n) {
            item = i;
            next = n;
        }
    }

    private IntNode first; 
    private int size;

    public SLList() {
        first = null;
        size = 0;
    }

    public SLList(int x) {
        first = new IntNode(x, null);
        size = 1;
    }

    /** Adds an item to the front of the list. */
    public void addFirst(int x) {
        first = new IntNode(x, first);
        size += 1;
    }    

    /** Retrieves the front item from the list. */
    public int getFirst() {
        return first.item;
    }

    /** Returns the number of items in the list. */
    public int size() {
        return size;
    }

    /** Adds an item to the end of the list. */
    /* 这里已经通过讨论首节点为空的情况修正，但采用哨兵节点会更简洁*/
    public void addLast(int x) {
       size += 1;
        if(first == null){
            first = new IntNode(x , first);
            return 0;
        IntNode p = first;
        while(p != null){
            p = p.next;         
        }
        p.next = IntNode(x , null);
    }

    /** Crashes when you call addLast on an empty SLList. Fix it. */
    public static void main(String[] args) {
        SLList x = new SLList();
        x.addLast(5);
    }
}

添加节点的方法：

    public void addLast(int x) {
       size += 1;
        if(first == null){
            first = new IntNode(x , first);
            return 0;
        IntNode p = first;
        while(p != null){
            p = p.next;         
        }
        p.next = IntNode(x , null);
    }

利用哨兵节点进行优化：

    public void addLast(int x) {
    	size += 1;
        IntNode p = sentinel;
        while(p != null){
            p = p.next;         
        }
        p.next = IntNode(x , null);
    }

本文为CS61B学习笔记，参考链接：https://joshhug.gitbooks.io/hug61b/content/chap2/chap22.html