LinkedList的源码查看

结构源码

LinkedList是一个双向链表，因为它具有next和prev的前后引用。所以每次添加元素，移除元素时，需要考虑两个指针的引用情况，保证对前一个元素的完全断开和新元素的完全引用，如果在指定位置上连接元素的过程和结构可以参考下图：

依赖结构

/* LinkedList的内部变量 可以看出LinkedList其实就是一个链表 */
transient int size = 0;

/**
 * 指向首节点
 * Invariant: (first == null && last == null) ||
 *            (first.prev == null && first.item != null)
 */
transient Node<E> first;

/**
 * 指向尾节点
 * Invariant: (first == null && last == null) ||
 *            (last.next == null && last.item != null)
 */
transient Node<E> last;

/* 内部node实现 */
    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构造函数

/* 空构造函数 比较常用 */
public LinkedList() {
   }

/* 有collection参数的构造函数 */
public LinkedList(Collection<? extends E> c) {
    this();
    addAll(c);
}

public boolean addAll(Collection<? extends E> c) {
    return addAll(size, c);
}
/* 参数：当前数量也就是要得到当前链表的位置 */
public boolean addAll(int index, Collection<? extends E> c) {
    checkPositionIndex(index);

    Object[] a = c.toArray();
    int numNew = a.length;
    if (numNew == 0)
        return false;
    Node<E> pred, succ;
    // 对插入前情况的判断
    if (index == size) {
//          如果在尾部插入 pred=最后一个节点
        succ = null;
        pred = last;
    } else {
//          否则在中部插入 succ=当前节点 pred=前一节点
/* - - - - - - - - -  */
/*     ^ ^ */
/*     1 2  如果想在2位置插入元素，前一个元素不动，将后面的元素后移*/
        succ = node(index);
        pred = succ.prev;
    }
    for (Object o : a) {
        @SuppressWarnings("unchecked") E e = (E) o;
// 构造方法 前节点/内容/后节点 始终pred是前置节点
        Node<E> newNode = new Node<>(pred, e, null);
        if (pred == null)
// 如果pred==null 说明 本身列表开始就是空的或者在开头插入元素
            first = newNode;
        else
// 否则在后面插入newNode
            pred.next = newNode;
// 向后循环节点
        pred = newNode;
    }
// 如果succ==null 说明到最后一个节点后位置 
// 将最后的新插入的元素pred赋值给last
    if (succ == null) {
        last = pred;
    } else {
      /* 否则插入在succ前 */
        pred.next = succ;
        succ.prev = pred;
    }

    size += numNew;
    modCount++;
    return true;
}

基本方法

添加

/* add方法默认调用linklast方法，也就是向后添加元素 */
public boolean add(E e) {
    linkLast(e);
    return true;
}

/* 同样有addLast 达到相同的目的，就是不返回任何东西 */
public void addLast(E e) {
        linkLast(e);
    }

使用add方法后会默认的调用 linkLast 后将元素添加至List的末尾。

void linkLast(E e) {
    final Node<E> l = last;
    /* 获得最后一个元素当作新节点的前置节点 */
    final Node<E> newNode = new Node<>(l, e, null);
    /* 把当前节点付给last */
    last = newNode;
    if (l == null)
        first = newNode;
    else
    // 将last的next指向新节点,完成双方相互链接
        l.next = newNode;
    size++;
    modCount++;
}

当然也可以调用方法在最前面添加元素

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

移除

remove方法

public E remove(int index) {
  /* 先判断是否越界 */
      checkElementIndex(index);
      return unlink(node(index));
  }

E unlink(Node<E> x) {
    // assert x != null;
    final E element = x.item;
    final Node<E> next = x.next;
    final Node<E> prev = x.prev;
/* 如果prev是空 说明当前元素是第一个元素 如 A B C 移除A，直接将B指向首节点即可 */
    if (prev == null) {
        first = next;
    } else {
      /* 当前节点与前后节点断绝链接 如ABC移除B，则需要将A.next指向C，B.pre指向空 */
        prev.next = next;
        x.prev = null;
    }
    // 因为LinkedList为双向链表，需要取消next和prev
/* 如果是最后一个元素 */
    if (next == null) {
        last = prev;
    } else {
      /* 当前节点与前后节点断绝链接 因为LinkedList是双向链表 */
        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 和removeFirst同理

赋值取值操作

get方法

public E get(int index) {
    checkElementIndex(index);
    /* 得到index处节点的item信息 */
    return node(index).item;
}

Node<E> node(int index) {
        // assert isElementIndex(index);
        // 分两个方向查找，1.如果给定的index小于size的一半
    if (index < (size >> 1)) {
        Node<E> x = first;
        //从头开始
        for (int i = 0; i < index; i++)
            x = x.next;
            // 返回最后一个
        return x;
    } else {
    // 2.如果给定的index大于size的一半
        Node<E> x = last;
        // 从尾部开始找
        for (int i = size - 1; i > index; i--)
            x = x.prev;
            //返回最后的那个
        return x;
    }
}

set方法

public E set(int index, E element) {
    checkElementIndex(index);
    Node<E> x = node(index);
    E oldVal = x.item;
    x.item = element;
    /* set方法会返回原来的值 */
    return oldVal;
}

LinkedList中的栈操作

peek方法

/**
 * Retrieves, but does not remove, the head (first element) of this list.
 * 只是检索栈首元素，但并不弹出
 * @return the head of this list, or {@code null} if this list is empty
 * @since 1.5
 */
public E peek() {
    final Node<E> f = first;
    return (f == null) ? null : f.item;
}

同理 peekFirst 和 peekLast

poll方法

/**
 * Retrieves and removes the head (first element) of this list.
 * 检索并且移除栈首元素 unlinkFirst是可以返回移除元素的
 * @return the head of this list, or {@code null} if this list is empty
 * @since 1.5
 */
public E poll() {
    final Node<E> f = first;
    return (f == null) ? null : unlinkFirst(f);
}

同理 pollFirst 和 pollLast

push方法

/**
 * Pushes an element onto the stack represented by this list.  In other
 * words, inserts the element at the front of this list.
 * 在栈首堆一个元素
 * <p>This method is equivalent to {@link #addFirst}.
 *
 * @param e the element to push
 * @since 1.6
 */
public void push(E e) {
    addFirst(e);
}

pop方法

/**
 * Pops an element from the stack represented by this list.  In other
 * words, removes and returns the first element of this list.
 * 出栈
 * <p>This method is equivalent to {@link #removeFirst()}.
 *
 * @return the element at the front of this list (which is the top
 *         of the stack represented by this list)
 * @throws NoSuchElementException if this list is empty
 * @since 1.6
 */
public E pop() {
    return removeFirst();
}

offer方法

实际上 offer 是调用的 add 方法，但是区别就在 linkedlist 继承了 Dequ 和 List 父类。一般当 queue 用的时候要用 offer/push/pop 而当使用 list 的时候用 add/remove 。

总结

通过查看LinkedList的源码可以发现：

1. 首先可以确定LinkedLIst是一个通过Node结构实现的双向链表
2. 其次通过add和remove方法可以看出它不向ArrayList一样，需要对容量进行扩容操作，而是通过‘指针’指向前后节点实现的‘连接’。
3. 然后通过get方法可以看出查找一个特定位置上的非常麻烦，需要遍历List，尽管使用了二分的方式进行了优化，但是查找性能依旧不能和ArrayList相比。