（源码分析）JDK1.8 LinkedList源码分析

灰太狼 2021-10-18 08:22 532阅读 0赞

### 目录 ###

*  链表的特点
 *   *  成员变量
     *  构造方法
     *  add(E e)
     *  offer(E e)
     *  add(int index, E element)
     *  addFirst(E e)
     *  addLast(E e)
     *  push(E e)
     *  offerFirst(E e)
     *  offerLast(E e)
     *  remove(int index)
     *  remove(Object o)
     *  removeFirst()
     *  removeLast()
     *  pop()
     *  get(int index)
     *  getFirst()
     *  getLast()
     *  addFirst()
     *  addLast()
     *  peek()
     *  peekFirst()
     *  peekLast()
     *  poll()
     *  pollFirst()
     *  pollLast()
     *  linkFirst(E e)
     *  linkLast(E e)
     *  linkBefore(E e, Node<E> succ)
     *  unlinkFirst(Node<E> f)
     *  unlinkLast(Node<E> l)
     *  unlink(Node<E> x)
     *  set(int index, E element)
     *  element()
     *  size()
     *  clear
     *  clone()
     *  contains(Object o)
     *  containsAll(Collection<?> c)
     *  indexOf(Object o)
     *  lastIndexOf(Object o)
     *  isEmpty
     *  retainAll(Collection<?> c)
     *  iterator()
     *  listIterator()
 *  总结

# 链表的特点 #

链表是一种物理储存在储存单元上非连续的储存结构，数据元素的逻辑顺序是通过链表中的指针连接此序实现的，链表由一系列节点(链表中每一个元素成为节点)组成，节点可以在运行时动态生成，每个节点包括两个部分：一个是储存数据元素的数据源，另一个储存下一个节点地址的指针域

双向链表是链表的一种，由节点组成，每个数据节点中都有两个指针，分别指向前一个节点(前继节点)和后一个节点(后继节点)

## 成员变量 ##

private static final long serialVersionUID = 876323262645176354L; // 用于序列化与反序列化时验证版本是否一致
    transient int size = 0; // 链表的容量(长度)
    transient Node<E> first; // 前继节点
    transient Node<E> last; // 后继节点

## 构造方法 ##

*  无参构造方法

public LinkedList() { 
    }

*  有参构造方法(参数为实现了Connection接口的集合类)

public LinkedList(Collection<? extends E> c) { 
        this();
        addAll(c);
    }
    
    /* * 在尾节点添加一个LinkedList */
    public boolean addAll(Collection<? extends E> c) { 
        return addAll(size, c);
    }
    
    /* * 在指定位置添加一个LinkedList */
    public boolean addAll(int index, Collection<? extends E> c) { 
        checkPositionIndex(index); // 判断下标index是否越界
        Object[] a = c.toArray();
        int numNew = a.length;
        if (numNew == 0)
            return false;
        Node<E> pred, succ;
        if (index == size) { 
            succ = null;
            pred = last;
        } else { 
            succ = node(index);
            pred = succ.prev;
        }
        for (Object o : a) { 
            E e = (E) o;
            Node<E> newNode = new Node<>(pred, e, null);
            if (pred == null)
                first = newNode;
            else
                pred.next = newNode;
            pred = newNode;
        }
        if (succ == null) { 
            last = pred;
        } else { 
            pred.next = succ;
            succ.prev = pred;
        }
        size += numNew;
        modCount++;
        return true;
    }

## add(E e) ##

/* * 插入元素 */
    public boolean add(E e) { 
        linkLast(e);
        return true;
    }
    
    /* * 在尾部插入元素 */
    void linkLast(E e) { 
        final Node<E> l = last; // 尾节点
        final Node<E> newNode = new Node<>(l, e, null); // 创建新节点，new Node<>(l, e, null)，l为前继节点，e为新创建的节点，null为后继节点
        last = newNode; // 新节点变成尾节点
        if (l == null) // 如果原来的尾节点为null，就相当于原来的LinkedList里面根本就没有元素
            first = newNode; // 新节点也为首节点，相当于第一次add元素的时候，第一个元素即为首节点，也为尾节点
        else
            l.next = newNode; // 设置原来的尾节点的后继节点为新节点
        size++;
        modCount++; // 修改次数加1
    }

## offer(E e) ##

