1. 简介

1.1 同 ArrayList 区别是什么？

• ArrayList
  • 优点：底层是数组，检索非常快
  • 缺点：底层是数组，所以扩容需要申请新的数组并且要把老数据拷贝到新数组，代价比较大
• LinkedList
  • 优点：进行增删改仅需要改变两个节点的指针引用即可，较快
  • 缺点：底层是链表，通过下标寻找元素，需要从链表头开始一个节点一个节点往下寻找，检索比较慢

1.2 继承关系

相较于 ArrayList ，LinkedList 多实现了接口 Queue （队列）、Deque （双端队列）。

队列的含义是先进先出，双端队列顾名思义就是可以把队列的首尾都当作队列处理，也就是首尾都可以增删元素，说明 LinkedList 除了队列先进先出的能力还具有栈先进后出的能力。

2. LinkedList 方法

2.1 构造方法

构造器	描述
LinkedList()	构造一个空列表。
LinkedList​(Collection<? extends E> c)	按照集合的迭代器返回的顺序构造一个包含指定集合元素的列表。

2.2 具体方法

变量和类型	方法	方法来源	操作	位置	列表内为空处理
void	add​(int index, E element)	List	增	指定位置
boolean	add​(E e)	Queue	增	末尾
void	addFirst​(E e)	Deque	增	开头
void	addLast​(E e)	Deque	增	末尾
void	clear()	Collection	删	所有位置
Iterator<E>	descendingIterator()	Deque	迭代
E	element()	Queue	检索	开头
E	get​(int index)	List	检索	指定位置
E	getFirst()	Deque	检索	开头
E	getLast()	Deque	检索	末尾
boolean	offer​(E e)	Queue	增	末尾
boolean	offerFirst​(E e)	Deque	增	开头
boolean	offerLast​(E e)	Deque	增	末尾
E	peek()	Queue	检索	开头
E	peekFirst()	Deque	检索	开头
E	peekLast()	Deque	检索	末尾
E	poll()	Queue	检索，删	开头	返回 null
E	pollFirst()	Deque	检索，删	开头	返回 null
E	pollLast()	Deque	检索，删	末尾	返回 null
E	pop()	Deque	检索，删	开头	异常
void	push​(E e)	Deque	增	末尾
E	remove()	Queue	检索	开头	异常
E	remove​(int index)	List	检索，删	指定位置	异常
boolean	remove​(Object o)	List	检索，删	第一个匹配项	异常
E	removeFirst()	Deque	检索，删	开头	异常
boolean	removeFirstOccurrence​(Object o)	Deque	删	第一个匹配项	异常
E	removeLast()	Deque	检索，删	末尾	异常
boolean	removeLastOccurrence​(Object o)	Deque	删	最后一个匹配项	异常
E	set​(int index, E element)	List	设置	指定位置

2.3 重点方法原理讲解

add​(int index, E element)

LinkedList 中的每一个节点都有两个指针 next（指向下一个节点），prev（指向上一个节点）。 如上图，如果想要用 NEW 2 把 2 替代，需要做的工作如下：

• 将 2 的 next 指针与 prev 指针指向 null，此时 2 便不会被引用，也不会引用其他节点
• 将 NEW 2 的 next 指针指向 3，prev 指针指向 1
• 将 1 的 next 指针指向 NEW 2
• 将 3 的 prev 指针指向 NEW 2
• 注意，如果替换的节点是 Head 节点/ Tail 节点，还需要改变两个指针的指向引用

remove​(int index)

如上图，如果需要删除一个节点，需要做的工作如下：

• 将 2 的 next 指针与 prev 指针指向 null，此时 2 便不会被引用，也不会引用其他节点
• 将 1 的 next 指针指向 3
• 将 3 的 prev 指针指向 1
• 注意，如果删除的节点是 Head 节点/ Tail 节点，还需要改变两个指针的指向引用

3. 总结

对于查操作较多的场景用 ArrayList 性能更好，可以直接获取到内存中的地址，不用遍历。

对于增删操作多的场景用 LinkedList ，只需要改变指针指向即可，不需要进行扩容拷贝。

LinkedList 具有队列和栈的能力，有相关需求在使用时可以考虑这两个特性。

小贴士：可以用 LinkedList 的队列特性对树结构进行广度优先搜索

class TreeNode {
    private int val;
    private TreeNode left;
    private TreeNode right;
}

public static void main(String[] args) {
    TreeNode root;

    LinkedList<TreeNode> queue = new LinkedList<>();
    queue.add(root);

    while (!queue.isEmpty()) {
        for (int i = queue.size() - 1 /*拷贝队列当前元素数量*/; i >= 0; i--) {
            TreeNode treeNode = queue.poll();
            TreeNode left = treeNode.left;
            TreeNode right = treeNode.right;

            System.out.println(treeNode.val);

            if (left != null) {
                queue.offer(left);
            }
            if (right != null) {
                queue.offer(right);
            }
        }
    }
}