上一章節我們的IntList實作了get和size方法，這邊就來談談add方法。

我們該如何在IntList加元素呢？

IntList L = new IntList(1, null);

// add element to the front [2, 1]
L = new IntList(2, L);

// add element to the last [2, 1, 3]
L.next.next = new IntList(3, null);
...

以上的code就是add最直觀的做法，但會發現這樣真的很難用！該怎麼辦呢？這時候就要發揮Java物件導向的特性，把這些很醜的實作包裝起來，甚至把我們的IntList包裝成另一個類別來重用：

public class SLList{

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

	private IntNode first;
	
	public SLList(){
		first = null;
	}

	public SLList(int num){
		first = new IntNode(num, null);
	}

	public void addFirst(int num){
		first = new IntNode(num, first);
	}

	public void addLast(int num){
		IntNode p = first;
		
		// avoid empty list
		if(p == null){
			p = new IntNode(num, null);
		}

		while(p.next != null){
			p = p.next;
		}
		p.next = new IntNode(num, null);
	}

	private int size(IntNode node){
	  if(node.next == null){
			return 1;
		}
		return 1 + size(node.next);
  }

	public int size(){
		return size(first);
  }
	
	private int get(IntNode node, int index) {
		if(index == 0) {
			return node.item;
		}
		return get(node.next, index - 1);
	}
	
	public int get(int index) {
		return get(first, index);
	}
}

不過這樣還不夠好，我們可以發現在addLast(int num)方法中有一個if statement來避免empty list的情況，因為後面會呼叫到p.next，假設我們的first IntNode為null，即假若我們的SLList為空list，就會發生NullPointerException。有沒有什麼辦法讓我們既可以避免掉為了例外而撰寫if statement，又能達到需要的功能呢？

這時老師使用了一個叫sentinel的node：

public class SLList{

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

	private IntNode sentinel;
	
	public SLList(){
		sentinel = new IntNode(69, null);
	}

	public SLList(int num){
		sentinel.next = new IntNode(num, null);
	}

	public void addFirst(int num){
		sentinel.next = new IntNode(num, sentinel.next);
	}

	public void addLast(int num){
		IntNode p = sentinel;
		while(p.next != null){
			p = p.next;
		}
		p.next = new IntNode(num, null);
	}

	private int size(IntNode node){
	  if(node.next == null){
			return 1;
		}
		return 1 + size(node.next);
    }

	public int size(){
		return size(sentinel.next);
    }
	
	private int get(IntNode node, int index) {
		if(index == 0) {
			return node.item;
		}
		return get(node.next, index - 1);
	}
	
	public int get(int index) {
		return get(sentinel.next, index);
	}
}

我們可以看到，在constructor中我們就會先指派一個IntNode給sentinel，sentinel中的item數值是多少無所謂，因為重要的是連結在它next中的IntNode才會是我們真正的list，所以我們只要把原本code中的first都改為sentinel.next，就搞定了~

如此一來addLast中不但不會遇到空list addList時會拋NullPointerException，判斷p == null的條件也可以去掉！讓code變得更優雅。

This work is licensed under a Creative Commons Attribution-NonCommercial-ShareAlike 4.0 International License