从jdk源码的角度重温链表

链表

  • 由一系列节点组成的有序集合。
  • 分为单向链表, 双向链表,循环链表
  • 单向链表: 每一个节点都有一个指针指向下一个节点,最后一个节点的指针指向null
  • 双向链表: 每一个节点都有两个指针(这里用p, n代表两个指针),p指向前一个节点,n指向下一个节点。但第一个节点的p指向null, 最后一个节点的n指向null
  • 循环链表: 每一个节点都有两个指针(这里用p, n代表两个指针), 第一个节点的p指向最后一个节点, 最后一个节点的n指向第一个节点。这样就形成了循环
java的LinkedList - 双向链表

这里以java的LinkedList的源码学习,不多说,先看源码

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;
}
}

上面代码定义了一个类,代表一个节点的实体类,里面有3个成员变量,next用于指向下一个节点,prev用于指向前一个节点,item则是该节点承载的元素。

接下来,看一下它的一些添加元素的方法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

public boolean add(E e) {
linkLast(e);
return true;
}

public void addFirst(E e) {
linkFirst(e);
}

public void addLast(E e) {
linkLast(e);
}

public void add(int index, E element) {
checkPositionIndex(index);

if (index == size)
linkLast(element);
else
linkBefore(element, node(index));
}

添加元素主要有4个方法,

  • add和addLast其实是同一方法,都是在后面添加一个元素,所有都调用了linkLast(e);
  • addFirst则调用linkFirst(e);
  • add(index, element)这个方法是把元素添加某个位置,先调用checkPositionIndex(index)检查index是否在[0,size]之间, 接着判断想添加到index是否等于size,
    因为位置是0开始,如果index == size,直接调用linkLast()放到最后一个位置即可。否则调用linkBefore方法

继续看linkLast,linkFirst,linkBefore这三个方法 ….

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

这个方法目的是把元素放到最前面,first和last是两个Node的成员变量,可以理解为用来记录第一个和最后一个的来临时变量。
先创建一个节点new Node<>(null, e, f),要把元素放到最前面,此时newNode就是第一个节点,之前的第一个节点就成为newNode的下一个节点。
接着判断 f == null, 这里的f是指没添加之前的第一个节点,如果f为null, 那么当前添加就是第一个节点,也是最后一个节点,所以newNode赋值为last;
如果f不为null, 那么f的p指针就应该指向newNode。最后记录节点的变量+1。

1
2
3
4
5
6
7
8
9
10
11
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差不多, 临时变量l记录最后一个节点,然后创建一个新的节点,该节点p指向l, n指向null,
如果l为null, 没添加元素前为空集合,所以当前也是第一个节点,赋值为first;如果l不为null, 那么 l 的n应该指向新的节点。最后节点数+1.

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

linkBefore方法的目的是将元素e放到一个指定的节点之前。 succ是这个指定的节点。首先用临时变量pred记录succ的前一个节点,
接着创建一个新的节点,p指向pred, n指向succ, succ的p指针就指向这个新的节点newNode。如果pred 为null, succ的前一个节点为null,
那么newNode就是第一个节点;如果pred不为null, pred的n指针应该指向newNode。最后节点数+1

添加分析完了,接下来看看移除

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
26
27
28
29
30
31
32
33
34
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);
}


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;
}

removeFirst, removeLast 分别调用unlinkFirst(f), unlinkLast(l);

看remove方法,遍历链表,从first开始, 找到和o相等的元素,调用unlink方法完成移除。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
private E unlinkFirst(Node<E> f) {
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--;
modCount++;
return element;
}

f是第一个节点,f.item和f.next分别临时赋值给element和next,接着f.item和f.next都设为null,就意味着移除了第一个节点,
那么next这个节点就是第一节点了,赋值给first; 如果next为null, 那么last为null,说明现在链表整个为空啦;如果next不为null,将next的p指针指向null。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
private E unlinkLast(Node<E> l) {
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;
}

l是最后一个节点,l.item和l.prev分别临时赋值给element和prev,接着l.item和l.prev都设为null,就意味着移除了最后一个节点了,
那么prev这个节点就是最后一个节点了,赋值给last; 如果prev为null, 那么first也为null,说明现在链表整个为空啦;如果prev不为null,将prev的n指针指向null。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
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.item = null;
size--;
modCount++;
return element;
}

移除某个节点: x.item, x.next, x.prev分别临时赋值给element, next和prev; 重新调整next 和prev节点,
如果prev为null, 那么next节点就是第一个节点;如果prev不为null, prev的n指向next, x的p设为null;
如果next为null, 那么prev节点就是最后一个节点; 如果next不为null, next的p指向prev, x的next设为null;
最后把x.item设为null,移除当前, size–代表节点数减1, modCount记录的是链表的操作次数,所以怎么都是加1。

到此, 双向链表的实现就基本完成啦。如果要实现循环链表,在双向链表的基础上,把第一个节点的p指向最后一个, 把最后一个节点的n指向第一个节点。

Loading comments box needs to over the wall