LinkedList源码个人解读

LinkedList的基本结构是双向链接的直线结构。

链表的构造函数有两个，其中空构造函数什么都没做，就是一个空实现。

    /**

     * Constructs an empty list.

     */

    public LinkedList() {

    }

    /**

     * Constructs a list containing the elements of the specified

     * collection, in the order they are returned by the collection's

     * iterator.

     *

     * @param  c the collection whose elements are to be placed into this list

     * @throws NullPointerException if the specified collection is null

     */

    public LinkedList(Collection<? extends E> c) {

        this();

        addAll(c);

    }

另外就是Node的组成

  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;

        }

    }

可以发现顺序是前驱，值，后继。

继续使用断点调试的方法阅读源码

 LinkedList linkedList = new LinkedList();

        linkedList.add(1);

目前还是空链表，我们准备加1.

public boolean add(E e) {

        linkLast(e);

        return true;

    }

继续跳转到linkLast（e）中

    /**

     * Links e as last element.

     */

    void linkLast(E e) {

        final Node<E> l = last;

        final Node<E> newNode = new Node<>(l, e, null);

        last = newNode;//last指向newNode

        if (l == null)//因为刚开始的last就是空，也就是一开始就是空链表

            first = newNode;那么first也指向newNode

        else

            l.next = newNode;

        size++;

        modCount++;

    }

首先last指向l，l此时为null，而l也指向了这个null。newNode为前驱和后继均为null，值为1的节点，。那么此时头节点就是当前节点就是尾节点。要不然的话，我们在执行

  linkedList.add(2);

此时再到

void linkLast(E e) {

        final Node<E> l = last;//此时last指向的是值为1的节点，也是链表的尾节点

        final Node<E> newNode = new Node<>(l, e, null);//创造新的节点，新节点的前驱是原先的尾戒点，

        last = newNode;//然后将last指向新的节点，也就是后移last。

        if (l == null)

            first = newNode;

        else//此时l不为空

            l.next = newNode;//所以l的下一个连上新的节点，这样就加入成功了

        size++;

        modCount++;

    }

LinkedList的get()方法，下标是从0开始算的

public E get(int index) {

        checkElementIndex(index);

        return node(index).item;

    }

首先越界检查，然后跳到node()方法。

    /**

     * Returns the (non-null) Node at the specified element index.

     */

    Node<E> node(int index) {

        // assert isElementIndex(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;

        }

    }

这段代码就很有意思，我们都知道链表增删都很快，但是查询较慢。此处的查询做了优化。也就是说如果索引小于链表长度的一半，那么就从头开始找。反之从后找。这样就提高了效率。

接下来就是add(int index, E element)方法。进断点调试

LinkedList linkedList = new LinkedList();

        linkedList.add(1);

        linkedList.add(2);

        linkedList.add(3);

        linkedList.add(4);

        linkedList.add(5);

        linkedList.add(3,9);

 public void add(int index, E element) {

        checkPositionIndex(index);

        if (index == size)

            linkLast(element);

        else

            linkBefore(element, node(index));

    }

可以看到首先是越界检查。然后是判断是否是直接插入队尾。如果是插入队尾。如果不是，则先node(idnex)查询出索引处的节点。然后再进入到linkBefore

    void linkBefore(E e, Node<E> succ) {此时succ为插入处的节点，也就是值为4的节点。e值为9

        // assert succ != null;

        final Node<E> pred = succ.prev;//保存4的前驱，

        final Node<E> newNode = new Node<>(pred, e, succ);//此时新的节点的前驱要为4的前驱，后继为4.

        succ.prev = newNode;//此时再连上4之后的节点，也就是4的前驱是新节点。

        if (pred == null)//这里是链接3的后继。如果4的前驱是空，那么就是在对头插入数据，那么first就是新的节点

            first = newNode;

        else//否则，3的next就是新的节点，此时就全部连上了

            pred.next = newNode;

        size++;

        modCount++;

    }

接下来就是remove（），默认删除第一个节点。

public E remove() {

        return 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;

    }

首先是保存first。存储头节点的后续节点next。然后令头节点值为空，头节点断开。再移动first到next。如果只有头节点，那么last也为空，此时链表为空。如果不是，则next的前驱为null，那么就删除了头节点了。

接下来是remove(int index)方法。

  public E remove(int index) {

        checkElementIndex(index);

        return unlink(node(index));

    }

一样，先检查越界，然后查找索引处的节点，再到unlink函数中

E unlink(Node<E> x) {//此时x为值为3的节点

        // assert x != null;

        final E element = x.item;//保存删除的节点的值用于返回

        final Node<E> next = x.next;//保存当前节点的后续节点

        final Node<E> prev = x.prev;//保存当前节点的前驱节点

        if (prev == null) {//如果前驱节点为空

            first = next;//那么就代表删除的是头节点，所以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;

    }

由于调试是

 LinkedList linkedList = new LinkedList();

        linkedList.add(1);

        linkedList.add(2);

        linkedList.add(3);

        linkedList.add(4);

        linkedList.add(5);

        linkedList.add(3,9);

        linkedList.get(3);

      //  linkedList.remove();//默认删除第一个节点

        linkedList.remove(2);//删除第二个节点

所以上述unlink中的注释就可以看懂了

接下来将indexof（Object o）

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;

    }

这就是查找节点对象的索引，如果没找到就返回-1.

最后将clear()函数。

 public void clear() {

        // Clearing all of the links between nodes is "unnecessary", but:

        // - helps a generational GC if the discarded nodes inhabit

        //   more than one generation

        // - is sure to free memory even if there is a reachable Iterator

        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++;

    }

循环依次断开每个头节点。然后fist和last都指向null，大小为0.

总结：1.LinkedList是非线程安全的

2.他的删除增加效率很高，但是查询较慢。

巴特西

LinkedList源码个人解读

最新文章

热门文章