/* * 底层是通过调用add(E e)方法来插入元素的，和add(E e)方法是一样的 */
    public boolean offer(E e) { 
        return add(e);
    }

## add(int index, E element) ##

/* * 在指定位置插入元素 */
    public void add(int index, E element) { 
        checkPositionIndex(index); // 判断下标index是否越界
        if (index == size) // 判断是不是从链表尾部添加元素
            linkLast(element); // 直接添加到尾部
        else
            linkBefore(element, node(index)); // element是要插入的元素，node(index)是原本在index处的节点
    }
    
    /* * 判断下标index是否越界 */
    private void checkPositionIndex(int index) { 
        if (!isPositionIndex(index))
            throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
    }
    
    /* * 在尾部添加节点 */
    void linkLast(E e) { 
        final Node<E> l = last;
        final Node<E> newNode = new Node<>(l, e, null);
        last = newNode;
        if (l == null)
            first = newNode;
        else
            l.next = newNode;
        size++;
        modCount++;
    }
    
    /* * 在指定位置插入元素 */
    void linkBefore(E e, Node<E> succ) { 
        final Node<E> pred = succ.prev; // 原节点的前继节点
        final Node<E> newNode = new Node<>(pred, e, succ); // 创建新节点
        succ.prev = newNode;
        if (pred == null) // 当原节点为首节点时
            first = newNode; // 新节点也为首节点
        else
            pred.next = newNode;
        size++;
        modCount++;
    }
    
    /* * 获取在index处的节点 */
    Node<E> node(int index) { 
        if (index < (size >> 1)) { 
            Node<E> x = first;
            for (int i = 0; i < index; i++)
                x = x.next;
            return x;
        } else { 
            Node<E> x = last;
            for (int i = size - 1; i > index; i--)
                x = x.prev;
            return x;
        }
    }

## addFirst(E e) ##

/* * 在链表首部添加元素 */
    public void addFirst(E e) { 
        linkFirst(e);
    }
        
    /* * 在链表首部添加元素 */
    private void linkFirst(E e) { 
        final Node<E> f = first;
        final Node<E> newNode = new Node<>(null, e, f);
        first = newNode;
        if (f == null)
            last = newNode;
        else
            f.prev = newNode;
        size++;
        modCount++;
    }

## addLast(E e) ##

/* * 在链表尾部添加元素 */
    public void addLast(E e) { 
        linkLast(e);
    }
        
    /* * 在链表尾部添加元素 */
    void linkLast(E e) { 
        final Node<E> l = last;
        final Node<E> newNode = new Node<>(l, e, null);
        last = newNode;
        if (l == null)
            first = newNode;
        else
            l.next = newNode;
        size++;
        modCount++;
    }

## push(E e) ##

public void push(E e) { 
        addFirst(e);
    }

## offerFirst(E e) ##

/* * 底层是通过调用addFirst(E e)方法在链表首部添加元素 */
    public boolean offerFirst(E e) { 
        addFirst(e);
        return true;
    }

## offerLast(E e) ##

/* * 底层是通过调用addLast(E e)来实现在链表尾部添加元素 */
    public boolean offerLast(E e) { 
        addLast(e);
        return true;
    }

## remove(int index) ##

/* * 删除尾节点元素 */
    public E remove(int index) { 
        checkElementIndex(index);
        return unlink(node(index));
    }
        
    /* * 判断下标index是否越界 */
    private void checkElementIndex(int index) { 
        if (!isElementIndex(index))
            throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
    }
    
    /* * 获取在index处的节点 */
    Node<E> node(int index) { 
        if (index < (size >> 1)) {  // 判断index与size/2的大小，如果更大，则正向遍历
            Node<E> x = first;
            for (int i = 0; i < index; i++)
                x = x.next;
            return x;
        } else {  // 反向遍历
            Node<E> x = last;
            for (int i = size - 1; i > index; i--)
                x = x.prev;
            return x;
        }
    }
    
    /* * 解链(删除尾节点元素) */
    E unlink(Node<E> x) { 
        final E element = x.item;
        final Node<E> next = x.next;
        final Node<E> prev = x.prev;
        if (prev == null) { 
            first = next;
        } else { 
            prev.next = next;
            x.prev = null;
        }
        if (next == null) { 
            last = prev;
        } else { 
            next.prev = prev;
            x.next = null;
        }
        x.item = null;
        size--;
        modCount++;
        return element;
    }

## remove(Object o) ##

