JDK源码 LinkedList

1.初始化一个空的节点header：

private transient Entry<E> header = new Entry<E>(null, null, null);

该节点在《算法导论》里应该叫“哨兵节点”。

2.初始化一个空的LinkedList，即设置header节点的前后节点都是空。

    /**

     * Constructs an empty list.

     */

    public LinkedList() {

        header.next = header.previous = header;

    }

3.Entry的构造方法：

private static class Entry<E> {

      E element;

      Entry<E> next;

      Entry<E> previous;

      Entry(E element, Entry<E> next, Entry<E> previous) {

          this.element = element;

          this.next = next;

          this.previous = previous;

      }

    }

包含节点的数据element，指向下一个节点的next，和指向前一个节点的previous.

4.主要的api包含删除元素，添加元素等，有许多重载方法。

1）删除LinkedList中的一个节点对象，主要是从头往后遍历节点，找到即删除之。

关于该删除操作的时间复杂度讨论，引用博文：LinkedList的局限。

    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;

    }

2）删除指定位置的节点。

    public E remove(int index) {

        return remove(entry(index));

    }

首先根据索引index去查找节点

    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;

    }

这里的技巧是，先判断index在LinkedList中是前半部分还是后半部分，如果前半部分就从头往后遍历，反之从后往前遍历，可以这么做的原因是该LinkedList是双向链表。

接下来的删除节点就比较简单了。

    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;

    }

先保存节点的数据E result = e.element;最后返回。

主要的操作是，让该节点的前一节点指向该节点的后一节点；

让该节点的后一节点的前一节点指向该节点的前一节点；

然后将该节点的前后节点置为空，节点数据也置为空；

链表的节点数减一，链表的修改次数加一。

返回之前保存的节点数据，删除操作结束。

3）在指定的位置index插入一个集合Collection c。

   主要是将集合c转换为数组，遍历数组元素；

   如果正好是在最后的位置(即index==size)插入，那么直接在header前面插入即可，因为LinkedList是一个双向链表。

   否则，那么在指定的index之前插入，然后遍历集合数组，依次在此插入各个元素。

    public boolean addAll(int index, Collection<? extends E> c) {

        if (index < 0 || index > size)

            throw new IndexOutOfBoundsException("Index: "+index+

                                                ", Size: "+size);

        Object[] a = c.toArray();

        int numNew = a.length;

        if (numNew==0)

            return false;

      modCount++;

        Entry<E> successor = (index==size ? header : entry(index));

        Entry<E> predecessor = successor.previous;

      for (int i=0; i<numNew; i++) {

            Entry<E> e = new Entry<E>((E)a[i], successor, predecessor);

            predecessor.next = e;

            predecessor = e;

        }

        successor.previous = predecessor;

        size += numNew;

        return true;

    }

 4）clear()方法，删除所有的节点

遍历该LinkedList，设置每个节点的前后节点及element为null

最后设置header前点的前后节点为null

    public void clear() {

        Entry<E> e = header.next;

        while (e != header) {

            Entry<E> next = e.next;

            e.next = e.previous = null;

            e.element = null;

            e = next;

        }

        header.next = header.previous = header;

        size = 0;

      modCount++;

    }

就列举这么多吧。