链式存储结构之LinkedList源码分析

链式存储结构之LinkedList源码分析

链式存储结构是用一组任意的存储单元存储线性表的数据元素，这组存储单元可以是连续的，也可以是不连续的。

• 为了表示每个数据元素a(i)和其直接后继数据元素a(i+1)之间的逻辑关系，对数据元素a(i)来说，除了存储其本身的信息外，还需存储一个指示其直接后继的信息(即直接后继的存储位置)。
• 我们把存储数据元素信息的域称为数据域，把存储直接后继位的域称为指针域。
• 指针域中存储的信息称做指针或链。这两部分信息组成数据元素a(i)的存储映像，称为结点。
• 链表中第一个结点的存储位置叫做头指针。
• 链表的最后一个结点指针为”空”(通常用NULL或^符号表示)

1. 链式存储结构的优缺点

优：删除和插入效率高
缺：查询效率低

2. 链表的分类

• 单链表

  n个结点链成一个链表，此链表的每个结点中只包含一个指针域

静态链表：静态链表其实是为了给没有指针的高级语言设计的一种实现单链表能力的方法。

• 循环链表

  将单链表中终端结点的指针端由空指针改为指向头结点，就使整个单链表形成了一个环，这种首尾相接单单链表称为单循环链表，简称循环链表

• 双向循环链表

  双向链表是在单向循环链表的每个结点中，再设置一个指向其前驱结点的指针域。

在Java中，我们常见具有代表性的链式存储结构有很多，这里我们以LinkedList为例，进行分析，看看它内部是如何实现链式存储结构的。

    
/**
 * LinkedList继承AbstractSequentialList抽象类,实现List、Deque(双端队列接口)、Cloneable、Serializable。
 * 
 * AbstractSequentiaList和其他RandomAccess主要的区别是AbstractSequentiaList的主要方法都是通过迭代器实现的。
 * 而不是直接实现的（不通过迭代器，比如ArrayList实现的方式是通过数组实现的。）
 * 因此对于一些可以提供RandomAccess的方法，直接使用方法可能更快。因为迭代器移动需要一定代价。
 *
 */
