图解双链表

以java.util.LinkedList源码结合本人用XP自带的简陋的画图程序分析链表成链的过程如下：

1、一个空的双链表其实是个环形的链，如下图：

public LinkedList() {
        header.next = header.previous = header;
    }

2、添加第一个元素的过程如下：

public boolean add(E o) {
	addBefore(o, header);
        return true;
    }
private Entry<E> addBefore(E o, Entry<E> e) {
	Entry<E> newEntry = new Entry<E>(o, e, e.previous);//①
	newEntry.previous.next = newEntry;   //③
	newEntry.next.previous = newEntry;   //②
	size++;
	modCount++;
	return newEntry;
    }

注意看①处，意思是说新增节点的后驱是header，前驱是header的前驱(header的前驱始终会指向链表的最后一个元素)

3、添加第二个元素如下和添加第一个类似：


--------------------------------------------------
2011-11-02 下午
补充：

private Entry<E> addBefore(E e, Entry<E> entry) {
	Entry<E> newEntry = new Entry<E>(e, entry, entry.previous);//A
	newEntry.previous.next = newEntry;
	newEntry.next.previous = newEntry;
	size++;
	modCount++;
	return newEntry;
    }

这段代码是添加元素到链表的尾部，创建新节点的代码A，如果站在空链表的角度去理解其实并不好理解，如果你站在已经添加了元素的角度来理解就显得容易一些了，如下图：


解释：原来是head和1节点组合成一个环形的链表，现在我要添加元素2，那么addBefore是怎么做的呢？它首先得把绿色的1->head的线分解成2条绿色的带箭头的虚线，然后把红色的head->1的线分解成那2条红色的虚线。
所以newEntry.next = head;
newEntry.pre = head.pre;
连起来写就是A处的代码了。下面2句代码就迎刃而解了。