/* * 删除指定元素 */
    public boolean remove(Object o) { 
        if (o == null) { 
            for (Node<E> x = first; x != null; x = x.next) { 
                if (x.item == null) { 
                    unlink(x);
                    return true;
                }
            }
        } else { 
            for (Node<E> x = first; x != null; x = x.next) { 
                if (o.equals(x.item)) { 
                    unlink(x);
                    return true;
                }
            }
        }
        return false;
    }
        
    /* * 解链(删除尾节点元素) */
    E unlink(Node<E> x) { 
        final E element = x.item; // x是要删除的节点
        final Node<E> next = x.next; // x的前继节点
        final Node<E> prev = x.prev; // x的后继节点
        if (prev == null) { 
            first = next;
        } else { 
            prev.next = next;
            x.prev = null;
        }
        if (next == null) {  // 当x为尾节点时
            last = prev; // 那么x的前继节点就位尾节点
        } else { 
            next.prev = prev;
            x.next = null;
        }
        x.item = null;
        size--;
        modCount++;
        return element;
    }

## removeFirst() ##

/* * 删除首节点中的元素 */
    public E removeFirst() { 
        final Node<E> f = first;
        if (f == null)
            throw new NoSuchElementException();
        return unlinkFirst(f);
    }
        
    /* * 解链(删除首节点元素) */
    private E unlinkFirst(Node<E> f) { 
        // assert f == first && f != null;
        final E element = f.item;
        final Node<E> next = f.next;
        f.item = null;
        f.next = null; // help GC
        first = next;
        if (next == null)
            last = null;
        else
            next.prev = null;
        size--;
        modCount++;
        return element;
    }

## removeLast() ##

/* * 删除尾节点中的元素 */
    public E removeLast() { 
        final Node<E> l = last;
        if (l == null)
            throw new NoSuchElementException();
        return unlinkLast(l);
    }
        
    /* * 解链(删除尾节点元素) */
    private E unlinkLast(Node<E> l) { 
        // assert l == last && l != null;
        final E element = l.item;
        final Node<E> prev = l.prev;
        l.item = null;
        l.prev = null; // help GC
        last = prev;
        if (prev == null)
            first = null;
        else
            prev.next = null;
        size--;
        modCount++;
        return element;
    }

## pop() ##

/* * 底层是通过调用removeFirst()方法来删除首节点 */
    public E pop() { 
        return removeFirst();
    }

## get(int index) ##

/* * 获取执行下标index处的元素 */
    public E get(int index) { 
        checkElementIndex(index);
        return node(index).item;
    }
    
    /* * 判断元素下标index是否越界，并抛出异常信息 */
    private void checkElementIndex(int index) { 
        if (!isElementIndex(index))
            throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
    }
    
    /* * 判断元素下标index是否越界 */
    private boolean isElementIndex(int index) { 
        return index >= 0 && index < size;
    }
    
    /* * 拼接元素下标index越界时要抛出的异常信息 */
    private String outOfBoundsMsg(int index) { 
        return "Index: "+index+", Size: "+size;
    }
        
    /* * 获取在index处的节点 */
    Node<E> node(int index) { 
        if (index < (size >> 1)) {  // 判断index与size/2的大小，如果更大，则正向遍历
            Node<E> x = first;
            for (int i = 0; i < index; i++)
                x = x.next;
            return x;
        } else {  // 反向遍历
            Node<E> x = last;
            for (int i = size - 1; i > index; i--)
                x = x.prev;
            return x;
        }
    }

## getFirst() ##

/** * 获取首节点元素 */
    public E getFirst() { 
        final Node<E> f = first;
        if (f == null)
            throw new NoSuchElementException();
        return f.item;
    }

## getLast() ##

/** * 获取尾节点元素 */
    public E getLast() { 
        final Node<E> l = last;
        if (l == null)
            throw new NoSuchElementException();
        return l.item;
    }

## addFirst() ##

/** * 底层其实还是调用linkFirst(E e)方法来实现的 */
    public void addFirst(E e) { 
        linkFirst(e);
    }

## addLast() ##

/** * 底层其实还是调用linkLast(E e)方法来实现的 */
    public void addLast(E e) { 
        linkLast(e);
    }

## peek() ##

/** * 获取首节点元素，和getFirst()类似，区别在于，如果首节点为null，getFirst()将抛出NoSuchElementException异常，而peek()将返回null */
    public E peek() { 
        final Node<E> f = first;
        return (f == null) ? null : f.item;
    }

