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号节点之后)。
























版权声明:本文为JAVASCHOOL原创文章,未经本站允许不得转载。