LinkedList

LinkedList也和ArrayList一样实现了List接口，但是它执行插入和删除操作时比ArrayList更加高效，因为它是基于链表的。基于链表也决定了它在随机访问方面要比ArrayList逊色一点。 除此之外，LinkedList还提供了一些可以使其作为栈、队列、双端队列的方法。这些方法中有些彼此之间只是名称的区别，以使得这些名字在特定的上下文中显得更加的合适。 先看LinkedList类的定义。 1 public class LinkedList

2 extends AbstractSequentialList

3 implements List, Deque, Cloneable, java.io.Serializable

LinkedList继承自AbstractSequenceList、实现了List及Deque接口。其实AbstractSequenceList已经实现了List接口，这里标注出List只是更加清晰而已。AbstractSequenceList提供了List接口骨干性的实现以减少实现List接口的复杂度。Deque接口定义了双端队列的操作。 LinkedList中之定义了两个属性：

1 private transient Entry header = new Entry(null, null, null); 2 private transient int size = 0;

size肯定就是LinkedList对象里面存储的元素个数了。LinkedList既然是基于链表实现的，那么这个header肯定就是链表的头结点了，Entry就是节点对象了。一下是Entry类的代码。

1 private static class Entry { 2 E element; 3 Entry next; 4 Entry previous; 5

6 Entry(E element, Entry next, Entry previous) { 7 this.element = element; 8 this.next = next;

9 this.previous = previous; 10 } 11 }

只定义了存储的元素、前一个元素、后一个元素，这就是双向链表的节点的定义，每个节点只知道自己的前一个节点和后一个节点。 来看LinkedList的构造方法。

1 public LinkedList() {

2 header.next = header.previous = header; 3 }

4 public LinkedList(Collection c) { 5 this(); 6 addAll(c); 7 }

LinkedList提供了两个构造方法。第一个构造方法不接受参数，只是将header节点的前一节点和后一节点都设置为自身（注意，这个是一个双向循环链表，如果不是循环链表，空链表的情况应该是header节点的前一节点和后一节点均为null），这样整个链表其实就只有

header一个节点，用于表示一个空的链表。第二个构造方法接收一个Collection参数c，调用第一个构造方法构造一个空的链表，之后通过addAll将c中的元素全部添加到链表中。来看addAll的内容。

1 public booleanaddAll(Collection c) { 2 return addAll(size, c); 3 }

4 // index参数指定collection中插入的第一个元素的位置 5 public booleanaddAll(int index, Collection c) {

6 // 插入位置超过了链表的长度或小于0，报IndexOutOfBoundsException异常 7 if (index < 0 || index > size)

8 throw new IndexOutOfBoundsException(\

9 \10 Object[] a = c.toArray(); 11 intnumNew = a.length;

12 // 若需要插入的节点个数为0则返回false，表示没有插入元素 13 if (numNew==0) 14 return false; 15 modCount++;

16 // 保存index处的节点。插入位置如果是size，则在头结点前面插入，否则获取index处的节点

17 Entry successor = (index==size ? header : entry(index)); 18 // 获取前一个节点，插入时需要修改这个节点的next引用 19 Entry predecessor = successor.previous;

20 // 按顺序将a数组中的第一个元素插入到index处，将之后的元素插在这个元素后面 21 for (int i=0; i

22 // 结合Entry的构造方法，这条语句是插入操作，相当于C语言中链表中插入节点并修改指针

23 Entry e = new Entry((E)a[i], successor, predecessor);

24 // 插入节点后将前一节点的next指向当前节点，相当于修改前一节点的next指针

25 predecessor.next = e;

26 // 相当于C语言中成功插入元素后将指针向后移动一个位置以实现循环的功能

27 predecessor = e; 28 }

29 // 插入元素前index处的元素链接到插入的Collection的最后一个节点 30 successor.previous = predecessor; 31 // 修改size

32 size += numNew; 33 return true; 34 }

构造方法中的调用了addAll(Collection c)方法，而在addAll(Collection

extends E> c)方法中仅仅是将size当做index参数调用了addAll(intindex,Collection c)方法。

1 private Entryentry(int index) {

2 if (index < 0 || index >= size)

3 throw new IndexOutOfBoundsException(\ 4 \ 5 Entry e = header;

6 // 根据这个判断决定从哪个方向遍历这个链表 7 if (index < (size >> 1)) {

8 for (int i = 0; i <= index; i++) 9 e = e.next; 10 } else {

11 // 可以通过header节点向前遍历，说明这个一个循环双向链表，header的previous指向链表的最后一个节点，这也验证了构造方法中对于header节点的前后节点均指向自己的解释

12 for (int i = size; i > index; i--) 13 e = e.previous; 14 }

15 return e; 16 }

结合上面代码中的注释及双向循环链表的知识，应该很容易理解LinkedList构造方法所涉及的内容。下面开始分析LinkedList的其他方法。 add(E e)

1 public booleanadd(E e) { 2 addBefore(e, header); 3 return true; 4 }

从上面的代码可以看出，add(E e)方法只是调用了addBefore(E e,Entry entry)方法，并且返回true。

addBefore(E e,Entry entry)

1 private EntryaddBefore(E e, Entry entry) {

2 EntrynewEntry = new Entry(e, entry, entry.previous); 3 newEntry.previous.next = newEntry; 4 newEntry.next.previous = newEntry; 5 size++;

6 modCount++; 7 return newEntry; 8 }

addBefore(E e,Entry entry)方法是个私有方法，所以无法在外部程序中调用（当然，这是一般情况，你可以通过反射上面的还是能调用到的）。

addBefore(E e,Entry entry)先通过Entry的构造方法创建e的节点newEntry（包含了将其下一个节点设置为entry，上一个节点设置为entry.previous的操作，相当于修改newEntry的“指针”），之后修改插入位置后newEntry的前一节点的next引用和后一节点的previous引用，使链表节点间的引用关系保持正确。之后修改和size大小和记录modCount，然后返回新插入的节点。

总结，addBefore(E e,Entry entry)实现在entry之前插入由e构造的新节点。而add(E e)实现在header节点之前插入由e构造的新节点。 add(intindex,E e)

1 public void add(int index, E element) {

2 addBefore(element, (index==size ? header : entry(index))); 3 }

也是调用了addBefore(E e,Entry entry)方法，只是entry节点由index的值决定。 构造方法，addAll(Collection c)，add(E e)，addBefor(E e,Entry entry)方法可以构造链表并在指定位置插入节点，为了便于理解，下面给出插入节点的示意图。

addFirst(E e)

1 public void addFirst(E e) {

2 addBefore(e, header.next); 3 }

addLast(E e)

1 public void addLast(E e) { 2 addBefore(e, header); 3 }