LlinkList学习

添加元素

首先看下LinkedList添加一个元素是怎么做的，假如我有一段代码：

public static void main(String[] args)

{

     List<String> list = new LinkedList<String>();

     list.add("111");

     list.add("222");

}

逐行分析main函数中的三行代码是如何执行的，首先是第3行，看一下LinkedList的源码：

public class LinkedList<E>

    extends AbstractSequentialList<E>

    implements List<E>, Deque<E>, Cloneable, java.io.Serializable

{

    private transient Entry<E> header = new Entry<E>(null, null, null);

    private transient int size = 0;

 

    /**

     * Constructs an empty list.

     */

    public LinkedList() {

        header.next = header.previous = header;

    }

    ...

}

 这里重要的是 header.next = header.previous = header;这一行，

private static class Entry<E> {
 2    E element;
 3     Entry<E> next;
 4     Entry<E> previous;
 5 
 6     Entry(E element, Entry<E> next, Entry<E> previous) {
 7         this.element = element;
 8         this.next = next;
 9         this.previous = previous;
10    }
11 

所以previours和next只是引用地址

添加元素的过程，链表的组成和变动

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

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

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

第三步：调整新加入节点和头结点（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实例是没有容量限制的。

LlinkList学习

原文：http://www.cnblogs.com/hanguocai/p/7746172.html