在日常开发中,最常用的List是ArrayList其次便是LinkedList了.上次我们已经研究过了ArrayList,今天来深入学习下LinkedList...
概述
LinkedList顾名思义本质上就是一个链表.它和ArrayList一样实现了List接口.
ArrayList是基于可变数组实现的,因此对于随机访问和修改ArrayList的效率会更高,而LinkedList更擅长于随机插入和删除,毕竟只需要移动"指针"即可.
源码分析
结构图
继承关系
public class LinkedList<E>
extends AbstractSequentialList<E>
implements List<E>, Deque<E>, Cloneable, java.io.Serializable {
LinkedList继承了AbstractSequentialList<E>,同时又实现了List<E> Deque<E> Cloneable Serializable.
AbstractSequentialList<E> 继承了 AbstractList<E>是LinkedList的父类,是List的简单实现,提供了对连续访问的支持,对于随机访问数据,应优先使用AbstractList.
为何又实现List的原因在此就不重复叙述了,如想了解可==点击此处(ArrayList)==.
Deque<E> 继承自Queue<E>, Queue<E>是Java中所有队列实现的根接口.
public interface Queue<E> extends Collection<E> {
// 把元素插入到队列末端 插入成功返回true, 若无空间可插入,则抛异常 (不推荐使用)
boolean add(E e);
// 把元素插入到队列末端 插入成功返回true, 反之 false
boolean offer(E e);
// 从队首删除一个元素并返回该元素 若队列为空抛异常 (不推荐使用)
E remove();
// 从队首删除一个元素并返回该元素 若队列为空,返回null
E poll();
// 获取队首的元素(只是获取并不会删除) 若队列是空的会抛异常 (不推荐使用)
E element();
// 获取队首的元素(只是获取并不会删除) 若队列是空,返回null
E peek();
}
Deque<E>是一个双端队列同时又提供了对栈的抽象,其支持在两端插入和移除元素.通常Deque的实现对容量是没有固定限制,但此接口即支持限容的双端队列,也支持无限容的双端队列.
public interface Deque<E> extends Queue<E> {
void addFirst(E e); // 队首插入元素,插入失败抛异常
void addLast(E e); // 队尾插入元素,插入失败抛异常
boolean offerFirst(E e); // 队首插入元素,插入失败返回false
boolean offerLast(E e); // 队尾插入元素,插入失败返回false
E removeFirst(); // 队首删除元素,删除失败抛异常
E removeLast(); // 队尾删除元素,删除失败抛异常
E pollFirst(); // 队首删除元素, 队列为空抛异常
E getFirst(); // 队首获取(不删除)元素,队列为空抛异常
E peekFirst(); // 队首获取(不删除)元素,队列为空返回null
...
}
它的api里提供了两种方式.一种在操作失败时抛出异常,另一种形式返回特殊值(null/false).插入操作的后一种形式是专为使用有容量限制的Deque实现设计的;在大多数实现中，插入操作不能失败.
Deque<E>包含的栈相关api:
E peek(); // 查看栈顶元素
void push(E e); // 入栈
E pop(); // 弹栈
注意: Java堆栈Stack类已经过时,官方推荐使用Deque代替Stack使用.
/**
* <p>A more complete and consistent set of LIFO stack operations is
* provided by the {@link Deque} interface and its implementations, which
* should be used in preference to this class. For example:
* <pre> {@code
* Deque<Integer> stack = new ArrayDeque<Integer>();}</pre>
*/
链表节点实体
Node<E>是LinkedList<E>维护链表结构的核心私有类,比较简单,直接看代码.
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;
}
}
类中属性
通过first last俩节点来维护链表进行各项操作,注意transient关键字,自定义了序列化方式.
/** 版本号,用于校验正反序列化时的一致性 */
private static final long serialVersionUID = 876323262645176354L;
/** 元素数量 **/
transient int size = 0;
/** 链表的首节点 */
transient Node<E> first;
/** 链表的尾节点 */
transient Node<E> last;
构造函数
两个构造器.一个无参,一个插入指定集合.
// 无参构造器
public LinkedList() {}
// 构造一个包含指定集合元素的LinkedList
public LinkedList(Collection<? extends E> c) {
this();
// 添加指定集合中的所有元素到LinkedList中
addAll(c);
}
核心函数
由于接口实现较多,各个功能的多个实现核心差不多,这里挑选每种功能里核心的来讲解.如想深入每个函数,请自行
翻阅源码.
查询节点
查询函数较为简单
/**
* 返回列表中指定位置的元素。
*/
public E get(int index) {
// 检查下标是否是链表内的
checkElementIndex(index);
// node(index) 会获取到下标为index的节点
return node(index).item;
}
Node<E> node(int 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;
}
}
public E getFirst() {
final Node<E> f = first;
if (f == null)
throw new NoSuchElementException();
return f.item;
}
public E getLast() {
final Node<E> l = last;
if (l == null)
throw new NoSuchElementException();
return l.item;
}
node(index)函数则是根据下标查找节点.
从这里就可以看出,基于双向链表结构的LinkedList,通过索引index查询是低效的,index元素越靠近中间所耗费的实际就越长,而在链表双端进行查询则会非常高效.
删除节点
/**
* 删除指定元素
*/
public boolean remove(Object o) {
// LinkedList可以接收null值
if (o == null) {
// 元素为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) {
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.prev = null;
}
// 若删除的节点是尾节点
if (next == null) {
last = prev;
} else {
next.prev = prev;
x.next = null;
}
// 清空x相关引用,方便gc
x.item = null;
size--;
modCount++;
return element;
}
通过remove(Object o)可以看出LinkedList是支持存储null值的,而unlink(Node<E> x)就是把x节点给置空,同时把x节点的上一个节点和下一个节点关联起来.
修改节点
/**
* 用指定的元素替换列表中指定位置的元素。
*/
public E set(int index, E element) {
checkElementIndex(index);
// 定位需要修改的节点
Node<E> x = node(index);
E oldVal = x.item;
x.item = element;
return oldVal;
}
set函数看起来比较简单,只要定位到节点,并修改节点内的元素就行了.
添加节点
// 添加元素
public boolean add(E e);
// 在指定下标插入元素
public void add(int index, E element);
// 在指定下标插入指定集合
public boolean addAll(int index, Collection<? extends E> c);
// 添加指定节点为第一个节点
public void addFirst(E e);
// 添加指定节点为尾节点
public void addLast(E e);
// 把指定集合里的元素添加到该LinkedList中
public boolean addAll(Collection<? extends E> c);
boolean add(E e)
add(E e)函数实际上是通过linklast(E e)来实现.而linklast(E e)内部也较为简单,即在老的last节点后再加入一个节点.注释较全,直接看代码
/**
* 添加元素
*/
public boolean add(E e) {
linkLast(e);
return true;
}
/**
* 添加指定元素到尾节点
*/
void linkLast(E e) {
final Node<E> l = last;
// 创建一个新节点,同时把这个节点的pred设置为原来的尾节点
final Node<E> newNode = new Node<>(l, e, null);
// 设置当前节点为last节点
last = newNode;
// 如果原本无尾节点,说明当前无任何节点
if (l == null)
// 把这个新的节点同时设定为首节点
first = newNode;
else
// 设置 老的尾节点的下一个节点为newNode
l.next = newNode;
// 元素数量+1 , 操作+1
size++;
modCount++;
}
翻阅源码即可发现类似linkLast(E e)的函数还有俩,
/**
* 添加指定元素为当前的首节点
*/
private void linkFirst(E e) {
final Node<E> f = first;
final Node<E> newNode = new Node<>(null, e, f);
first = newNode;
if (f == null)
last = newNode;
else
f.prev = newNode;
size++;
modCount++;
}
/**
* 在指定节点的位置插入节点
*/
void linkBefore(E e, Node<E> succ) {
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++;
}
其中linkFirst(E e)和linkLast(E e)没啥区别,无非是把last换成了first.
而linkBefore则是把succ的上一个节点的next指向新节点,同时把新节点的next指向succ,再把succ的prev指向新节点,如下图:
void add(int index, E element)
该函数用到了上述讲过的 linkLast(element)和linkBefore(element)函数.
/**
* 在指定的下标插入节点
*/
public void add(int index, E element) {
checkPositionIndex(index);
if (index == size)
linkLast(element);
else
linkBefore(element, node(index));
}
private void checkPositionIndex(int index) {
if (!isPositionIndex(index))
throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
}
private boolean isPositionIndex(int index) {
return index >= 0 && index <= size;
}
先调用checkPositionIndex检测插入下标是否越界,再根据index是否是size来判断调用的插入函数.
boolean addAll(int index, Collection<? extends E> c);
/**
* 从指定下标开始插入指定的集合
*/
public boolean addAll(int index, Collection<? extends E> c) {
// 越界检查
checkPositionIndex(index);
// 转换数组
Object[] a = c.toArray();
int numNew = a.length;
if (numNew == 0)
return false;
// 获取 index索引位置上的节点,和其上一个节点
Node<E> pred, succ;
if (index == size) {
succ = null;
pred = last;
} else {
succ = node(index);
pred = succ.prev;
}
// 从index位置开始插入
for (Object o : a) {
E e = (E) o;
Node<E> newNode = new Node<>(pred, e, null);
if (pred == null)
first = newNode;
else
pred.next = newNode;
pred = newNode;
}
// 最后把原位置上节点的prev设置为集合c的最后一个节点
if (succ == null) {
last = pred;
} else {
pred.next = succ;
succ.prev = pred;
}
// 修改计数
size += numNew;
modCount++;
return true;
}
addAll(int index, Collection<? extends E> c)的代码首先是把集合c转换成Object[],然后获取index索引上的节点,再以其上一个节点为起点开始插入.
总结
只要理解了双向链表的存储结,再看LinkedList的源码就会简单很多了.LinkedList其余函数在此就不叙述了,实现上相似.源码分析的差不多了,这里来做下总结.
LinkedList是一个有序的可重复允许null值的集合,看其内部实现不存在容量不足的问题.底层使用了双向链表结构维护了first和last指针.实现了栈和队列相关接口,所以可做栈,队列,双端队列来使用.
