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

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

public abstract class AbstractSequentialList<E> extends AbstractList<E> {
    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> 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> 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<? extends E> c) {
        try {
            boolean modified = false;
            ListIterator<E> e1 = listIterator(index);
            Iterator<? extends E> 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<E> iterator() {
        return listIterator();
    }
    public abstract ListIterator<E> listIterator(int index);
}

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

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

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

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

 public LinkedList() {   }
    public LinkedList(Collection<? extends E> c) {
        this();
        addAll(c);
    }

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

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

    private LinkedList<E> superClone() {
        try {
            return (LinkedList<E>) 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<E> 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<E> x = first; x != null; x = x.next)
            clone.add(x.item);
        return clone;
    }

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

LinkedList<Number> 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<Number> l=(LinkedList<Number>) list.clone();
		l.add(5);
		l.set(2, 33);
		for(Number i:l){
			System.out.println(i);// 1 2 33 4 5
		}

修改l的值list中的值不会受到影响，再举个例子：

String[] x={"a","c"};
		String[] y={"m","n"};
		LinkedList<String[]> list=new LinkedList<>();
		list.add(x);
		list.add(y);
		
		
		LinkedList<String[]> l=(LinkedList<String[]>) list.clone();
		l.get(1)[1]="ttttt";
		
		System.out.println(list.get(1)[1]);

这时候打印出的值为ttt，也就是修改克隆后的引用值，原值也会被修改，这时候就要用深度克隆了。如果细心且阅读过源代码的人就会发现，有些方法克隆链表元素的方法其实和clone方法是一样的，如下：

  public Object[] toArray() {
        Object[] result = new Object[size];
        int i = 0;
        for (Node<E> x = first; x != null; x = x.next)
            result[i++] = x.item;
        return result;
    }

 public <T> T[] toArray(T[] a) {
        if (a.length < size)
            a = (T[])java.lang.reflect.Array.newInstance(a.getClass().getComponentType(), size);
        int i = 0;
        Object[] result = a;
        for (Node<E> x = first; x != null; x = x.next)
            result[i++] = x.item;

        if (a.length > size)
            a[size] = null;

        return a;
    }