从源码上分析 LinkedList(附图)

前言

上一篇我们介绍了 ArrayList,这次,我们再看看一下它的兄弟:LinkedList

LinkedList 同样也实现了 List 接口,底层原理是双向链表,那么它又是如何实现的呢?继续来看吧。

源码分析

成员变量

LinkedList 只有三个成员变量:

1
2
3
4
5
transient int size = 0;

transient Node<E> first;

transient Node<E> last;

size 属性不用说,肯定是表示链表的逻辑长度,first 应该是链表的第一个元素,last 表示最后一个元素。

构造方法

先来看无参构造:

1
2
public LinkedList() {
}

无参构造没有任何逻辑,那么再来看看其他的构造方法:

1
2
3
4
public LinkedList(Collection<? extends E> c) {
this();
addAll(c);
}

这里牵扯到要给 addAll 方法,一会在常用方法里我们会讲到,这里先放一放。

这次我们带上内存图来分析,会更直观一些,首先用无参构造来创建一个对象:

1
List<Student> list = new LinkedList<>();

注:为了节省篇幅,本图省略了一些细节上东西,如常量池,方法区等内容。

常用方法

add

首先是 add 方法:

1
2
3
4
public boolean add(E e) {
linkLast(e);
return true;
}

1
2
3
4
5
6
7
8
9
10
11
void linkLast(E e) {
final Node<E> l = last; // last 节点表示添加前最后一个节点
final Node<E> newNode = new Node<>(l, e, null); // 要添加的节点的上一个节点应该是 last 节点。
last = newNode; // 添加了节点后,添加的新节点应该为 last 节点。
if (l == null) // 如果当前元素没有上一个元素,则表示为第一次添加,
first = newNode; // 那么当前节点应该也算是 first 节点。
else
l.next = newNode;
size++; // 逻辑长度 + 1
modCount++; // 修改次数 + 1
}

这里提到了 Node 类,来看看它的定义:

1
2
3
4
5
6
7
8
9
10
11
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;
}
}

原来 Node 类是 LinkedList 的静态内部类,表示链表的一个节点。

那么当我们执行这段代码后,会发送什么呢?

1
list.add(new Student("张三", 20));

那我们再添加一个元素呢?

1
list.add(new Student("李四", 21));

可能看起来有写复杂,其实也不难理解,耐下心对照源码好好看一下,应该就能理解这张图的意思了。

我们再添加两个元素看看效果。

1
2
list.add(new Student("王五", 22));
list.add(new Student("赵六", 23));

remove

添加了这么多,我们删除一个试试,先来看看源码:

1
2
3
4
5
// 根据索引删除
public E remove(int index) {
checkElementIndex(index); // 检查要删除的元素索引是否有效,即 0 <= index < size
return unlink(node(index)); // node(index) 方法找到第 index 个元素
}

1
2
3
4
5
6
7
private void checkElementIndex(int index) {
if (!isElementIndex(index))
throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
}
private boolean isElementIndex(int index) {
return index >= 0 && index < size;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
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; // 删除头节点后,更换 first 指向
} else { // 如果不是头节点
prev.next = next; // 将前驱节点的 next 指向要删除节点的后继节点
x.prev = null; // 将要删除的节点不再指向任何节点
}

if (next == null) { // 如果当前节点为最后一个节点
last = prev; // 将 last 指向倒数第二个
} else { // 如果不是最后一个节点
next.prev = prev; // 将后继节点的 prev 指向要删除元素的前驱节点
x.next = null; // 将要删除的节点不再指向任何节点
}

x.item = null; // 将要删除的元素的数据清空
size--; // 逻辑长度 - 1
modCount++; // 修改次数 + 1
return element;
}

可能这里的这 10 和 17 行不太容易理解:

1
2
prev.next = next;         // 将前驱节点的 next 指向要删除节点的后继节点
next.prev = prev; // 将后继节点的 prev 指向要删除元素的前驱节点

举个简单的例子:
张三 <==> 李四 <==> 王五

那么要删除李四的话,应该要将张三的 “下一个” 指向王五吧,也就是 prev.next = next;。同样,应为是双向链表,所以也应该让王五的 “上一个” 指向张三,即 next.prev = prev;

这里讲解的是根据索引删除,还有根据元素删除,其实原理是一样的,主要是 unlink 这个方法,先根据传入的参数,找到要删除的元素,然后进行 unlink 方法的逻辑即可,这里就不再展开,如果你看懂了根据索引删除,相信你也能理解根据元素删除。

但是需要注意的是:如果删除的是引用数据类型的话,需要重写 equals 方法,不然可能会无法进行删除操作哦。

其实仔细想想也能理解,既然需要 找到要删除的元素,那么如何判断传入的参数和要删除的是同一个呢?只有 equals 方法了,而默认从 Object 继承的 equals 方法可不一定能满足我们的需求,因为它只比较地址值,所以我们需要重写 equals 方法。

get

1
2
3
4
 public E get(int index) {
checkElementIndex(index); // 检查要获取的元素索引是否有效,即 0 <= index < size
return node(index).item; // 根据索引来找到这个元素,返回它的 item 值
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
 Node<E> node(int index) {
// assert isElementIndex(index);

if (index < (size >> 1)) { // 如果要删除的元素在前半段, 则从 first 开始查找
Node<E> x = first;
for (int i = 0; i < index; i++)
x = x.next;
return x;
} else { // 如果要删除的元素在后半段, 则从 last 开始查找
Node<E> x = last;
for (int i = size - 1; i > index; i--)
x = x.prev;
return x;
}
}

这里用了一个很巧妙的小算法,既然我们知道链表的长度,那么当要删除的元素 索引 < 长度 / 2,就从第一个开始找,反之从最后一个开始找,长度 / 2 可以改写为位运算即:size >> 1,效率更高一些。

先讲这么多,如果你看懂了这些,相信 LinkedList 的其他方法,你也能够轻松的理解。

总结

根据上方的源码分析,我们可以总结出 LinkedList 的一些特性:

  • LinkedList 底层数据结构是双向链表。
  • 不能对元素进行随机访问,虽然提供了 get 方法,但这个方法是通过遍历来实现的。
  • 删除、添加元素的效率很高,但查找元素的的效率较差。
坚持原创技术分享,您的支持将鼓励我继续创作!