java LinkedList源码解读

1. 前言

众所周知，

LinkedList

是由链表实现的，其实它是由双向链表实现的。我们看一下源码中add，delete等是如何实现的。

2. LinkedList的属性

LinkedList

里只有一个int类型的长度size，和一个

Link

类型的voidLink。

Link

是内部类，其实相当于节点Node类。具体实现如下：

transient int size = 0; //长度

transient Link<E> voidLink; //结点voidLink

private static final class Link<ET> {
    ET data; //数据域

    //指向前一个结点的previous指针和指向后一个结点的next指针
    Link<ET> previous, next; 

    Link(ET o, Link<ET> p, Link<ET> n) {
        data = o;
        previous = p;
        next = n;
    }
}
           

3. 构造函数

3.1 空构造函数

//默认前后指针都指向自己
public LinkedList() {
    voidLink = new Link<E>(null, null, null);
    voidLink.previous = voidLink;
    voidLink.next = voidLink;
}   
           

3.2 LinkedList(Collection collection)

public LinkedList(Collection<? extends E> collection) {
    this();
    //addAll的实现看下文
    addAll(collection);
}
           

4. add方法

4.1 add(int location, E object)

双向链表插入一个数的思想如下：

1. 定义一个临时指针link向后遍历，直到到达指定位置location（这里有个优化：如果location < size/2，则从前向后遍历，否则，从后向前遍历）
2. new一个Link，数据域为要插入的object，previous指向link的previous，next指向link的next

3. size ++。

   下图为双向链表中间插入的过程，头插和尾插这里不多说。

   

   代码实现如下：

   @Override
   public void add(int location, E object) {
       if (location >= 0 && location <= size) {
           Link<E> link = voidLink;
           if (location < (size / 2)) {
               for (int i = 0; i <= location; i++) {
                   link = link.next;
               }
           } else {
               for (int i = size; i > location; i--) {
                   link = link.previous;
               }
           }
           Link<E> previous = link.previous;
           Link<E> newLink = new Link<E>(object, previous, link);
           previous.next = newLink;
           link.previous = newLink;
           size++;
           modCount++;
       } else {
           throw new IndexOutOfBoundsException();
       }
   }