Java 源码 - LinkedList 集合类

介绍

Doubly-linked list implementation of the List and Deque interfaces. Implements all optional list operations, and permits all elements including null.

示例

public class App {
  public static void main(String[] args) {
    LinkedList list = new LinkedList();
    list.add("费");
    list.add("哥");
    list.forEach(System.out::print);
  }
}

结构

源码

成员变量

/**
 * Pointer to first node.
 */
transient Node first;

/**
 * Pointer to last node.
 */
transient Node last;

构造方法

/**
 * Constructs an empty list.
 */
public LinkedList() { }

成员方法

添加

/**
 * Links e as last element.
 */
void linkLast(E e) {
    final Node l = last;
    final Node newNode = new Node<>(l, e, null);
    last = newNode;
    if (l == null)
        first = newNode;
    else
        l.next = newNode;
    size++;
    modCount++;
}

刪除

/**
 * Unlinks non-null node x.
 */
E unlink(Node x) {
    // assert x != null;
    final E element = x.item;
    final Node next = x.next;
    final Node 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;
}

面试

它与 ArrayList 的区别？
1、一个是动态数组的数据结构，一个是链表的数据结构，都是对 List 接口的实现。
2、随机访问 ArrayList 的效率高，它底层数组支持随机访问，LinkedList 需要移动指针从前往后依次查找。
3、增删的操作 LinkedList 的效率更高，它修改一些指针的方向即可，ArrayList 需要进行数据的移动。
如何实现 LinkedList 线程安全？
1、使用 Collections.synchronizedList 包装一下 List，内部使用了 synchronized (mutex) 修饰方法体。
2、使用 ConcurrentLinkedQueue 集合类，内部使用 CAS算法。