LinkedList有以下几个特性：
- LinkedList实现了List接口的同时，还实现了Deque接口，所以LinkedList也可以当双端队列使用；
- LinkedList底层实现是双向链表，优点是删除或添加元素的效率高（时间复杂度是O(1)），查询效率低（时间复杂度为O(n)）；
- LinkedList虽然实现了随机访问，但是效率低效，不建议使用；
- 由于LinkedList底层是链表，不存在容量不足的问题，因此不像ArrayList一样还需要动态扩容机制；
- LinkedList允许元素为null，且允许重复元素；
- LinkedList是线程不安全的。
日常开发中如果需要用到队列或者栈这些数据结构时，建议使用LinkedList作为实现类。
1、常用API
1.1 常用API概览
***************************** 插入元素 *****************************// 将指定元素添加到链表末尾public boolean add(E e);// 将指定元素插入到链表的指定位置public void add(int index, E element);// 将指定元素插入到链表头public void addFirst(E e);// 将指定元素添加到链表的末尾public void addLast(E e);// 将指定集合中的所有元素添加到链表末尾public boolean addAll(Collection<? extends E> c);// 将指定集合中的所有元素从指定位置开始插入链表public boolean addAll(int index, Collection<? extends E> c);// 将指定元素添加到链表末尾（对应Queue里的offer）public boolean offer(E e);// 将指定元素添加到链表头public boolean offerFirst(E e);// 将指定元素添加到链表末尾public boolean offerLast(E e);// 将指定元素添加到链表头（对应Stack里的push）public void push(E e);***************************** 删除元素 *****************************// 移除链表中的所有元素public void clear();// 移除链表的第一个元素，并返回该元素public E remove();// 移除链表中指定位置处的元素，并返回该元素public E remove(int index);// 若元素存在则从链表中该元素第一次出现的位置移除该元素public boolean remove(Object o);// 移除链表的第一个元素，并返回该元素public E removeFirst();// 移除链表最后一个元素，并返回该元素public E removeLast();// 从链表中移除指定元素第一次出现位置处的元素（以正序遍历）public boolean removeFirstOccurrence(Object o);// 链表中移除指定元素最后一次出现位置处的元素（以正序遍历）public boolean removeLastOccurrence(Object o);// 移除链表的第一个元素并返回（对应Queue里的poll）public E poll();// 移除链表的第一个元素并返回public E pollFirst();// 移除链表的最后一个元素并返回public E pollLast();// 移除链表的第一个元素并返回（对应Stack里的pop）public E pop();***************************** 查找元素 *****************************// 判断链表中是否存在指定元素public boolean contains(Object o);// 返回链表中指定位置的元素public E get(int index);// 返回链表的第一个元素public E getFirst();// 返回链表的最后一个元素public E getLast();// 返回指定元素在链表中第一次出现的位置，若未找到则返回-1public int indexOf(Object o);// 返回指定元素在链表中最后一次出现的位置，若未找到则返回-1public int lastIndexOf(Object o);// 返回链表的第一个元素，不做删除（对应Stack里的peek）public E peek();// 返回链表的第一个元素，不做删除public E peekFirst();// 返回链表的最后一个元素，不做删除public E peekLast();// 返回链表的第一个元素（对应Queue里的element）public E element();***************************** 修改元素 *****************************// 链表中指定位置处的元素修改为指定的元素，返回被替换的元素public E set(int index, E element);***************************** 其他方法 *****************************// 返回链表中包含的元素的数量public int size();// 以适当的顺序（从第一个元素到最后一个元素）返回包含此链表中所有元素的数组public Object[] toArray();// 返回该链表的浅拷贝public Object clone();
LinkedList即可以当栈的实现类，又可以当队列的实现类，因此可以看到有些方法名就与Stack或者Queue里的方法名保持一致，方便习惯了api的人无缝切换到LinkedList的使用上来。
1.2 栈相关API
以下api与Stack类中的方法名保持一致，也推荐使用LinkedList定义的api:
// 将指定元素添加到链表头（对应Stack里的push）
public void push(E e);
// 返回链表的第一个元素，不做删除（对应Stack里的peek）
public E peek();
// 移除链表的第一个元素并返回（对应Stack里的pop）
public E pop();
1.3 队列相关API
以下api与Queue接口中的方法名保持一致，也推荐使用LinkedList定义的api:
// 将指定元素添加到链表末尾（对应Queue里的offer）
public boolean offer(E e);
// 返回链表的第一个元素，不做删除（对应Queue里的peek）
public E peek();
// 返回链表的第一个元素（对应Queue里的element）
public E element();
// 移除链表的第一个元素并返回（对应Queue里的poll）
public E poll();
2、源码浅析
先看一下LinkedList继承了哪些类，实现了哪些接口：
public class LinkedList<E>
extends AbstractSequentialList<E>
implements List<E>, Deque<E>, Cloneable, java.io.Serializable
{}
2.1 内部属性
// LinkedList中元素的数量
transient int size = 0;
// 头节点
transient Node<E> first;
// 尾节点
transient Node<E> last;
LinkedList底层是双向链表，该链表的节点的数据结构是内部类Node，如下：
private static class Node<E> {
// 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;
}
}
这个双向链表如下图所示：
如果看链表相关操作的源码吃力的话，建议先学习一下单链表的数据结构。
2.2 构造函数
// 无参构造函数
LinkedList<String> linkedList = new LinkedList<>();
// 有参构造函数，入参是一个集合
public LinkedList(Collection<? extends E> c);
2.3 add(int index, E element)
public void add(int index, E element) {
// 检查插入索引是否合法
checkPositionIndex(index);
if (index == size)
// 如果是尾插，则走专门的尾插方法
linkLast(element);
else
// 否则走一般的插入方法
linkBefore(element, node(index));
}
checkPositionIndex：
private void checkPositionIndex(int index) {
if (!isPositionIndex(index))
// 又抛出了熟悉的异常
throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
}
isPositionIndex：
private boolean isPositionIndex(int index) {
// 插入索引的位置在头节点和尾结点之间
return index >= 0 && index <= size;
}
linkLast:
// 尾插 && 头插
void linkLast(E e) {
final Node<E> l = last;
final Node<E> newNode = new Node<>(l, e, null);
// 更新last尾节点指向新建的node节点
last = newNode;
// 如果当前链表一个元素都没有，则newNode就是头节点（头插）
if (l == null)
first = newNode;
else
// 让上一个尾节点的next指针指向newNode
l.next = newNode;
// LinkedList总元素个数+1
size++;
// LinkedList被修改次数+1，这一点跟ArrayList一样
modCount++;
}
node：
// LinkedList源码中非常重要的一个方法，很多增删改查方法都会调用该方法
// 该方法输入一个index，返回该index对应的链表的Node节点
Node<E> node(int index) {
// 也要先遍历一下链表才能获取指定位置的Node节点，出于提升遍历效率的考虑，这里有一定优化：
// 遍历链表前会判断一下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;
}
}
linkBefore:
// 插入到链表中间部分
void linkBefore(E e, Node<E> succ) {
// succ是调用node方法根据指定index获取到链表中的Node节点
final Node<E> pred = succ.prev;
// newNode的prev指针和next指针已经安排好了
final Node<E> newNode = new Node<>(pred, e, succ);
// succ节点只需更新prev指针，注意是newNode插入到当前节点succ的前面一个位置
succ.prev = newNode;
// 如果当前链表中只有一个节点，即succ是头结点，需单独处理，直接将头节点指向newNode
if (pred == null)
first = newNode;
else
// pred节点也只需更新prev指针
pred.next = newNode;
size++;
modCount++;
}
如果这块看的迷糊的同学，建议刷一下leetCode里单链表插入节点的题。
2.4 remove(int index)
public E remove(int index) {
// 跟add一样，做操作前先检查一下index值，严谨
checkElementIndex(index);
// 先调用node方法获取指定index的Node节点，再做删除操作
return unlink(node(index));
}
checkElementIndex：
private void checkElementIndex(int index) {
if (!isElementIndex(index))
// index非法都会抛出相同的异常
throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
}
isElementIndex:
private boolean isElementIndex(int index) {
// 判断index是否合法的规则跟isPositionIndex非法一样，必须在头节点和尾节点之间
return index >= 0 && index < size;
}
unlink：
E unlink(Node<E> x) {
// 先把被删除节点的三个成员都获取一遍
final E element = x.item;
final Node<E> next = x.next;
final Node<E> prev = x.prev;
if (prev == null) {
// 如果删除的是头节点，直接将头节点指向当前节点的下一个节点
first = next;
} else {
prev.next = next;
// 当x的三个成员引用在使用完毕后都指向null，便于垃圾回收
x.prev = null;
}
if (next == null) {
// 如果删除的节点是尾节点，直接将尾节点指向当前节点的前一个节点
last = prev;
} else {
next.prev = prev;
// 当x的三个成员引用在使用完毕后都指向null，便于垃圾回收
x.next = null;
}
// 当x的三个成员引用在使用完毕后都指向null，便于垃圾回收，此时x节点在下一次垃圾回收时可以被gc了
x.item = null;
// 更新一下这两个值
size--;
modCount++;
return element;
}
2.5 get(int index)
public E get(int index) {
// 上面已分析过该方法
checkElementIndex(index);
// 先调用node方法获取指定index对应的Node节点，再返回该Node节点的val成员
return node(index).item;
}
2.5 set(int index, E element)
public E set(int index, E element) {
// 上面已分析过该方法
checkElementIndex(index);
// 调用node方法获取指定index对应的Node节点
Node<E> x = node(index);
// 获取当前index下之前的值，因为该方法的返回值是这个
E oldVal = x.item;
// 一个赋值操作，将x.item引用重新指向被set的新值
x.item = element;
return oldVal;
}
3、其他
3.1 ArrayList和LinkedList哪个更占空间？
先上结论：LinkedList更占空间。但也要分析一下ArryList和LinkedList中占内存空间的点是哪些：
- ArryList：由于存在动态扩容机制，且是1.5倍，也就是说当刚触发一次扩容操作时，底层数组中只有将近2/3的空间被利用，还有1/3的空间都是空；
LinkedList：由于底层是双向链表，需要维护头指针和尾指针，虽然没有动态扩容机制，但内存空间占用更大。
3.2 LinkedList真的插入比ArrayList快么？
不一定，要取决插入的具体位置，但整体情况确实是LinkedList的插入比ArrayList快。
如果ArrayList是尾插且不存在扩容的情况，ArrayList的插入操作不会比LinkedList慢，因为仅是一个底层数组的赋值操作；
- 如果是插入在list的中间位置，LinkedList也要先遍历最多一半长度的list找到那个index，然后再做链表插入操作；而ArrayList有可能触发扩容操作，且一定会存在数组的copy动作，如果插入的位置靠近尾端，需要移动元素的个数会相对较少些，移动的元素个数是插入位置之后的元素个数。
3.3 为什么使用LinkedList代替原有的Stack类？
因为Stack的性能相比LinkedList低。因为 Stack 继承自 Vector， 而 Vector 在每个方法中都加了synchronized 锁；但是如果考虑线程安全的情况，不能使用LinkedList，Stack虽然线程安全，但也有比Stack更高效的方案，比如线程安全的集合类，或者在外部加锁。3.4 为什么遍历操作ArrayList比LinkedList效率高？
因为ArryList底层是数组，会开辟一块连续的内存空间，LinkedList相邻节点在内存空间上基本不会连续，显然遍历操作在连续内存空间中更快。参考：
https://www.jianshu.com/p/4a1347d92cef
当面试官问我ArrayList和LinkedList哪个更占空间时，我这么答让他眼前一亮
为什么不推荐 ArrayDeque 代替 Stack
LinkedList详解
若有收获，就点个赞吧
0 人点赞
