1. LinkedList的继承与实现

LinkedList继承了AbstractSequentialList，实现了List、Cloneable、Serializable接口
LinkedList 源码分析面试题 - 图1

2. 源码分析

2.1. 成员变量与成员方法与静态内部类

2.1.1. 成员变量

transient int size = 0;
//指向第一个节点
transient Node<E> first;
//指向最后一个节点
transient Node<E> last;

2.1.2. 非公有成员方法

linkLast(E e) ：将传入的元素包装成Node节点，并添加到链表的最后。
node(int index)：找到链表中索引为index的节点并返回。
linkBefore(E e , Node succ)：将e包装成Node节点并插入到 Node succ所在位置，使succ成为e的next。

void linkLast(E e) {
    final Node<E> l = last;
    final Node<E> newNode = new Node<>(l, e, null);
    last = newNode;
    if (l == null)
        first = newNode;
    else
        l.next = newNode;
    size++;
    modCount++;
}
Node<E> node(int index) {
    // 如果 index比 size/2小则从前遍历找到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;
    }
}
//传入待插入元素e 和 待插入位置上的Node
void linkBefore(E e, Node<E> succ) {
    // assert succ != null;
    final Node<E> pred = succ.prev;
    final Node<E> newNode = new Node<>(pred, e, succ);
    succ.prev = newNode;
    if (pred == null)
        first = newNode;
    else
        pred.next = newNode;
    size++;
    modCount++;
}

2.1.3. 静态内部类

Node类对象包装每一个传入的元素，并构成LinkedList双向链表中的节点。

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

2.2. 构造方法

1.空参构造
2.有参构造——传入另一个Collection实现类

public LinkedList() {}

public LinkedList(Collection<? extends E> c) {
    this();
    addAll(c);
}

2.3. add

2.3.1. add(Integer e) 添加（尾插，返回true/false）

将传入的元素包装成Node对象，向链表的末尾添加该Node对象。

public boolean add(E e) {
    linkLast(e);
    return true;
}

2.3.2. add(int index, Integer element) 指定位置插入（无返回值）

将传入的元素包装成Node对象，向指定位置插入该Node对象。

public void add(int index, E element) {
    //确认 0 <=  index <= size
    checkPositionIndex(index);

    //如果是在末尾插入
    if (index == size)
        linkLast(element);
    else//如果是在中间插入
        linkBefore(element, node(index));
}

2.3.3. addFirst(Integer e) 头插

2.3.4. addLast(Integer e) 尾插无返回值

2.4. remove

这部分源码太简单了，就是双向链表的删除

2.4.1. remove() = removeFirst()

2.4.2. removeFirst() 删除链表第一个元素

2.4.3. removeLast() 删除链表最后一个元素

2.4.4. remove(int index) 删除指定位置元素

2.4.5. remove(Object o) 删除指定元素

2.5. get

这部分源码太简单了，就是查找节点

2.5.1. get(int index)

2.5.2. getFirst()

2.5.3. getLast()

2.6. set(int index , E element)

3. 面试题

3.0. LinkedList的数据结构是如何实现的

**。
特性：
在头尾添加元素的时间复杂度是O(1);
涉及到查找节点的操作时间复杂度为O(n);

3.1. LinkedList的增删改查

● 链表批量增加，是靠for循环遍历原数组，依次执行插入节点操作。对比ArrayList是通过System.arraycopy完成批量增加的。增加一定会修改modCount。
● 查找node：通过下标获取某个node 的时候会判断index处于size的前半段还是后半段，然后从头或从尾进行遍历，以提高查询效率
● 删：会修改modCount。按下标删，也是先根据index找到Node，然后去链表上unlink掉这个Node。按元素删，会先去遍历链表寻找是否有该Node，如果有，去链表上unlink掉这个Node。
● 改：先根据index找到Node，然后替换值。改不修改modCount。
● 它的CRUD操作里，都涉及到根据index去找到Node的操作（ node(int index) ）。

3.2. add(E e) 与 offer(E e)的区别

JDK1.8中，offer(E e) 的方法体直接返回了一个 add(e)，所以两者没有区别。只是在作为队列的时候添加元素没有一个统一的命名方式，有些用add，有些用offer，所以就保留了几个相同功能但不同名的方法。

LinkedList 源码分析 面试题