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要从各动作的执行效率综合考虑。