定义
链表：各个元素物理内存空间不连续，通过“指针”将一组零散的内存空间串联起来。指针的链接顺序为链表中元素的逻辑顺序。
基本特点
链表由一组节点组成，每个节点包含两个部分：一个是存储元素的数据域，另一个是存储下一个节点地址的指针域。天然支持动态扩容。
链表分类
- 单链表：第一个节点称为头节点，最后一个节点称为尾节点。头节点用来记录链表的基地址，可以通过头节点遍历整个链表。尾节点的指针域指向
null。 - 循环链表：特殊的单链表，与单链表唯一不同的是：尾节点的指针域指向了头节点。
- 双向链表：每个节点不仅存储数据域和指向下一个节点的指针域，它还会有一个指针域指向前一个节点。通常称为前驱节点和后继节点。
- 双向循环链表：综合了循环链表和双向链表。头节点的前驱节点指向尾节点，尾节点的后继节点指向头节点。
JDK的java.util.LinkedList就是一个双向链表。
单链表节点类定义
我们来定义一个单链表的节点类SinglyLinkedListNode：
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
| package com.sunchaser.sparrow.algorithm.base.linkedlist;
import lombok.AllArgsConstructor;
import lombok.Data;
import lombok.NoArgsConstructor;
@Data
@NoArgsConstructor
@AllArgsConstructor
public class SinglyLinkedListNode {
public Integer val;
public SinglyLinkedListNode next;
public SinglyLinkedListNode(Integer val) {
this.val = val;
}
}
|
构造单链表及其打印
构造一个单链表，并按顺序打印在控制台。我们提供一个工具类LinkedListUtils来实现。
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
35
36
37
38
39
40
41
42
| package com.sunchaser.sparrow.algorithm.base.util;
import com.sunchaser.sparrow.algorithm.base.linkedlist.SinglyLinkedListNode;
public class LinkedListUtils {
private LinkedListUtils() {
}
public static SinglyLinkedListNode generateSinglyLinkedList() {
SinglyLinkedListNode node4 = new SinglyLinkedListNode(5,null);
SinglyLinkedListNode node3 = new SinglyLinkedListNode(4,node4);
SinglyLinkedListNode node2 = new SinglyLinkedListNode(3,node3);
SinglyLinkedListNode node1 = new SinglyLinkedListNode(2,node2);
return new SinglyLinkedListNode(1,node1);
}
public static void printLink(SinglyLinkedListNode head) {
if (head == null) {
System.out.print("");
return;
}
if (head.next == null) {
System.out.println("->" + head.val + "->null");
return;
}
System.out.print("->" + head.val);
printLink(head.next);
}
}
|
插入和删除操作
单链表的插入操作：例如：1 -> 2 -> 3 -> 4 -> 5 -> null。
现在要将元素0插入到3和4之间。做法很简单，只需要先将0指向4，再将3指向0即可。注意先后顺序，要先将0指向4，后将3指向0。因为如果顺序对调，将3先指向0之后就找不到节点4了。
现在要将0从链表中删除。需要将节点0前面的节点3指向节点0后面的4，然后将节点0的指针域置为空。注意：将节点3指向节点4后，中间的节点0就会找不到了，所以需要用一个中间变量来保存节点0，待指向完成后再将节点0的指针域指向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
25
26
27
| public static void main(String[] args) {
SinglyLinkedListNode head = LinkedListUtils.generateSinglyLinkedList();
LinkedListUtils.printLink(head);
SinglyLinkedListNode c = new SinglyLinkedListNode(0);
SinglyLinkedListNode cHead = head;
while (cHead.next != null) {
if (cHead.val == 3) {
c.next = cHead.next;
cHead.next = c;
}
cHead = cHead.next;
}
LinkedListUtils.printLink(head);
SinglyLinkedListNode dHead = head;
while (dHead.next != null) {
if (dHead.val == 3) {
SinglyLinkedListNode temp = dHead.next;
dHead.next = dHead.next.next;
temp.next = null;
}
dHead = dHead.next;
}
LinkedListUtils.printLink(head);
}
|
微信
