LinkedList源码分析

前言

public class LinkedList<E>
    extends AbstractSequentialList<E>
    implements List<E>, Deque<E>, Cloneable, java.io.Serializable

和ArrayList相比，LinkedList多了AbstractSequentialList类和Deque接口。

其中Deque又是继承自Queue，所以LinkedList可以当做队列或者双端队列。

其中AbstractSequentialList的作用可以当做是RandomAccess的对照来看。

关于RandomAccess，可以看看ArrayList源码。

底层结构

LinkedList每个节点都是一个Node类，Node中有next和prev。可以看到实现的是双端队列。

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

基本的成员变量，保存了链表的头部和尾部

transient Node<E> first;
transient Node<E> last;
transient int size = 0;

基本操作

get方法

public E get(int index) {
        checkElementIndex(index);
        return node(index).item;
    }

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

get方法调用了node方法，node方法是找到index位的元素。
这个方法还是很有意思的，他先判断index是在前半段还是后半段，前半段就从first节点开始找，后半段就从last节点开始找。

remove方法

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

因为LinkedList支持存null，所以在remove的时候要分两种情况讨论。

迭代

Iterator

Iterator方法是在AbstractSequentialList中

public Iterator<E> iterator() {
        return listIterator();
    }

LinkedList中重写了listIterator方法。

public ListIterator<E> listIterator(int index) {
        checkPositionIndex(index);
        return new ListItr(index);
    }

ListLtr是LinkedList中的一个类

private class ListItr implements ListIterator<E>

ListIterator

public ListIterator<E> listIterator(int index) {
        checkPositionIndex(index);
        return new ListItr(index);
    }

可以看到，其实和Iterator方法的实现是一样的。