JAVA语言集合框架LinkedList详解.doc

《JAVA语言集合框架LinkedList详解.doc》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。

1、JAVA语言集合框架LinkedList详解一、概述     LinkedList与ArrayList一样实现List接口，只是ArrayList是List接口的大小可变数组的实现，LinkedList是List接口链表的实现。基于链表实现的方式使得LinkedList在插入和删除时更优于ArrayList，而随机访问则比ArrayList逊色些。     LinkedList实现所有可选的列表操作，并允许所有的元素包括null。     除了实现List接口外，LinkedList类还为在列表的开头及结尾get、remove和insert元素提供了统一的命名方法。这些操作允许将链

2、接列表用作堆栈、队列或双端队列。     此类实现Deque接口，为add、poll提供先进先出队列操作，以及其他堆栈和双端队列操作。     所有操作都是按照双重链接列表的需要执行的。在列表中编索引的操作将从开头或结尾遍历列表（从靠近指定索引的一端）。     同时，与ArrayList一样此实现不是同步的。     （以上摘自JDK6.0API）。二、源码分析     2.1、定义     首先我们先看LinkedList的定义：publicclassLinkedListextendsAbstractSequentialListimplementsList,D

3、eque,Cloneable,java.io.Serializable     从这段代码中我们可以清晰地看出LinkedList继承AbstractSequentialList，实现List、Deque、Cloneable、Serializable。其中AbstractSequentialList提供了List接口的骨干实现，从而最大限度地减少了实现受“连续访问”数据存储（如链接列表）支持的此接口所需的工作,从而以减少实现List接口的复杂度。Deque一个线性collection，支持在两端插入和移除元素，定义了双端队列的操作。2.2、属性     在LinkedList

4、中提供了两个基本属性size、header。privatetransientEntryheader=newEntry(null,null,null);privatetransientintsize=0;     其中size表示的LinkedList的大小，header表示链表的表头，Entry为节点对象。privatestaticclassEntry{Eelement;//元素节点Entrynext;//下一个元素Entryprevious;//上一个元素Entry(Eelement,Entrynext,Entryprevious){th

5、is.element=element;this.next=next;this.previous=previous;}}     上面为Entry对象的源代码，Entry为LinkedList的内部类，它定义了存储的元素。该元素的前一个元素、后一个元素，这是典型的双向链表定义方式。2.3、构造方法     LinkedList提高了两个构造方法：LinkedLis()和LinkedList(Collectionc)。/***构造一个空列表。*/publicLinkedList(){header.next=header.previous=header;}/***构

6、造一个包含指定collection中的元素的列表，这些元素按其collection的迭代器返回的顺序排列。*/publicLinkedList(Collectionc){this();addAll(c);}     LinkedList()构造一个空列表。里面没有任何元素，仅仅只是将header节点的前一个元素、后一个元素都指向自身。     LinkedList(Collectionc)：构造一个包含指定collection中的元素的列表，这些元素按其collection的迭代器返回的顺序排列。该构造函数首先会调用LinkedList(

7、)，构造一个空列表，然后调用了addAll()方法将Collection中的所有元素添加到列表中。以下是addAll()的源代码：/***添加指定collection中的所有元素到此列表的结尾，顺序是指定collection的迭代器返回这些元素的顺序。*/publicbooleanaddAll(Collectionc){returnaddAll(size,c);}/***将指定collection中的所有元素从指定位置开始插入此列表。其中inde