概述

先看代码

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

• 实现了List接口，是一个长度可变的集合，提供了增删改查的功能。
• 实现了栈和队列的操作方法，因此也可以作为栈、队列和双端队列来使用
• 实现了Serializable接口，说明ArrayList可以被序列化。
• 实现了Cloneable接口，可以被复制。
• 允许元素为null，允许重复元素
• 非线程安全

对于随机访问集合类一般建议继承AbstractList而不是AbstractSequentialList

底层实现原理

实现

LinkedList是双向链表实现的List，此链表上的每个节点包含三部分，前指针、数据、后指针。最后一个节点的后指针指向第一个节点的前指针，形成一个循环。
在这里没有所谓的哑元，当链表为空的时候first和last都指向null。

特点

查询慢、增删快

容量

不存在容量不足的问题，没有扩容方法

添加元素

add()

不指定位置添加新元素add(E e)

使用的尾插法
（与头插法相比不会影响效率，因为链表中已经存储了尾部节点last，所以不需要从头开始遍历去寻找尾部节点）

在指定位置插入元素add(int index,E e)

add(int index,E e),当index==size时，等同于add(E e);如果不是，则需要分为两步：

• 根据index找到要插入的位置，即node(index)方法；
• 修改引用，完成插入操作

addAll()

？？

查找元素

LinkedList 查找过程需要从链表头结点（或尾节点）向后查找，时间复杂度为 O(N)。
即通过比较 index 与节点数量 size/2 的大小，决定从头结点还是尾节点进行查找。