## peekFirst() ##

/** * 获取首节点元素，和peek()方法完全一样 */
    public E peekFirst() { 
        final Node<E> f = first;
        return (f == null) ? null : f.item;
    }

## peekLast() ##

/** * 获取尾节点元素，和getFirst()类似，区别在于，如果尾节点为null，getLast()将抛出NoSuchElementException异常，而peekLast()将返回null */
    public E peekLast() { 
        final Node<E> l = last;
        return (l == null) ? null : l.item;
    }

## poll() ##

/** * 获取首节点元素，并删除首节点元素，和removeFirst()类似，区别在于，如果首节点为null，removeFirst()将抛出NoSuchElementException异常，而poll()将返回null */
    public E poll() { 
        final Node<E> f = first;
        return (f == null) ? null : unlinkFirst(f);
    }

## pollFirst() ##

/** * 获取首节点元素，和poll()方法完全一样 */
    public E pollFirst() { 
        final Node<E> f = first;
        return (f == null) ? null : unlinkFirst(f);
    }

## pollLast() ##

/** * 获取尾节点元素，并删除首节点元素，和getFirst()类似，区别在于，如果尾节点为null，getLast()将抛出NoSuchElementException异常，而peekLast()将返回null */
    public E pollLast() { 
        final Node<E> l = last;
        return (l == null) ? null : unlinkLast(l);
    }

## linkFirst(E e) ##

/** * 添加元素到首节点 */
    private void linkFirst(E e) { 
        final Node<E> f = first;
        final Node<E> newNode = new Node<>(null, e, f);
        first = newNode;
        if (f == null)
            last = newNode;
        else
            f.prev = newNode;
        size++;
        modCount++;
    }

## linkLast(E e) ##

/** * 添加元素到尾节点 */
    void linkLast(E e) { 
        final Node<E> l = last;
        final Node<E> newNode = new Node<>(l, e, null);
        last = newNode;
        if (l == null)
            first = newNode;
        else
            l.next = newNode;
        size++;
        modCount++;
    }

## linkBefore(E e, Node<E> succ) ##

/** * 在指定节点前非null处添加元素到尾节点 */
    void linkBefore(E e, Node<E> succ) { 
        final Node<E> pred = succ.prev;
        final Node<E> newNode = new Node<>(pred, e, succ);
        succ.prev = newNode;
        if (pred == null)
            first = newNode;
        else
            pred.next = newNode;
        size++;
        modCount++;
    }

## unlinkFirst(Node<E> f) ##

/** * 删除首节点f */
    private E unlinkFirst(Node<E> f) { 
        final E element = f.item;
        final Node<E> next = f.next;
        f.item = null;
        f.next = null; // 将尾节点l中的引用置为null，下次GC来临之时会回收
        first = next;
        if (next == null)
            last = null;
        else
            next.prev = null;
        size--;
        modCount++;
        return element;
    }

## unlinkLast(Node<E> l) ##

/** * 删除尾节点l */
    private E unlinkLast(Node<E> l) { 
        final E element = l.item;
        final Node<E> prev = l.prev;
        l.item = null;
        l.prev = null; // 将尾节点l中的引用置为null，下次GC来临之时会回收
        last = prev;
        if (prev == null)
            first = null;
        else
            prev.next = null;
        size--;
        modCount++;
        return element;
    }

## unlink(Node<E> x) ##

/** * 删除指定节点 */
    E unlink(Node<E> x) { 
        final E element = x.item;
        final Node<E> next = x.next;
        final Node<E> prev = x.prev;
        if (prev == null) { 
            first = next;
        } else { 
            prev.next = next;
            x.prev = null;
        }
        if (next == null) { 
            last = prev;
        } else { 
            next.prev = prev;
            x.next = null;
        }
        x.item = null; // 将尾节点l中的引用置为null，下次GC来临之时会回收
        size--;
        modCount++;
        return element;
    }

## set(int index, E element) ##

/** * 在指定下标index处替换元素 */
    public E set(int index, E element) { 
        checkElementIndex(index);
        Node<E> x = node(index);
        E oldVal = x.item;
        x.item = element;
        return oldVal;
    }
    
    private void checkElementIndex(int index) { 
        if (!isElementIndex(index))
            throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
    }

