Java集合类--LinkedList

http://www.cnblogs.com/huangfox/archive/2010/10/11/1847863.html

一、 LinkedList
 

3.1      创建：LinkedList()

LinkedList底层的数据结构是一个双向链表。既然是双向链表，那么必定存在一种数据结构——我们可以称之为节点，节点实例保存业务数据，前一个节点的位置信息和后一个节点位置信息，如下图所示：

图——双线链表及节点示意图

 

首先来了解节点类：

private static class Entry<E>{

    Eelement;

    Entry<E> next;

    Entry<E> previous;

 

    Entry(Eelement, Entry<E>next, Entry<E>previous) {

        this.element = element;

        this.next = next;

        this.previous = previous;

    }

    }

节点类很简单，element存放业务数据，previous与next分别存放前后节点的信息（在数据结构中我们通常称之为前后节点的指针）。

声明LinkedList对象时，创建一个Entry对象，不过全部为空。

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

private transient int size = 0;

在执行构造函数的时候，将header实例的previous和next全部指向header实例。

public LinkedList(){

       header.next = header.previous = header;

    }

执行完构造函数后，header实例自身形成一个闭环，如下图所示：

图——初始化LinkedList

 

3.2      添加数据：add()

从源代码中我们可知——给LinkedList添加数据是从双向链表的头开始的，代码如下所示：

public boolean add(E e) {

    addBefore(e, header);

       return true;

    }

private Entry<E> addBefore(Ee, 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;

    }

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

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

图——初始化后

 

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

Entry<E> newEntry = newEntry<E>(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实例是没有容量限制的。

3.3      删除数据：remove()、remove(int)、remove(Object)

LinkedList的数据删除操作虽然有多种（这里认为只包括remove()、remove(int)、remove(Object) ），但是真正执行删除操作的代码如下所示：

private E remove(Entry<E> e) {

    if (e == header)

        throw new NoSuchElementException();

 

       E result = e.element;

    e.previous.next = e.next;

    e.next.previous = e.previous;

       e.next = e.previous = null;

       e.element = null;

    size--;

    modCount++;

       return result;

    }

Remove方法接收的参数是一个节点实例，即预被删除的节点。只不过remove()是删除的第一个节点（头结点后的第一个节点）——

public EremoveFirst() {

    return remove(header.next);

    }

Remove(int)是删除指定位置的节点——

private Entry<E> entry(int index) {

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

           throw new IndexOutOfBoundsException("Index: "+index+

                                               ", Size: "+size);

       Entry<E> e = header;

       if(index < (size >> 1)) {//判断是从头开始遍历还是从尾开始遍历 

            for (int i = 0; i<= index; i++)

                e = e.next;

        } else {

            for (int i = size;i > index; i--)

                e = e.previous;

        }

       return e;

    }

Remove(Object)是删除指定内容的节点——

public boolean remove(Object o) {

       if (o==null) {

           for (Entry<E> e = header.next; e != header; e = e.next) {

                if (e.element==null) {

                    remove(e);

                    return true;

                }

           }

       } else {

           for (Entry<E> e = header.next; e != header; e = e.next) {

                if (o.equals(e.element)) {

                    remove(e);

                    return true;

                }

           }

       }

       return false;

    }

在回到我们的remove(Entry e)方法：

由于删除了某一节点因此调整相应节点的前后指针信息，如下：

e.previous.next = e.next;//预删除节点的前一节点的后指针指向预删除节点的后一个节点。 

e.next.previous = e.previous;//预删除节点的后一节点的前指针指向预删除节点的前一个节点。 

清空预删除节点：

e.next = e.previous = null;

e.element = null;

交给gc完成资源回收，删除操作结束。

与ArrayList比较而言，LinkedList的删除动作不需要“移动”很多数据，从而效率更高。

3.4      获取数据：get(int)

Get(int)方法的实现在remove(int)中已经涉及过了。首先判断位置信息是否合法（大于等于0，小于当前LinkedList实例的Size），然后遍历到具体位置，获得节点的业务数据（element）并返回。

注意：为了提高效率，需要根据获取的位置判断是从头还是从尾开始遍历。

private Entry<E> entry(int index) {

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

           throw new IndexOutOfBoundsException("Index: "+index+

                                               ", Size: "+size);

       Entry<E> e = header;

       if(index < (size >> 1)) {//判断是从头开始遍历还是从尾开始遍历 

            for (int i = 0; i<= index; i++)

                e = e.next;

        } else {

            for (int i = size;i > index; i--)

                e = e.previous;

        }

       return e;

    }

注意细节：位运算与直接做除法的区别。

3.5      遍历数据：Iterator()

对ArrayList的iterator有所了解后，在此重点关注以下几点：

当调用iterator方法是，每次都创建一个ListItr实例，它拥有一个属性cursor，起到游标的作用。

Iterator实例的hasNext方法：

public boolean hasNext() {

     return cursor != size();

}

当游标跑到最后时返回false，说明遍历完成。

Iterator实例的next方法：

public E next() {

           checkForComodification();

        try {

       Enext = get(cursor);

       lastRet= cursor++;

       return next;

        } catch (IndexOutOfBoundsException e) {

       checkForComodification();

       throw newNoSuchElementException();

        }

    }

通过get方法返回当前游标位置的节点内容，并将游标后移一个位置。

LinkedList在遍历的过程中，如果有添加、删除等动作发生，会导致ConcurrentModificationException异常，和ArrayList类似。

3.6      判断存在或获取位置 

获取位置的IndexOf方法在remove(Object)中已经涉及，而判断存在的contains(Object)方法则主要是调用IndexOf方法，根据IndexOf返回的位置和-1进行比较进而判断指定数据是否存在。

3.7      注意 

LinkedList是无容量限制的；

LinkedList是非线程安全的；

LinkedList是基于双向链表实现的，当数据顺序无关的情况下，选择ArrayList还是LinkedList要从各动作的执行效率综合考虑。