LinkedList 是 Java 集合框架中一个常用的集合类,底层采用双向链表结构。和 ArrayList 一样,LinkedList 也支持空值和重复值。
由于 LinkedList 基于链表实现,存储元素过程中,无需像 ArrayList 那样进行扩容。但有得必有失,LinkedList 存储元素的节点需要额外的空间存储前驱和后继的引用。另一方面,LinkedList 在链表头部和尾部插入效率比较高,但在指定位置进行插入时,效率一般。原因是,在指定位置插入需要定位到该位置处的节点,此操作的时间复杂度为 O(N)
。
最后,LinkedList 是非线程安全的,并发环境下,多个线程同时操作 LinkedList,会引发不可预知的错误。
我们先来看下 LinkedList 的常用操作:
LinkedList<String> dataList = new LinkedList<>(); // 创建 LinkedList
dataList.add("test"); // 添加数据
dataList.add(1, "test1"); // 指定位置,添加数据
dataList.addFirst("first"); // 添加数据到头部
dataList.addLast("last"); // 添加数据到尾部
dataList.get(0); // 获取指定位置数据
dataList.getFirst(); // 获取头部数据
dataList.getLast(); // 获取尾部数据
dataList.remove(1); // 移除指定位置的数据
dataList.removeFirst(); // 移除头部数据
dataList.removeLast(); // 移除尾部数据
dataList.clear(); // 清空数据
LinkedList 与 ArrayList 不同的是 LinkedList 没有直接继承 AbstractList,而是继承的 AbstractSequentialList 双向链表,AbstractSequentialList 提供了一套基于顺序访问的接口。
LinkedList 实现了 Deque 接口,也可以当队列使用。
transient int size = 0; // 当前列表的节点个数
transient Node<E> first; // 第一个节点
transient Node<E> last; // 最后一个节点
/* 构造方法一 */
public LinkedList() {
}
/* 构造方法二 */
public LinkedList(Collection<? extends E> c) {
this();
addAll(c);
}
可以看到 LinkedList 有 三个成员变量和两个构造方法,这里需要注意一下成员变量前面的 transient
关键字。
transient 关键字:当对象被序列化时(写入字节序列到目标文件)时,transient阻止实例中那些用此关键字声明的变量持久化;当对象被反序列化时(从源文件读取字节序列进行重构),这样的实例变量值不会被持久化和恢复。
为什么要有这个关键字呢?因为这里要告诉虚拟机,这三个成员变量不是 LinkedList 的永久性变量。
下面来分析一下构造方法二中的 addAll()
方法。
public boolean addAll(Collection<? extends E> c) {
return addAll(size, c);
}
public boolean addAll(int index, Collection<? extends E> c) {
// 检查 index 是否越界
checkPositionIndex(index);
Object[] a = c.toArray();
int numNew = a.length;
if (numNew == 0) // 需要添加的集合为空,直接返回
return false;
Node<E> pred, succ;
if (index == size) { // 插入位置与当前列表数量相同,表示为尾部插入
succ = null;
pred = last;
} else { // 否则,寻找 index 所在节点
// 找到 index 所在位置的节点,
// 也就是插入集合后的后一个节点
succ = node(index);
// index 所在位置的前一个节点,
// 也就是插入集合后的前一个节点
pred = succ.prev;
}
// 遍历需要添加的集合,逐个插入
for (Object o : a) {
// 创建一个新的节点,以 pred 为前一个节点,值为 e,null 为后一个节点
@SuppressWarnings("unchecked") E e = (E) o;
Node<E> newNode = new Node<>(pred, e, null);
if (pred == null) // 如果 pred 为空,说明是在头部插入
first = newNode; // 也就是说新建的节点是第一个节点
else // pred 不为空,说明是在中间或者尾部从插入
pred.next = newNode; // pred 的下一个节点连接上新创建的节点
pred = newNode; // 依次插入
}
if (succ == null) { // 如果 succ 为空,说明是在尾部插入
last = pred; // 所以最后插入的元素就是最后一个元素
} else { // succ 不为空,说明是在中间插入
pred.next = succ; // 最后插入的元素连接上后面的一段
succ.prev = pred; // 后面的一段第一个元素连接上前面的一段
}
size += numNew; // 数量合并
modCount++;
return true;
}
我们来看下 checkPositionIndex()
方法:
private void checkPositionIndex(int index) {
if (!isPositionIndex(index))
throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
}
private boolean isPositionIndex(int index) {
return index >= 0 && index <= size;
}
看到了很熟悉的异常 IndexOutOfBoundsException
,就是根据链表大小检查一下,逻辑很简单。
我们继续分析 add()
方法:
public boolean add(E e) {
linkLast(e);
return true;
}
public void add(int index, E element) {
// 检查 index 是否越界,上面分析过了
checkPositionIndex(index);
if (index == size) // 插入位置与当前数量相同,说明是尾部插入
linkLast(element);
else
linkBefore(element, node(index));
}
public void addFirst(E e) {
linkFirst(e);
}
public void addLast(E e) {
linkLast(e);
}
这里主要是调用了 linkFirst()
、linkLast()
、linkBefore
三个方法,我们继续分析。
private void linkFirst(E e) {
final Node<E> f = first; // 当前第一个节点
// 创建了一个新节点,以 null 为前一个节点、e 为值、当前第一个节点为下一个节点
final Node<E> newNode = new Node<>(null, e, f);
first = newNode; // 设置新建的节点为第一个节点
if (f == null) // 当前第一个节点为空,说明列表为空
last = newNode; // 所以最后一个节点为当前插入的节点
else // 当前第一个节点不为空,说明列表不为空
f.prev = newNode; // 当前列表头部连接上插入的节点
size++;
modCount++;
}
linkFirst()
逻辑很简单,就是头部插入节点的操作。
void linkLast(E e) {
final Node<E> l = last;
final Node<E> newNode = new Node<>(l, e, null);
last = newNode;
if (l == null)
first = newNode;
else
l.next = newNode;
size++;
modCount++;
}
linkLast()
的逻辑与 linkFirst()
的逻辑相似这里不再分析,大家自己分析一下。
void linkBefore(E e, Node<E> succ) {
// assert succ != null;
final Node<E> pred = succ.prev; // 获取到 succ 的上一个节点
// 创建一个新的节点,连接到 succ 上一个节点后面
final Node<E> newNode = new Node<>(pred, e, succ);
succ.prev = newNode; // 将 succ 连接到 newNode 后面
if (pred == null) // 如果 succ 的上一个节点为空,说明 succ 为头部节点
first = newNode; // 直接将 newNode 设为头部节点
else // 如果 succ 的上一个节点不为空,说明 succ 为中间或者尾部节点
pred.next = newNode; // 将 succ 的上一个节点关联到 newNode 上
size++;
modCount++;
}
linkBefore()
的逻辑也很简单,就是在某个节点前面插入一个节点。
我们接着来看 get()
方法。
public E get(int index) {
// 检查 index 是否越界,上面分析过了
checkElementIndex(index);
return node(index).item;
}
get()
中调用了 node()
方法。
Node<E> node(int index) {
// 如果 index 小于 size 的一半,从开头开始查找
if (index < (size >> 1)) {
Node<E> x = first;
// 抽头开始查找,直到 i == index
for (int i = 0; i < index; i++)
x = x.next;
return x;
} else { // 如果 index 大于 size 的一半,从尾部开始查找
Node<E> x = last;
for (int i = size - 1; i > index; i--)
x = x.prev;
return x;
}
}
node()
方法的就是根据 index 查找到对应节点,这里用到了折半查找,算是一个小优化。大家可以思考一下这里为什么只折半了一次,而不是一直折半下去呢?
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;
}
另外两个 getFirst()
、getLast()
方法比较简单,大家看一下就行,不再分析。
我们继续分析 remove()
方法。
public E remove(int index) {
// 检查 index 是否越界,上面分析过了
checkElementIndex(index);
return unlink(node(index));
}
public E removeFirst() {
final Node<E> f = first;
if (f == null)
throw new NoSuchElementException();
return unlinkFirst(f);
}
public E removeLast() {
final Node<E> l = last;
if (l == null)
throw new NoSuchElementException();
return unlinkLast(l);
}
可以看到 remove()
方法中分别调用了 unlink()
、unlinkFirst()
、unlinkLast()
我们分别来看下。
E unlink(Node<E> x) {
// assert x != null;
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.item = null; // 当前节点元素设置为空,方便 GC
size--;
modCount++;
return element;
}
可以看到 unlink()
方法就是移除链表上的某个节点。
private E unlinkFirst(Node<E> f) {
// assert f == first && f != null;
final E element = f.item; // 获取到当前节点的元素
final Node<E> next = f.next; // 获取到当前节点的下一个元素
f.item = null;
f.next = null; // help GC
first = next; // 将当前节点的下一个节点设置为头部节点
if (next == null) // 如果下一个节点为空,说明链表只有一个节点
last = null; // 清空尾部节点
else // 否则,说明还有其他节点
// 下一个节点已经设置为头部节点了
// 所以清空一下与前一个节点的 关联
next.prev = null;
size--; // 数量 -1
modCount++;
return element;
}
unlinkFirst()
方法主要是移除头部节点的操作。
private E unlinkLast(Node<E> l) {
// assert l == last && l != null;
final E element = l.item;
final Node<E> prev = l.prev;
l.item = null;
l.prev = null; // help GC
last = prev;
if (prev == null)
first = null;
else
prev.next = null;
size--;
modCount++;
return element;
}
unlinkLast()
方法与 unlinkFirst()
方法的逻辑相似,这里不再赘述,大家自己分析下就好。
我们最后分析下 clear()
方法:
public void clear() {
// 遍历一遍全部设置为空
for (Node<E> x = first; x != null; ) {
Node<E> next = x.next;
x.item = null;
x.next = null;
x.prev = null;
x = next;
}
first = last = null;
size = 0;
modCount++;
}
可以看到 clear()
方法操作很简单,就是遍历一下全部设置为空。
通过上面的分析,大家对 LinkedList 的底层实现应该很清楚了。总体来看 LinkedList 的源码并不复杂,大家耐心看一下,一般都能看懂。好了本文就到这里了,希望对大家有所帮助。