public class LinkedList<E> extends AbstractSequentialList<E> implements
        List<E>, Deque<E>, Queue<E>, Cloneable, Serializable {

    private static final long serialVersionUID = 876323262645176354L;

    transient int size = 0;//代表LinkedList中的节点个数

    transient Link<E> voidLink;// 头结点

    private static final class Link<ET> {
        ET data;

        Link<ET> previous, next;// 双向链表

        Link(ET o, Link<ET> p, Link<ET> n) {
            data = o;
            previous = p;
            next = n;
        }
    }

    /**
     * 作为一个List，LinkedList肯定也包含一个迭代器
     */
    private static final class LinkIterator<ET> implements ListIterator<ET> {
        int pos, expectedModCount;

        final LinkedList<ET> list;

        Link<ET> link, lastLink;// link表示当前正在遍历的结点，lastLink表示最后的结点

        LinkIterator(LinkedList<ET> object, int location) {
            list = object;
            expectedModCount = list.modCount;
            if (location >= 0 && location <= list.size) {
                // pos ends up as -1 if list is empty, it ranges from -1 to
                // list.size - 1
                // if link == voidLink then pos must == -1
                link = list.voidLink;//设置当前的指针为空指针

                // 为了提高效率，采用二分法的思想，需要判断前半段和后半段进行赋值
                if (location < list.size / 2) {// 表示在前半段
                    for (pos = -1; pos + 1 < location; pos++) {
                        link = link.next;
                    }
                } else {// 表示在后半段
                    for (pos = list.size; pos >= location; pos--) {
                        link = link.previous;
                    }
                }
            } else {
                throw new IndexOutOfBoundsException();
            }
        }

        /**
         * 在迭代器中的添加方法，单向链表
         */
        public void add(ET object) {
            if (expectedModCount == list.modCount) {
                Link<ET> next = link.next;// 拿到当前结点的下一个结点
                Link<ET> newLink = new Link<ET>(object, link, next);//创建一个新结点,头部指向当前结点,尾部指向next结点
                link.next = newLink;// 把当前结点的下一个结点指向newLink
                next.previous = newLink;// 把先前结点的下一个结点的前驱指向newLink
                link = newLink;//把当前结点link变为newLink
                lastLink = null;//指向新结点后,把LastLink置空
                pos++;
                expectedModCount++;
                list.size++;// 长度+1
                list.modCount++;// 计量器+1
            } else {
                throw new ConcurrentModificationException();
            }
        }

        public boolean hasNext() {
            return link.next != list.voidLink;
        }

        public boolean hasPrevious() {
            return link != list.voidLink;
        }

        /**
         * 取出一个结点数据
         * @return
         */
        public ET next() {
            if (expectedModCount == list.modCount) {
                LinkedList.Link<ET> next = link.next;// 拿到当前结点的下一个结点
                if (next != list.voidLink) {// 如果next结点不为空结点
                    lastLink = link = next;//将当前结点和lastLink设置为next结点
                    pos++;
                    return link.data;
                }
                throw new NoSuchElementException();
            }
            throw new ConcurrentModificationException();
        }

        public int nextIndex() {
            return pos + 1;
        }

        /**
         * 取出上一个结点数据
         * @return
         */
        public ET previous() {
            if (expectedModCount == list.modCount) {
                if (link != list.voidLink) {// 如果当前结点不为空结点
                    lastLink = link;//将最后一个结点设置为当前结点
                    link = link.previous;//再设置当前结点为当前结点之前的结点
                    pos--;
                    return lastLink.data;
                }
                throw new NoSuchElementException();
            }
            throw new ConcurrentModificationException();
        }

        public int previousIndex() {
            return pos;
        }

        /**
         *移除当前结点
         */
        public void remove() {
            if (expectedModCount == list.modCount) {
                if (lastLink != null) {
                    Link<ET> next = lastLink.next;
                    Link<ET> previous = lastLink.previous;
                    next.previous = previous;
                    previous.next = next;
                    if (lastLink == link) {
                        pos--;
                    }
                    link = previous;
                    lastLink = null;
                    expectedModCount++;
                    list.size--;
                    list.modCount++;
                } else {
                    throw new IllegalStateException();
                }
            } else {
                throw new ConcurrentModificationException();
            }
        }

        /**
         * 修改当前结点
         */
        public void set(ET object) {
            if (expectedModCount == list.modCount) {
                if (lastLink != null) {
                    lastLink.data = object;
                } else {
                    throw new IllegalStateException();
                }
            } else {
                throw new ConcurrentModificationException();
            }
        }
    }

    /*
     * NOTES:descendingIterator is not fail-fast, according to the documentation
     * and test case.
     */
    private class ReverseLinkIterator<ET> implements Iterator<ET> {
        private int expectedModCount;

        private final LinkedList<ET> list;

        private Link<ET> link;

        private boolean canRemove;

        ReverseLinkIterator(LinkedList<ET> linkedList) {
            list = linkedList;
            expectedModCount = list.modCount;
            link = list.voidLink;
            canRemove = false;
        }

        public boolean hasNext() {
            return link.previous != list.voidLink;
        }

        public ET next() {
            if (expectedModCount == list.modCount) {
                if (hasNext()) {
                    link = link.previous;
                    canRemove = true;
                    return link.data;
                }
                throw new NoSuchElementException();
            }
            throw new ConcurrentModificationException();

        }

        public void remove() {
            if (expectedModCount == list.modCount) {
                if (canRemove) {
                    Link<ET> next = link.previous;
                    Link<ET> previous = link.next;
                    next.next = previous;
                    previous.previous = next;
                    link = previous;
                    list.size--;
                    list.modCount++;
                    expectedModCount++;
                    canRemove = false;
                    return;
                }
                throw new IllegalStateException();
            }
            throw new ConcurrentModificationException();
        }
    }

    /**
     * LinkedList无参构造
     */
    public LinkedList() {
        // 实例化头结点
        voidLink = new Link<E>(null, null, null);
        // 分别让头结点的previous和next等于自身
        voidLink.previous = voidLink;
        voidLink.next = voidLink;
    }

    /**
     * 接收一个Collection参数的LinkedList构造方法
     */
    public LinkedList(Collection<? extends E> collection) {
        this();
        addAll(collection);
    }

    /**
     * 添加方法，在指定位置进行添加
     */
    @Override
    public void add(int location, E object) {
        if (location >= 0 && location <= size) {
            Link<E> link = voidLink;
            // 为了提高效率，采用二分法的思想，需要判断前半段和后半段进行查找
            if (location < (size / 2)) {// 表示在前半段
                for (int i = 0; i <= location; i++) {
                    link = link.next;
                }
            } else {// 表示在后半段
                for (int i = size; i > location; i--) {
                    link = link.previous;
                }
            }
            Link<E> previous = link.previous; // 获取当前结点的前一结点previous
            Link<E> newLink = new Link<E>(object, previous, link);//创建新结点，头部指向previous，尾部指向当前结点
            previous.next = newLink;// 把previous.next结点指向新节点
            link.previous = newLink;// 同时让link.previous指向新节点
            size++;// 长度+1
            modCount++;// 计量器+1
        } else {
            throw new IndexOutOfBoundsException();
        }
    }

    /**
     * 将元素(E)添加到LinkedList中
     */
    @Override
    public boolean add(E object) {
        return addLastImpl(object);
    }

    /**
     * 在最后添加元素的方法
     */
    private boolean addLastImpl(E object) {
        //双向循环链表
        // 将头结点的previous，其实就是头结点自己，赋值给oldLast
        Link<E> oldLast = voidLink.previous;
        // 新建一个要插入的新节点，其数据域是object，previous结点是oldLast，next结点是voidLink
        Link<E> newLink = new Link<E>(object, oldLast, voidLink);
        // 让头结点的前面previous指向新建结点
        voidLink.previous = newLink;
        // 让oldLast.next指向新建结点
        oldLast.next = newLink;
        size++;// 长度+1
        modCount++;// 计量器+1
        return true;
    }

    /**
     * 添加集合,在指定位置进行添加
     */
    @Override
    public boolean addAll(int location, Collection<? extends E> collection) {
        if (location < 0 || location > size) {
            throw new IndexOutOfBoundsException();
        }
        int adding = collection.size();
        if (adding == 0) {
            return false;
        }
        Collection<? extends E> elements = (collection == this) ?
                new ArrayList<E>(collection) : collection;
        // 为了提高效率，采用二分法的思想，需要判断前半段和后半段进行查找
        Link<E> previous = voidLink;
        //获取要插入位置前一位的结点previous
        if (location < (size / 2)) {
            for (int i = 0; i < location; i++) {
                previous = previous.next;
            }
        } else {
            for (int i = size; i >= location; i--) {
                previous = previous.previous;
            }
        }
        Link<E> next = previous.next;//获取previous结点的后一位
        //循环创建并设置结点
        for (E e : elements) {
            //创建一个新的结点,数据为e,头部指向previous，尾部指向null
            Link<E> newLink = new Link<E>(e, previous, null);
            previous.next = newLink;//设置previous.next为新创建的结点
            previous = newLink;//设置previous为新创建的结点
        }
        previous.next = next;//最后一个插入的结点 尾部指向next结点
        next.previous = previous;//next结点到头部指向最后一个插入的结点
        size += adding;// 长度+adding
        modCount++;// 计量器+1
        return true;
    }

    /**
     * 添加集合到LinkedList
     */
    @Override
    public boolean addAll(Collection<? extends E> collection) {
        int adding = collection.size();
        if (adding == 0) {
            return false;
        }
        Collection<? extends E> elements = (collection == this) ?
                new ArrayList<E>(collection) : collection;

        //空指针的头部指向链表到末尾(双向循环链表),即previous为最后一个结点
        Link<E> previous = voidLink.previous;
        for (E e : elements) {
            //创建一个新的结点,数据为e,头部指向previous，尾部指向nul
            Link<E> newLink = new Link<E>(e, previous, null);
            previous.next = newLink;//设置previous.next为新创建的结点
            previous = newLink;//设置previous为新创建的结点
        }
        previous.next = voidLink;//最后一个插入的结点也是最后一个结点，尾部指向为头结点
        voidLink.previous = previous;//头结点头部指向最后一个结点，这样链表就首尾连起来了
        size += adding;// 长度+adding
        modCount++;// 计量器+1
        return true;
    }


    public void addFirst(E object) {
        addFirstImpl(object);
    }

    /**
     * 添加元素到LinkedList首部
     */
    private boolean addFirstImpl(E object) {
        Link<E> oldFirst = voidLink.next;//获取头结点的下一个结点oldFirst
        Link<E> newLink = new Link<E>(object, voidLink, oldFirst);//创建新的结点，设置数据为object,头部指向头结点，尾部指向oldFirst
        voidLink.next = newLink;//修改头结点的尾部指向新创建的结点
        oldFirst.previous = newLink;//修改oldFirst头部指向新创建的结点
        size++;//长度+1
        modCount++;//计量器+1
        return true;
    }

    /**
     * Adds the specified object at the end of this {@code LinkedList}.
     * @param object
     *            the object to add.
     */
    public void addLast(E object) {
        addLastImpl(object);
    }

    /**
     * 清除所有的元素，头结点自己指向自己
     * @see List#isEmpty
     * @see #size
     */
    @Override
    public void clear() {
        if (size > 0) {
            size = 0;
            voidLink.next = voidLink;
            voidLink.previous = voidLink;
            modCount++;
        }
    }

    /**
     * 克隆方法，由于LinkedList实现了Cloneable接口，所以能被克隆
     * LinkedList的Clone()只是浅复制，也就是只能复制对象的引用，而不能再内存中新生成一个对象，所以复制之后的LinkedList和原始的LinkedList中存储的对象是共享的。
     */
    @SuppressWarnings("unchecked")
    @Override
    public Object clone() {
        try {
            LinkedList<E> l = (LinkedList<E>) super.clone();
            l.size = 0;
            l.voidLink = new Link<E>(null, null, null);
            l.voidLink.previous = l.voidLink;
            l.voidLink.next = l.voidLink;
            l.addAll(this);
            return l;
        } catch (CloneNotSupportedException e) {
            throw new AssertionError(e);
        }
    }

    /**
     * 查找是否包含某个元素
     */
    @Override
    public boolean contains(Object object) {
        Link<E> link = voidLink.next;//获取头结点指向的第一个结点link
        if (object != null) {//查找的元素不为null
            while (link != voidLink) {//当头结点不是指向自身
                //判断是否查找到
                if (object.equals(link.data)) {
                    return true;
                }
                //将link设置为link后面的结点,以便继续循环
                link = link.next;
            }
        } else {//查找的元素为null
            while (link != voidLink) {
                //判断是否查找到
                if (link.data == null) {
                    return true;
                }
                //将link设置为link后面的结点,以便继续循环
                link = link.next;
            }
        }
        return false;
    }

    /**
     * 获取某个位置的元素
     * @param location
     * @return
     */
    @Override
    public E get(int location) {
        if (location >= 0 && location < size) {
            Link<E> link = voidLink;
            // 采用二分法的思想，先找前半段
            if (location < (size / 2)) {
                for (int i = 0; i <= location; i++) {
                    link = link.next;
                }
            } else {// 再找后半段
                for (int i = size; i > location; i--) {
                    link = link.previous;
                }
            }
            return link.data;// 返回结点内容
        }
        throw new IndexOutOfBoundsException();
    }

    /**
     * Returns the first element in this {@code LinkedList}.
     * @return the first element.
     * @throws NoSuchElementException
     *             if this {@code LinkedList} is empty.
     */
    public E getFirst() {
        return getFirstImpl();
    }

    /**
     * 获取第一个元素
     * @return
     */
    private E getFirstImpl() {
        Link<E> first = voidLink.next;
        if (first != voidLink) {
            return first.data;
        }
        throw new NoSuchElementException();
    }

    /**
     * 获取最后一个元素
     */
    public E getLast() {
        Link<E> last = voidLink.previous;
        if (last != voidLink) {
            return last.data;
        }
        throw new NoSuchElementException();
    }

    /**
     * 从前向后查找元素所在的索引
     */
    @Override
    public int indexOf(Object object) {
        int pos = 0;
        Link<E> link = voidLink.next;
        if (object != null) {
            while (link != voidLink) {
                if (object.equals(link.data)) {
                    return pos;
                }
                link = link.next;
                pos++;
            }
        } else {
            while (link != voidLink) {
                if (link.data == null) {
                    return pos;
                }
                link = link.next;
                pos++;
            }
        }
        return -1;
    }

    /**
     * 从后向前查找元素所在的索引。
     */
    @Override
    public int lastIndexOf(Object object) {
        int pos = size;
        Link<E> link = voidLink.previous;
        if (object != null) {
            while (link != voidLink) {
                pos--;
                if (object.equals(link.data)) {
                    return pos;
                }
                link = link.previous;
            }
        } else {
            while (link != voidLink) {
                pos--;
                if (link.data == null) {
                    return pos;
                }
                link = link.previous;
            }
        }
        return -1;
    }

    /**
     * Returns a ListIterator on the elements of this {@code LinkedList}. The
     * elements are iterated in the same order that they occur in the
     * {@code LinkedList}. The iteration starts at the specified location.
     *
     * @param location
     *            the index at which to start the iteration
     * @return a ListIterator on the elements of this {@code LinkedList}
     * @throws IndexOutOfBoundsException
     *             if {@code location < 0 || location > size()}
     * @see ListIterator
     */
    @Override
    public ListIterator<E> listIterator(int location) {
        return new LinkIterator<E>(this, location);
    }

    /**
     * 删除指定索引位置的元素
     */
    @Override
    public E remove(int location) {
        if (location >= 0 && location < size) {
            Link<E> link = voidLink;
            if (location < (size / 2)) {// 采用二分法的思想，先找前半段
                for (int i = 0; i <= location; i++) {
                    link = link.next;
                }
            } else {// 再找后半段
                for (int i = size; i > location; i--) {
                    link = link.previous;
                }
            }
            Link<E> previous = link.previous;//previous为location位置结点的上一个结点
            Link<E> next = link.next;//next为location位置结点的下一个结点
            previous.next = next;//修改previous尾部指向next结点
            next.previous = previous;//修改next头部指向previous结点
            size--;//长度-1
            modCount++;//计量器+1
            return link.data;//返回删除的结点内容
        }
        throw new IndexOutOfBoundsException();
    }

    @Override
    public boolean remove(Object object) {
        return removeFirstOccurrenceImpl(object);
    }

    /**
     * Removes the first object from this {@code LinkedList}.
     *
     * @return the removed object.
     * @throws NoSuchElementException
     *             if this {@code LinkedList} is empty.
     */
    public E removeFirst() {
        return removeFirstImpl();
    }

    /**
     * 删除第一个元素
     * @return
     */
    private E removeFirstImpl() {
        Link<E> first = voidLink.next;//头结点尾部指向的结点即为第一个元素的结点
        if (first != voidLink) {
            Link<E> next = first.next;//第二个元素的结点
            voidLink.next = next;//头结点的尾部指向第二个元素结点
            next.previous = voidLink;//第二个元素的结点头部指向头结点
            size--;//长度-1
            modCount++;//计量器+1
            return first.data;//返回移除元素的结点内容
        }
        throw new NoSuchElementException();
    }

    /**
     * Removes the last object from this {@code LinkedList}.
     * @return the removed object.
     * @throws NoSuchElementException
     *             if this {@code LinkedList} is empty.
     */
    public E removeLast() {
        return removeLastImpl();
    }

    /**
     * 删除最后一个元素
     */
    private E removeLastImpl() {
        Link<E> last = voidLink.previous;//头结点头部指向的结点为最后一个元素的结点
        if (last != voidLink) {
            Link<E> previous = last.previous;//倒数第二个元素的结点
            voidLink.previous = previous;//头结点的头部指向倒数第二个元素的结点
            previous.next = voidLink;//倒数第二个元素的结点尾部指向头结点
            size--;//长度-1
            modCount++;//计量器+1
            return last.data;
        }
        throw new NoSuchElementException();
    }

    /**
     * {@inheritDoc}
     *
     * @see java.util.Deque#descendingIterator()
     * @since 1.6
     */
    public Iterator<E> descendingIterator() {
        return new ReverseLinkIterator<E>(this);
    }

    /**
     * {@inheritDoc}
     *
     * @see java.util.Deque#offerFirst(java.lang.Object)
     * @since 1.6
     */
    public boolean offerFirst(E e) {
        return addFirstImpl(e);
    }

    /**
     * {@inheritDoc}
     *
     * @see java.util.Deque#offerLast(java.lang.Object)
     * @since 1.6
     */
    public boolean offerLast(E e) {
        return addLastImpl(e);
    }

    /**
     * {@inheritDoc}
     *
     * @see java.util.Deque#peekFirst()
     * @since 1.6
     */
    public E peekFirst() {
        return peekFirstImpl();
    }

    /**
     * {@inheritDoc}
     *
     * @see java.util.Deque#peekLast()
     * @since 1.6
     */
    public E peekLast() {
        Link<E> last = voidLink.previous;
        return (last == voidLink) ? null : last.data;
    }

    /**
     * {@inheritDoc}
     *
     * @see java.util.Deque#pollFirst()
     * @since 1.6
     */
    public E pollFirst() {
        return (size == 0) ? null : removeFirstImpl();
    }

    /**
     * {@inheritDoc}
     *
     * @see java.util.Deque#pollLast()
     * @since 1.6
     */
    public E pollLast() {
        return (size == 0) ? null : removeLastImpl();
    }

    /**
     * {@inheritDoc}
     *
     * @see java.util.Deque#pop()
     * @since 1.6
     */
    public E pop() {
        return removeFirstImpl();
    }

    /**
     * {@inheritDoc}
     *
     * @see java.util.Deque#push(java.lang.Object)
     * @since 1.6
     */
    public void push(E e) {
        addFirstImpl(e);
    }

    /**
     * {@inheritDoc}
     *
     * @see java.util.Deque#removeFirstOccurrence(java.lang.Object)
     * @since 1.6
     */
    public boolean removeFirstOccurrence(Object o) {
        return removeFirstOccurrenceImpl(o);
    }

    /**
     * {@inheritDoc}
     *
     * @see java.util.Deque#removeLastOccurrence(java.lang.Object)
     * @since 1.6
     */
    public boolean removeLastOccurrence(Object o) {
        Iterator<E> iter = new ReverseLinkIterator<E>(this);
        return removeOneOccurrence(o, iter);
    }

    private boolean removeFirstOccurrenceImpl(Object o) {
        Iterator<E> iter = new LinkIterator<E>(this, 0);
        return removeOneOccurrence(o, iter);
    }

    private boolean removeOneOccurrence(Object o, Iterator<E> iter) {
        while (iter.hasNext()) {
            E element = iter.next();
            if (o == null ? element == null : o.equals(element)) {
                iter.remove();
                return true;
            }
        }
        return false;
    }

    /**
     * 修改指定位置的元素
     */
    @Override
    public E set(int location, E object) {
        if (location >= 0 && location < size) {
            Link<E> link = voidLink;
            if (location < (size / 2)) {// 采用二分法的思想，先找前半段
                for (int i = 0; i <= location; i++) {
                    link = link.next;
                }
            } else {// 采用二分法的思想，先找前半段
                for (int i = size; i > location; i--) {
                    link = link.previous;
                }
            }
            E result = link.data;//记录当前location位置的结点内容
            link.data = object;//修改location位置的结点内容为object
            return result;//返回修改前location位置的结点内容
        }
        throw new IndexOutOfBoundsException();
    }

    /**
     * Returns the number of elements in this {@code LinkedList}.
     *
     * @return the number of elements in this {@code LinkedList}.
     */
    @Override
    public int size() {
        return size;
    }

    public boolean offer(E o) {
        return addLastImpl(o);
    }

    public E poll() {
        return size == 0 ? null : removeFirst();
    }

    public E remove() {
        return removeFirstImpl();
    }

    public E peek() {
        return peekFirstImpl();
    }

    private E peekFirstImpl() {
        Link<E> first = voidLink.next;
        return first == voidLink ? null : first.data;
    }

    public E element() {
        return getFirstImpl();
    }

    /**
     * 创建一个新的Object数组，按顺序循环将结点内容设置到数组，然后返回
     */
    @Override
    public Object[] toArray() {
        int index = 0;
        Object[] contents = new Object[size];
        Link<E> link = voidLink.next;
        while (link != voidLink) {
            contents[index++] = link.data;
            link = link.next;
        }
        return contents;
    }

    /**
     * 按顺序循环将结点内容设置到给定的数组，并返回
     */
    @Override
    @SuppressWarnings("unchecked")
    public <T> T[] toArray(T[] contents) {
        int index = 0;
        if (size > contents.length) {
            //如果给定到数组长度不够,则通过反射方式创建长度够的数组
            Class<?> ct = contents.getClass().getComponentType();
            contents = (T[]) Array.newInstance(ct, size);
        }
        Link<E> link = voidLink.next;
        while (link != voidLink) {
            contents[index++] = (T) link.data;
            link = link.next;
        }
        if (index < contents.length) {
            contents[index] = null;
        }
        return contents;
    }

    private void writeObject(ObjectOutputStream stream) throws IOException {
        stream.defaultWriteObject();
        stream.writeInt(size);
        Iterator<E> it = iterator();
        while (it.hasNext()) {
            stream.writeObject(it.next());
        }
    }

    @SuppressWarnings("unchecked")
    private void readObject(ObjectInputStream stream) throws IOException,
            ClassNotFoundException {
        stream.defaultReadObject();
        size = stream.readInt();
        voidLink = new Link<E>(null, null, null);
        Link<E> link = voidLink;
        for (int i = size; --i >= 0;) {
            Link<E> nextLink = new Link<E>((E) stream.readObject(), link, null);
            link.next = nextLink;
            link = nextLink;
        }
        link.next = voidLink;
        voidLink.previous = link;
    }

Iterator和ListIterator主要区别在以下方面：

• ListIterator只能用于List，Iterator是通用的
• Iterator容易引起并发修改异常问题，而ListIterator可以避免线程安全问题的发生，因为其有内置的add()等修改集合的方法。
• ListIterator和Iterator都有hasNext()和next()方法，可以实现顺序向后遍历，但是ListIterator有hasPrevious()和previous()方法，可以实现逆向（顺序向前）遍历。Iterator就不可以。
• ListIterator可以定位当前的索引位置，nextIndex()和previousIndex()可以实现。Iterator没有此功能。
• 都可实现删除对象，但是ListIterator可以实现对象的修改，set()方法可以实现。Iierator仅能遍历，不能修改。
  因为ListIterator的这些功能，可以实现对LinkedList等List数据结构的操作。其实，数组对象也可以用迭代器来实现。