上一章節我們實作出了一個LinkedList的類別，可以做到基本的操作。不過有一個地方其實有點不太完美，那就是addLast方法的效能不太好，當list的元素很多時，就會跑很久才找到最後一個IntNode，然後assign new IntNode到next變數。

很直覺的想法就是，那我們就多加一個last變數來記錄最後一個node在哪裡囉：

而且這個last變數可以在每次執行addLast方法時順便紀錄，貌似一切都很美好～

但其實這樣會有一個問題，那就是當我們要實作remove時，假若我們要remove掉最後一個元素last，我們不能直接把last變數清掉，因為重點在於Linked的前一個關聯要移掉！變成我們還是得從first開始一路找到last的前一個，然後把他的next清掉才是真正的remove。

該怎麼優化呢？那就是在IntNode多加一個prev的屬性！這也是本章節叫做DLList的由來，D代表”doubly” linked list：

但這樣實作的話會有個問題，就是當空list時last會指到sentinel node；當list有元素存在時又會指到真正的IntNode：

所以這時候就可以現學現賣了，我們的last就一樣使用一個sentinel node：

其實上面這個範例在實作上就不會有任何問題了，但是還有一個更精妙的做法，那就是讓sentinel node的prev指向last node！

真是優雅。

以下是我實作的扣的：

public class DLListWithLastSentinel {

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

	private IntNode sentinelFirst;
	private IntNode sentinelLast;
	
	public DLListWithLastSentinel(){
		IntNode first = new IntNode(0, null, null);
		sentinelFirst = first;
		IntNode last = new IntNode(99, null, sentinelFirst);
		sentinelLast = last;
		sentinelFirst.next = sentinelLast;
	}

	public DLListWithLastSentinel(int num){
		IntNode node = new IntNode(num, sentinelLast, sentinelFirst);
		sentinelFirst.next = node;
		sentinelLast.prev = node;
	}

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

	public void addLast(int num){
		IntNode oldLast = sentinelLast.prev;
		sentinelLast.prev = new IntNode(num, sentinelLast, oldLast);
		oldLast.next = sentinelLast.prev;
	}

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

	public int size(){
		// minus 1 to remove the count of sentinelLast
		return size(sentinelFirst.next) - 1;
    }
	
	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(sentinelFirst.next, index);
	}
}

Slides are from Josh Hug CS61B

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