以下目录只能预览本篇，请点击右侧目录栏（可滚动）进行内容跳转
目录简介
- LinkedList基于双向链表适用于增删频繁且查询不频繁的场景
- 线程不安全的且适用于单线程
- 可以用LinkedList来实现栈和队列.
继承体系
public class LinkedList<E>
extends AbstractSequentialList<E>
implements List<E>, Deque<E>, Cloneable, java.io.Serializable
- LinkedList继承了AbstractSequentialList
- LinkedList实现了List，（集合功能）
- LinkedList实现了Deque （双端队列功能，模拟栈和队列）
- LinkedList实现了Cloneable（克隆数组，实现为浅拷贝）
- LinkedList实现了Serializable（序列化）
源码分析
属性
//集合元素个数
transient int size = 0;
//链表首节点
//判断一个节点是否是第一个节点的条件：
//(first == null && last == null) || (first.prev == null && first.item != null)
transient Node<E> first;
//链表尾节点
//最后一个节点，判断是否是最后一个节点的条件:
//(first == null && last == null) || (last.next == null && last.item != null)
transient Node<E> last;
主要内部类
典型的双链表结构。
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;
}
}
构造方法
public LinkedList() {
}
public LinkedList(Collection<? extends E> c) {
this();
addAll(c);
}
两个构造方法也很简单，可以看出是一个*的队列。
添加元素
-
从双端队列角度，添加元素分为addFirst和addLast，内部调用linkFirst和linkLast
-
从集合角度，可以在任意位置添加元素add(int index, E element)
作为双端队列，只能支持在队头队尾添加结点。
//从队头添加元素
public void addFirst(E e) {
linkFirst(e);
}
public boolean offerFirst(E e) {
addFirst(e);
return true;
}
//从队头添加元素 主要方法
private void linkFirst(E e) {
//首节点
final Node<E> f = first;
//创建新节点，新节点的next是首节点
/*
new Node<>(null, e, f);
等价于
node.prev = null;
node.val = e;
node.next = f;
*/
final Node<E> newNode = new Node<>(null, e, f);
//让新节点为新的首节点
first = newNode;
// 判断是不是第一个添加的元素
//如果f为空，说明之前没有元素，所以把最后一个节点也赋值为新节点，first=last=newNode
//如果f不为空，把f.prev指向newNode, 即newNode.next=f, f.prev=newNode
if (f == null)
last = newNode;
else
f.prev = newNode;
//元素个数加一
size++;
//修改次数加1，说明这是一个支持fail-fast的集合
modCount++;
}
//从队尾添加元素
public void addLast(E e) {
linkLast(e);
}
public boolean offerLast(E e) {
addLast(e);
return true;
}
//从队尾添加元素 主要方法
void linkLast(E e) {
//尾节点
final Node<E> l = last;
//创建新节点 node.prev=l node.next=null
final Node<E> newNode = new Node<>(l, e, null);
//让新节点为尾节点
last = newNode;
//判断是不是第一个添加的元素
//如果是，将头节点置为新节点 即last=first=newNode
//否则，将尾节点的next置为新节点 newNode.prev=l, l.next=newNode
if (l == null)
first = newNode;
else
l.next = newNode;
size++;//元素个数加1
modCount++;//修改次数加1
}
//队列api 在队尾添加元素值为e的结点
public boolean offer(E e) {
return add(e);
}
public boolean add(E e) {
linkLast(e);
return true;
}
作为List，是要支持在中间添加元素的，主要是通过下面这个方法实现的。
// 在指定index位置处添加元素
public void add(int index, E element) {
//检查索引是否越界
checkPositionIndex(index);
//如果index 是队列尾结点之后的一个位置
//直接添加到尾结点之后
//否则调用linkBefore()方法在中间添加节点
if (index == size)
linkLast(element);
else
linkBefore(element, node(index));
}
//获取索引为index位置的结点
Node<E> node(int index) {
// 所以根据index是在前半段还是后半段决定从前遍历还是从后遍历
// 这样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;
}
}
// 在节点succ之前添加元素
void linkBefore(E e, Node<E> succ) {
// succ是待添加结点的后置结点
//找到待添加结点的前置结点 pred
final Node<E> pred = succ.prev;
//在其前置节点和后继节点之间创建一个新节点
final Node<E> newNode = new Node<>(pred, e, succ);
//后置结点的前置指针指向新结点
succ.prev = newNode;
//如果前置结点为null，说明是第一个添加的元素，修改first指针
//否则前置结点的next为新结点
if (pred == null)
first = newNode;
else
pred.next = newNode;
size++;//修改元素个数
modCount++;//修改次数加1
}
在中间添加元素的方法也很简单，典型的双链表在中间添加元素的方法。
添加元素的三种方式大致如下图所示：
在队列首尾添加元素很高效，因为有首位指针，时间复杂度为O(1)。
在中间添加元素比较低效，首先要先找到插入位置的节点，再修改前后节点的指针，时间复杂度为O(n)。
//按迭代顺序将集合的元素追加到此列表的末尾
public boolean addAll(Collection<? extends E> c) {
return addAll(size, c);
}
//在此列表的给定索引处按迭代顺序插入集合的元素
public boolean addAll(int index, Collection<? extends E> c) {
//检查索引是否合法
checkPositionIndex(index);
//集合转化为数组
Object[] a = c.toArray();
int numNew = a.length;
//如果插入的集合没有元素 直接return false
if (numNew == 0)
return false;
//succ指向当前需要插入结点的位置，pred指向其前一个结点
Node<E> pred, succ;
//当插入位置为列表尾部
if (index == size) {
succ = null;
pred = last;
} else {
//若不是插入尾部，查询索引对应的元素node()
succ = node(index);
pred = succ.prev;
}
//遍历collection中的所有元素将其依次插入链表指定位置
for (Object o : a) {
@SuppressWarnings("unchecked") E e = (E) o;
//创建元素相应新结点
Node<E> newNode = new Node<>(pred, e, null);
//如果插入位置是0
if (pred == null)
first = newNode;
else
//否则 建立结点前后连接
pred.next = newNode;
//切换到下一个结点
pred = newNode;
}
//如果当前位置的结点为空
if (succ == null) {
//将前一个结点置为尾结点
last = pred;
} else {
//否则 建立前后结点的链接
pred.next = succ;
succ.prev = pred;
}
size += numNew;//增加元素个数
modCount++;//修改次数加1
return true;
}
删除元素
- 作为双端队列，删除元素也有两种方式，一种是队列首删除元素，一种是队列尾删除元素。
- 作为List，又要支持中间删除元素
分别如下：
//删除首结点
public E removeFirst() {
//获取首结点
final Node<E> f = first;
//首结点为空 抛出异常
if (f == null)
throw new NoSuchElementException();
return unlinkFirst(f);
}
private E unlinkFirst(Node<E> f) {
// 此时的f已经确定 f == first && f != null;
//首结点的元素值
final E element = f.item;
//首结点的next指针
final Node<E> next = f.next;
//元素值和next指针置null 方便GC回收
f.item = null;
f.next = null;
//把首节点的next作为新的首节点
first = next;
//如果next为null 说明只有一个元素，删除了，把last也置为空
//否则把next前置指针置null
if (next == null)
last = null;
else
next.prev = null;
size--;//元素个数加1
modCount++;//修改次数加1
return element;//返回元素值
}
//删除尾结点
public E removeLast() {
//获取尾结点并保证尾结点不为空，为空抛出异常
final Node<E> l = last;
if (l == null)
throw new NoSuchElementException();
return unlinkLast(l);
}
private E unlinkLast(Node<E> l) {
// 此时的l保证了 l == last && l != null;
//获取尾结点的元素值
final E element = l.item;
//尾结点的前置指针
final Node<E> prev = l.prev;
//元素值 和 前置指针 置null 方便GC回收
l.item = null;
l.prev = null;
// 让前置节点成为新的尾节点
last = prev;
//如果只有一个元素 把首结点也置为null
//否则把前置节点的next置为空
if (prev == null)
first = null;
else
prev.next = null;
size--;
modCount++;
return element;
}
删除中间结点分两种情况，结点是否为null
- 从头到尾遍历整个链表，找到第一个结点值相同的结点， 如果是null使用==，否则使用equals
- 断开结点连接
public boolean remove(Object o) {
if (o == null) {
for (Node<E> x = first; x != null; x = x.next) {
if (x.item == null) {
unlink(x);
return true;
}
}
} else {
for (Node<E> x = first; x != null; x = x.next) {
if (o.equals(x.item)) {
unlink(x);
return true;
}
}
}
return false;
}
E unlink(Node<E> x) {
//x的元素值
final E element = x.item;
//x的前置结点
final Node<E> next = x.next;
//x的后置结点
final Node<E> prev = x.prev;
//如果前置结点为null，说明是第一个添加的结点，令first指向x的后置节点
if (prev == null) {
first = next;
} else {
// 否则修改前置节点的next为x的后置节点
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;
}
删除元素的三种方法都是典型的双链表删除元素的方法，大致流程如下图所示。
在队列首尾删除元素很高效，时间复杂度为O(1)。
在中间删除元素比较低效，首先要找到删除位置的节点，再修改前后指针，时间复杂度为O(n)。
区别： removeLast()在链表为空时将抛出NoSuchElementException，而pollLast()方法返回null。
其他的删除方法：removeFirstOccurrence、removeLastOccurrence
//删除第一个匹配项
ublic boolean removeFirstOccurrence(Object o) {
return remove(o);
}
//删除最后一个匹配项 分为null和非null
public boolean removeLastOccurrence(Object o) {
if (o == null) {
for (Node<E> x = last; x != null; x = x.prev) {
if (x.item == null) {
unlink(x);
return true;
}
}
} else {
for (Node<E> x = last; x != null; x = x.prev) {
if (o.equals(x.item)) {
unlink(x);
return true;
}
}
}
return false;
}
获取元素
//获取指定位置的元素
public E get(int index) {
//检查索引是否合法
checkElementIndex(index);
//返回指定索引的元素
return node(index).item;
}
private void checkElementIndex(int index) {
if (!isElementIndex(index))
throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
}
private boolean isElementIndex(int index) {
return index >= 0 && index < size;
}
Node<E> node(int 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;
}
}
修改元素
//修改指定位置的元素值
public E set(int index, E element) {
//检查索引是否合法
checkElementIndex(index);
//获取指定位置的结点
Node<E> x = node(index);
//获取结点值 方便返回旧结点值
E oldVal = x.item;
//修改结点值
x.item = element;
return oldVal;//返回旧结点值
}
迭代器
//从给定的索引开始，获取此列表上的ListIterator。此方法返回的ListIterator支持add、remove和set方法。
public ListIterator<T> listIterator(int index){
checkBoundsInclusive(index);
return new LinkedListItr<T>(index);
}
//列表上的列表迭代器。这个类跟踪它在列表中的位置以及它所处的两个列表项。
private final class LinkedListItr<I> implements ListIterator<I>{
private int konwnMod = modCount;
private Entry<I> next;
private Entry<I> previous;
private Entry<I> lastReturned;
private int position;
//初始化迭代器
public LinkedListItr(int index) {
if(index == size){
next = null;
previous = (Entry<I>) last;
}else{
next = (Entry<I>)getEntry(index);
previous = next.previous;
}
position = index;
}
//检查迭代器的一致性。
private void checkMod(){
if(konwnMod != modCount)
throw new ConcurrentModificationException();
}
//返回下一个元素的下标
public int nextIndex(){
return position;
}
//返回前一个元素的下标
public int previousIndex(){
return position-1;
}
//如果通过下一个元素存在更多元素，则返回true。
public boolean hasNext(){
return (next != null);
}
//如果先前存在更多元素，则返回true。
public boolean hasPrevious(){
return (previous != null);
}
//返回下一个元素
public I next(){
checkMod();
if(next == null)
throw new NoSuchElementException();
position++;
lastReturned = previous = next;
next = lastReturned.next;
return lastReturned.data;
}
//返回前一个元素
public I previous(){
checkMod();
if(previous == null)
throw new NoSuchElementException();
position--;
lastReturned = next = previous;
previous = lastReturned.previous;
return lastReturned.data;
}
//从列表中删除最近返回的元素
public void remove(){
checkMod();
if(lastReturned == null){
throw new IllegalStateException();
}
if(lastReturned == previous){
position--;
}
next = lastReturned.next;
previous = lastReturned.previous;
removeEntry((Entry<T>)lastReturned);
konwnMod++;
lastReturned = null;
}
//在上一个和下一个之间添加元素，然后前进到下一个。
public void add(I o){
checkMod();
modCount++;
konwnMod++;
size++;
position++;
Entry<I> e = new Entry<I>(o);
e.previous = previous;
e.next = next;
if(previous != null)
previous.next = e;
else
first = (Entry<T>)e;
if(next != null){
next.previous = e;
}else{
last = (Entry<T>) e;
}
previous = e;
lastReturned = null;
}
//更改最近返回的元素的内容。
public void set(I o){
checkMod();
if(lastReturned == null){
throw new IllegalStateException();
}
lastReturned.data = o;
}
}
栈
| Stack Method | Equivalent Deque Method |
|---|---|
| push(e) | addFirst(e) |
| pop() | removeFirst() |
| peek() | peekFirst() |
官方推荐使用Deque代替stack来实现栈
Deque<E> stack = new LinkedList<>()
public void push(E e) {
addFirst(e);
}
public E pop() {
return removeFirst();
}
public E peek() {
final Node<E> f = first;
return (f == null) ? null : f.item;
}
栈的特性是LIFO(Last In First Out)，所以作为栈使用也很简单，添加删除元素都只操作队列首节点即可。
队列
常用操作:
| Throws exception | Returns special value | |
|---|---|---|
| Insert | add(e) | offer(e) |
| Remove | remove() | poll() |
| Examine | element() | peek() |
//添加元素
public boolean offer(E e) {
return add(e);
}
///返回第一个元素，并在队列中删除
public E poll() {
final Node<E> f = first;
return (f == null) ? null : unlinkFirst(f);
}
//获取队头元素
public E peek() {
final Node<E> f = first;
return (f == null) ? null : f.item;
}
//------ 以下api不推荐直接用 因为会抛出异常
//@throws IndexOutOfBoundsException
public boolean add(E e) {
linkLast(e);
return true;
}
//Throws: NoSuchElementException – if this list is empty
public E element() {
return getFirst();
}
//Throws: NoSuchElementException – if this list is empty
public E remove() {
return removeFirst();
区别： getFirst(),element(),peek(),peekFirst() 这四个获取头结点方法的区别在于对链表为空时的处理，是抛出异常还是返回null，其中getFirst() 和element() 方法将会在链表为空时，抛出异常
element()方法的内部就是使用getFirst()实现的。它们会在链表为空时，抛出NoSuchElementException
getLast() 方法在链表为空时，会抛出NoSuchElementException，而peekLast() 则不会，只是会返回 null。
总结
-
LinkedList是一个以双链表实现的List；
-
LinkedList还是一个双端队列，具有队列、双端队列、栈的特性；
-
LinkedList在队列首尾添加、删除元素非常高效，时间复杂度为O(1)；
-
LinkedList在中间添加、删除元素比较低效，时间复杂度为O(n)；
-
LinkedList不支持随机访问，所以访问非队列首尾的元素比较低效；
-
LinkedList在功能上等于ArrayList + ArrayDeque；
-
遍历效率(快-慢)：
Iterator迭代 > for循环
LinkedList面试题
Arraylist 与 LinkedList 区别?
-
是否保证线程安全：
ArrayList和LinkedList都是不同步的，也就是不保证线程安全； -
底层数据结构：
Arraylist底层使用的是 Object 数组；LinkedList底层使用的是 双向链表 数据结构（JDK1.6 之前为循环链表，JDK1.7 取消了循环） -
插入和删除是否受元素位置的影响：
-
ArrayList采用数组存储，所以插入和删除元素的时间复杂度受元素位置的影响。首尾插入O(1),中间插入O(n-i) -
LinkedList采用链表存储，所以，如果是在头尾插入或者删除元素不受元素位置的影响，近似 O(1)，如果是要在指定位置 i 插入和删除元素的话 时间复杂度近似为 O(n)
- 是否支持快速随机访问：
LinkedList 不支持高效的随机元素访问，而 ArrayList 支持。快速随机访问就是通过元素的序号快速获取元素对象(对应于get(int index)方法)。
- 内存空间占用：
ArrayList的花费主要体现在在 list 列表的结尾会预留一定的容量空间，
而 LinkedList 的空间花费则体现在它的每一个元素都需要消耗比 ArrayList 更多的空间（因为要存放直接后继和直接前驱以及数据）。