Java 7源码分析第9篇 - List集合基于链表的实现 - JAVA

基于链表实现的集合在存储的速度上肯定比不上基于数组实现的集合，但是链表实现的最大优点在于，频繁的操作节点时速度就比较快了，例如删除一个节点，不需要向数组一样，调用System.arraycopy()方法进行后续的整体左移。先看一下AbstractSequencialList抽象类：

public abstract class AbstractSequentialList
  
    extends AbstractList
   
     { protected AbstractSequentialList() { } public E get(int index) { try { return listIterator(index).next(); } catch (NoSuchElementException exc) { throw new IndexOutOfBoundsException("Index: "+index); } } public E set(int index, E element) { try { ListIterator
    
      e = listIterator(index); E oldVal = e.next(); e.set(element); return oldVal; } catch (NoSuchElementException exc) { throw new IndexOutOfBoundsException("Index: "+index); } } public void add(int index, E element) { try { listIterator(index).add(element); } catch (NoSuchElementException exc) { throw new IndexOutOfBoundsException("Index: "+index); } } public E remove(int index) { try { ListIterator
     
       e = listIterator(index); E outCast = e.next(); e.remove(); return outCast; } catch (NoSuchElementException exc) { throw new IndexOutOfBoundsException("Index: "+index); } } // Bulk Operations public boolean addAll(int index, Collection
       c) { try { boolean modified = false; ListIterator
      
        e1 = listIterator(index); Iterator
        e2 = c.iterator(); while (e2.hasNext()) { e1.add(e2.next()); modified = true; } return modified; } catch (NoSuchElementException exc) { throw new IndexOutOfBoundsException("Index: "+index); } } // Iterators public Iterator
       
         iterator() { return listIterator(); } public abstract ListIterator
        
          listIterator(int index); }

这个类大量使用了Iterator进行集合的顺序遍历，由于不能随机定位，所以这个类注重顺序遍历，如果要自己实现一个链表集合的话，最好继承这个抽象类，这样就不用费工夫自己来实现这么多的方法了。

LinkedList就是子结构List的一个现实。并且它实现了其他接口，如Deque -double ended queue双向队列，还有Cloneable,java.io.Serializable可克隆和可序列化结构，以及List下的子接口AbstractSequentialList顺序获取结构。下面来研究LinkedList类，这个类是基于双向链表实现的，所以可以在两端进行操作，这就需要有两个指向首尾节点的指针：

transient int size = 0;
    transient Node
  
    first;
    transient Node
   
     last; // 链表节点 private static class Node
    
      { E item; Node
     
       next; Node
      
        prev; Node(Node
       
         prev, E element, Node
        
          next) { this.item = element; this.next = next; this.prev = prev; } }

通过一个内部的私有类表示链表的Node结点，这个节点有指向前和后的指针。看一下构造函数：

 public LinkedList() {   }
    public LinkedList(Collection
   c) {
        this();
        addAll(c);
    }

同样可以将其他集合中的元素转换为链表结构的集合。下面当然就是对双向链表进行节点操作了。包括删除、查询链表首尾节点、查找某个节点、顺序、逆序遍历结点等操作，方法很简单，有兴趣的读者可以自己下去研究。顺便提醒一下，数组可以用来实现栈操作，链表同样可以，在这个类中提供了pop()、push()等方法，如果你要进行栈操作的话，同样调用这些方法可以实现。只要在双链表的一端操作就可以了。

由于这个类还实现了Conable接口，所以实现了clone()方法，但是这个方法只实现了浅克隆，源代码如下：

    private LinkedList
  
    superClone() {
        try {
            return (LinkedList
   
    ) super.clone(); } catch (CloneNotSupportedException e) { throw new InternalError(); } } /** * Returns a shallow copy of this LinkedList. (The elements * themselves are not cloned.) */ public Object clone() {// 只克隆引用 LinkedList
    
      clone = superClone(); // Put clone into "virgin" state clone.first = clone.last = null; clone.size = 0; clone.modCount = 0; // Initialize clone with our elements for (Node
     
       x = first; x != null; x = x.next) clone.add(x.item); return clone; }

所以如果你操作的节点中item是基本类型的话，修改时两者不会影响。如果item中是引用类型的话，两者的值是会相互影响的，这时候就必须使用自己克隆的方法了。举个例子：

LinkedList
  
    list=new LinkedList<>();
		list.add(1);
		list.add(2);
		list.add(3);
		list.add(4);
		for(Number i:list){
			System.out.println(i);// 1 2 3 4 
		}
		
		LinkedList
   
     l=(LinkedList
    
     ) list.clone(); l.add(5); l.

Java 7源码分析第9篇 - List集合基于链表的实现(一)