## element() ##

/** * 底层通过调用getFirst()来获取首节点元素，和getFirst()是完全一样的 */
    public E element() { 
        return getFirst();
    }

## size() ##

/** * 直接返回链表的容量(长度) */
    public int size() { 
        return size;
    }

## clear ##

/** * 遍历链表，将所有的引用都置为null */
    public void clear() { 
        for (Node<E> x = first; x != null; ) { 
            Node<E> next = x.next;
            x.item = null;
            x.next = null;
            x.prev = null;
            x = next;
        }
        first = last = null;
        size = 0;
        modCount++;
    }

## clone() ##

/** * 克隆方法，改克隆为浅克隆，也就是复制对象的引用，并没有为元开辟新的空间去储存 */
    public Object clone() { 
        LinkedList<E> clone = superClone();
        clone.first = clone.last = null;
        clone.size = 0;
        clone.modCount = 0;
        for (Node<E> x = first; x != null; x = x.next) // 遍历LinkedList将元素添加到克隆的LinkedList中
            clone.add(x.item);
        return clone;
    }

## contains(Object o) ##

/** * 判断该LinkedList中是否保存此元素 */
    public boolean contains(Object o) { 
        return indexOf(o) != -1;
    }
    
    /** * 获取指定元素在LinkedList中的第一次出现的下标index，如果不存在返回-1 */
    public int indexOf(Object o) { 
        int index = 0;
        if (o == null) {  // 当指定元素为null时
            for (Node<E> x = first; x != null; x = x.next) { 
                if (x.item == null)
                    return index;
                index++;
            }
        } else {  // 当指定元素不为null时
            for (Node<E> x = first; x != null; x = x.next) { 
                if (o.equals(x.item))
                    return index;
                index++;
            }
        }
        return -1;
    }

## containsAll(Collection<?> c) ##

*  在`LinkedList`中是没有实现`containsAll(Collection<?> c)`方法的，它是通过继承了父类`AbstractSequentialList`的父类`AbstractList`的父类`AbstractCollection`中的`containsAll(Collection<?> c)`方法

/** * 判断LinkedList中是否包含指定集合中的元素 */
    public boolean containsAll(Collection<?> c) { 
        for (Object e : c)
            if (!contains(e))
                return false;
        return true;
    }
    
    /** * 获取指定元素在LinkedList中的下标index，存在返回true，不存在返回false */
    public boolean contains(Object o) { 
        Iterator<E> it = iterator();
        if (o==null) { 
            while (it.hasNext())
                if (it.next()==null)
                    return true;
        } else { 
            while (it.hasNext())
                if (o.equals(it.next()))
                    return true;
        }
        return false;
    }

## indexOf(Object o) ##

/** * 获取指定元素在LinkedList中的第一次出现的下标index，如果不存在返回-1 */
    public int indexOf(Object o) { 
        int index = 0;
        if (o == null) { 
            for (Node<E> x = first; x != null; x = x.next) { 
                if (x.item == null)
                    return index;
                index++;
            }
        } else { 
            for (Node<E> x = first; x != null; x = x.next) { 
                if (o.equals(x.item))
                    return index;
                index++;
            }
        }
        return -1;
    }

## lastIndexOf(Object o) ##

/** * 获取指定元素在LinkedList中的最后一次出现的下标index，如果不存在返回-1 */
    public int lastIndexOf(Object o) { 
        int index = size;
        if (o == null) { 
            for (Node<E> x = last; x != null; x = x.prev) { 
                index--;
                if (x.item == null)
                    return index;
            }
        } else { 
            for (Node<E> x = last; x != null; x = x.prev) { 
                index--;
                if (o.equals(x.item))
                    return index;
            }
        }
        return -1;
    }

## isEmpty ##

*  在`LinkedList`中是没有实现`isEmpty()`方法的，它是通过继承了父类`AbstractSequentialList`的父类`AbstractList`的父类`AbstractCollection`中的`isEmpty()`方法

/** * 是通过比较LinkedList实际容量与0比较大小 */
    public boolean isEmpty() { 
        return size() == 0;
    }

## retainAll(Collection<?> c) ##

*  在`LinkedList`中是没有实现`retainAll(Collection<?> c)`方法的，它是通过继承了父类`AbstractSequentialList`的父类`AbstractList`的父类`AbstractCollection`中的`retainAll(Collection<?> c)`方法

