Java LinkedList.add() 增加方法以及原理

LinkedList add(E e)将指定元素添加到此列表的结尾。

源码分析

// 将元素(E)添加到LinkedList中
public boolean add(E e) {
    // 将节点(节点数据是e)添加到表头(header)之前。
    // 即，将节点添加到双向链表的末端。
    addBefore(e, header);
    return true;
}
public void add(int index, E element) {
    addBefore(element, (index == size ? header: entry(index)));
}
private Entry < E > addBefore(E e, Entry < E > entry) {
    Entry < E > newEntry = new Entry < E > (e, entry, entry.previous);
    newEntry.previous.next = newEntry;
    newEntry.next.previous = newEntry;
    size++;
    modCount++;
    return newEntry;
} 
public void addFirst(E e) {
 addBefore(e, header.next);
}
public void addLast(E e) {
 addBefore(e, header);
}
private Entry<E> addBefore(E e, Entry<E> entry) {
 //利用Entry构造函数构建一个新节点 newEntry，
 Entry<E> newEntry = new Entry<E>(e, entry, entry.previous);
 //修改newEntry的前后节点的引用，确保其链表的引用关系是正确的
 newEntry.previous.next = newEntry;
 newEntry.next.previous = newEntry;
 //容量+1
 size++;
 //修改次数+1
 modCount++;
 return newEntry;
}

addBefore(E e,Entry<E> entry)方法是个私有方法，所以无法在外部程序中调用（当然，这是一般情况，你可以通过反射上面的还是能调用到的）。
addBefore(E e,Entry<E> entry)先通过Entry的构造方法创建e的节点newEntry（包含了将其下一个节点设置为entry，上一个节点设置为entry.previous的操作，相当于修改newEntry的“指针”），之后修改插入位置后newEntry的前一节点的next引用和后一节点的previous引用，使链表节点间的引用关系保持正确。之后修改和size大小和记录modCount，然后返回新插入的节点。

添加原理

下面分解“添加第一个数据”的步骤：

第一步：初始化后LinkedList实例的情况：

LinkedList.add原理

第二步：初始化一个预添加的Entry实例（newEntry）。

Entry newEntry = newEntry(e, entry, entry.previous);

LinkedList.add原理

第三步：调整新加入节点和头结点（header）的前后指针。

newEntry.previous.next = newEntry;

newEntry.previous即header，newEntry.previous.next即header的next指向newEntry实例。在上图中应该是“4号线”指向newEntry。

newEntry.next.previous = newEntry;

newEntry.next即header，newEntry.next.previous即header的previous指向newEntry实例。在上图中应该是“3号线”指向newEntry。

调整后如下图所示：

图——加入第一个节点后LinkedList示意图

LinkedList.add原理

下面分解“添加第二个数据”的步骤：

第一步：新建节点。

图——添加第二个节点

LinkedList.add原理

第二步：调整新节点和头结点的前后指针信息。

图——调整前后指针信息

LinkedList.add原理

添加后续数据情况和上述一致，LinkedList实例是没有容量限制的。

总结，addBefore(E e,Entry<E> entry)实现在entry之前插入由e构造的新节点。而add(E e)实现在header节点之前插入由e构造的新节点。为了便于理解，下面给出插入节点的示意图。

LinkedList.add原理

看上面的示意图，结合addBefore(E e,Entry<E> entry)方法，很容易理解addFrist(E e)只需实现在header元素的下一个元素之前插入，即示意图中的一号之前。addLast(E e)只需在实现在header节点前（因为是循环链表，所以header的前一个节点就是链表的最后一个节点）插入节点（插入后在2号节点之后）。