源码分析：LinkedList和Java中的指针操作

LinkedList类似C语言的双向链表，但是java中没有指针如何实现呢，看完LinkedList
你将对java中的引用类型有更深入的理解。LindedList的声明如下：

public class LinkedList extends AbstractSequentialList implements List, Cloneable, java.io.Serializable
有关AbstractSequentialList：http://blog.csdn.net/treeroot/archive/2004/09/18/108696.aspx
有关List： http://blog.csdn.net/treeroot/archive/2004/09/14/104638.aspx
有关Cloneable：http://blog.csdn.net/treeroot/archive/2004/09/07/96936.aspx

下面分析一下这个链表的实现，这里只重点分析某些方法。

private transient Entry header = new Entry(null, null, null);
private transient int size = 0;
public LinkedList() {
　　header.next = header.previous = header;
}
header相当于C中的头指针，而且这个头指针不是链表的元素，有关Entry将在下面介绍。

public LinkedList(Collection c) {
　　this();
　　addAll(c);
}

public Object getFirst() {
　if (size==0)
　　　throw new NoSuchElementException();
　 return header.next.element;
}
头指针的下一个元素就是第一个元素

public Object getLast() {
　　if (size==0)
　　　　throw new NoSuchElementException();
　　return header.previous.element;
}
头指针的前一个当然就是最后一个了

public Object removeFirst() {
　　Object first = header.next.element;
　　remove(header.next);
　　return first;
}

public Object removeLast() {
　　Object last = header.previous.element;
　　remove(header.previous);
　　return last;
}

public void addFirst(Object o) {
　　addBefore(o, header.next);
}

public void addLast(Object o) {
　　addBefore(o, header);
}
这个方法在链表末尾插入新的元素，功能和add方法一样，这个方法完全是为了对称性(因为有addFirst)

public boolean contains(Object o) {
　　return indexOf(o) != -1;
}

public int size() {
　　return size;
}

public boolean add(Object o) {
　　addBefore(o, header);
　　return true;
}

public boolean remove(Object o) {
　　if (o==null) {
　　　　for (Entry e = header.next; e != header; e = e.next) {
　　　　　　if (e.element==null) {
　　　　　　　　remove(e);
　　　　　　　　return true;
　　　　　　}
　　　　}
　　} else {
　　　　　for (Entry e = header.next; e != header; e = e.next) {
　　　　　　if (o.equals(e.element)) {
　　　　　　　　remove(e);
　　　　　　　　return true;
　　　　　　　}
　　　　　}
　　}
　　return false;
}
用过C的人应该感到很熟悉了，这里就是通过指针后移来查找相同的元素，注意这里最多只删除一个
元素，符合List接口中的说明。

public boolean addAll(Collection c) {
　　return addAll(size, c);
}

public boolean addAll(int index, Collection c) {
　　int numNew = c.size();
　　if (numNew==0)
　　　　return false;
　　modCount++;

　　Entry successor = (index==size ? header : entry(index));
　　Entry predecessor = successor.previous;
　　Iterator it = c.iterator();
　　for (int i=0; i

本文地址：http://com.8s8s.com/it/it15370.htm