public boolean retainAll(Collection<?> c) { 
        Objects.requireNonNull(c);
        boolean modified = false;
        Iterator<E> it = iterator();
        while (it.hasNext()) { 
            if (!c.contains(it.next())) { 
                it.remove();
                modified = true;
            }
        }
        return modified;
    }

## iterator() ##

/* * 继承自LinkedList的父类AbstractSequentialList的iterator()方法 */
    public Iterator<E> iterator() { 
        return listIterator();
    }
    
    /* * 继承自LinkedList的父类AbstractSequentialList的父类AbstractList中的listIterator()方法 */
    public ListIterator<E> listIterator() { 
        return listIterator(0);
    }
    
    /* * 这是AbstractList中的方法 */
    public ListIterator<E> listIterator(final int index) { 
        rangeCheckForAdd(index);
        return new ListItr(index);
    }
    
    /* * 这是AbstractList中的方法，用于检测下标index是否越界 */
    private void rangeCheckForAdd(int index) { 
        if (index < 0 || index > size())
            throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
    }
    
    /* * 这是AbstractList中的方法，继承了Itr内部类，实现了ListIterator迭代器接口 */
    private class ListItr extends Itr implements ListIterator<E> { 
        ListItr(int index) { 
            cursor = index;
        }
    
        public boolean hasPrevious() { 
            return cursor != 0;
        }
    
        public E previous() { 
            checkForComodification();
            try { 
                int i = cursor - 1;
                E previous = get(i);
                lastRet = cursor = i;
                return previous;
            } catch (IndexOutOfBoundsException e) { 
                checkForComodification();
                throw new NoSuchElementException();
            }
        }
    
        public int nextIndex() { 
            return cursor;
        }
    
        public int previousIndex() { 
            return cursor-1;
        }
    
        public void set(E e) { 
            if (lastRet < 0)
                throw new IllegalStateException();
            checkForComodification();
    
            try { 
                AbstractList.this.set(lastRet, e);
                expectedModCount = modCount;
            } catch (IndexOutOfBoundsException ex) { 
                throw new ConcurrentModificationException();
            }
        }
    
        public void add(E e) { 
            checkForComodification();
    
            try { 
                int i = cursor;
                AbstractList.this.add(i, e);
                lastRet = -1;
                cursor = i + 1;
                expectedModCount = modCount;
            } catch (IndexOutOfBoundsException ex) { 
                throw new ConcurrentModificationException();
            }
        }
    }
    
    /* * 这是AbstractList中的方法，实现了Iterator迭代器接口 */
    private class Itr implements Iterator<E> { 
        int cursor = 0;
        int lastRet = -1;
        int expectedModCount = modCount;
    
        public boolean hasNext() { 
            return cursor != size();
        }
    
        public E next() { 
            checkForComodification();
            try { 
                int i = cursor;
                E next = get(i);
                lastRet = i;
                cursor = i + 1;
                return next;
            } catch (IndexOutOfBoundsException e) { 
                checkForComodification();
                throw new NoSuchElementException();
            }
        }
    
        public void remove() { 
            if (lastRet < 0)
                throw new IllegalStateException();
            checkForComodification();
    
            try { 
                AbstractList.this.remove(lastRet);
                if (lastRet < cursor)
                    cursor--;
                lastRet = -1;
                expectedModCount = modCount;
            } catch (IndexOutOfBoundsException e) { 
                throw new ConcurrentModificationException();
            }
        }
    
        final void checkForComodification() { 
            if (modCount != expectedModCount)
                throw new ConcurrentModificationException();
        }
    }

## listIterator() ##

/* * 可以和iterator()比较发现，其实iterator()方法就是调用listIterator()来实现迭代器的 */
    public ListIterator<E> listIterator() { 
        return listIterator(0);
    }

# 总结 #

*  LinkedList底层是一个双向链表
 *  因为LinkedList底层是一个链表，所以它增删元素快(只需要在相应节点上增删节点就行)，查询元素慢(因为查询元素必须前一个节点或者后一个节点才能找到，时间复杂度是O(n))
 *  迭代器方法iterator()和listIterator()在实现上是完全一样的，都是通过实现了ListItr内部类返回内部类的一个实例
 *  LinkedList迭代器既可以正向遍历，也可以逆向遍历(LinkedList底层是双向链表，可以通过后继节点找到前一个节点)