数据结构与算法 -- 链表

链表

单链表

  1. 数组需要一块连续的内存空间来存储,而链表并不需要,而是通过指针将一组零散的内存块串联起来
  2. 为了将所有结点串起来,每个链表的结点除了存储数据之外,还需要记录下一个结点的地址
    • 将记录下个结点地址的指针称为后继指针next
  3. 有两个结点比较特殊,分别是第一个结点和第二个结点,习惯性地称为头结点尾结点
    • 头结点用来记录链表的基地址
    • 尾结点的指针指向的不是下一个结点,而是指向一个空地址NULL,表示这是链表上的最后一个结点

插入 + 删除

  1. 数组的插入和删除操作,为了保持内存数据的连续性,需要做大量的数据搬移,时间复杂度为O(n)
  2. 链表的插入和删除操作,并不需要为了保持内存的连续性而搬移结点,因为链表的存储空间本身就不是连续的
    • 因此在链表中插入和删除一个数据是非常快速的,只需要考虑相邻结点的指针变化,时间复杂度为O(1)

随机访问

  1. 链表中的数据并非连续存储,无法像数组那样,根据首地址下标,通过寻址公式直接计算出对应的内存地址
  2. 而是需要根据指针一个结点一个结点地依次遍历,直到找到相应的结点,时间复杂度为O(n)

循环链表

  1. 循环链表是一种特殊的单链表,单链表的尾结点指向空地址NULL,而循环链表的尾结点指针指向链表的头结点
  2. 与单链表相比,循环链表的优点是从链尾到链头比较方便,当要处理的数据具有环型结构特点时,适合采用循环链表

双向链表

  1. 单向链表只有一个方向,结点只有一个后继指针next指向后面的结点
  2. 双向链表支持两个方向,每个结点除了有后继指针next指向后面的结点,还有前驱结点prev指向前面的结点
  3. 双向链表需要额外的空间来储存后继结点前驱结点的地址,比单链表占用更多的内存空间,但支持双向遍历更加灵活
  4. 双向链表查找前驱结点的时间复杂度为O(1),在某些场景下,双向链表的插入和删除操作要比单链表简单高效
  5. 在实际的软件开发中,虽然双向链表占用更多的内存,但还是比单链表有更广的应用,体现了空间换时间的设计思想

插入 + 删除

  1. 删除结点中“值等于某个给定值”的结点
    • 不管单链表还是双向链表,都需要从头结点开始一个一个依次遍历对比,直到找到的值等于给定值的结点
    • 单纯的删除操作的时间复杂度为O(1),但遍历查找的时间复杂度为O(n),因此总的时间复杂度为O(1)
  2. 删除给定指针指向的结点
    • 此时已经找到要删除的结点,但删除某个结点需要知道其前驱结点,而单链表并不支持直接获取前驱结点
      • 所以,单链表为了找到前驱结点,还是需要从头结点开始遍历链表
      • 而双向链表中的结点已经保存了前驱结点的指针,不需要像单链表那样遍历
    • 在这种场景下,使用单链表的时间复杂度为O(n),而使用双向链表的时间复杂度为O(1)
  3. 同理,在链表中某个指定结点的前面插入一个结点,使用双向链表的时间复杂度为O(1),而使用单链表的时间复杂度O(1)

查找

  1. 对于一个有序链表,双向链表按值查询的效率也要比单链表要高一些
  2. 可以记录上次查找的位置,每次查询时,根据情况决定往前查找还是往后查找,平均只需要查找一半的数据

对比数组

时间复杂度

操作 数组 链表
插入/删除 O(n) O(1)
随机访问 O(1) O(n)

CPU缓存

  1. 数组使用连续的内存空间,可以利用CPU的缓存机制,预读数组中的数据,访问效率更高
  2. 链表在内存中并不是连续存储,对CPU缓存不友好,没办法有效预读

固定大小

  1. 数组的缺点是大小固定,一经声明就要占用整块连续内存空间
    • 如果声明过大,系统就没有足够的连续内存空间来分配,导致内存不足
    • 如果声明过小,就有可能出现不够用的情况,这时只能再申请一个更大的内存空间,把原数组拷贝过去,非常耗时
  2. 链表本身没有大小的限制,天然支持动态扩容,这是与数组最大的区别
  3. 如果程序对内存大小非常敏感,数组会是更优的选择

LRU缓存

  1. 维护一个有序单链表,越靠近尾部的结点是越早之前访问的,当有一个新的数据被访问时,从链表头开始遍历链表
  2. 如果此数据之前已经被缓存在链表中,遍历得到这个数据对应的结点,并将其从原来的位置删除,然后再插入到链表的头部
  3. 如果此数据没有缓存在链表中,分为两种情况
    • 如果此时缓存未满,则将此结点直接插入到链表头部
    • 如果此时缓存已满,则将链表尾结点删除,并将新结点插入到链表头部
  4. 不管缓存有没有满,都需要遍历链表,时间复杂度为O(n)

技巧

哨兵

插入

单链表中,在结点p后插入一个新节点

1
2
3
// p有可能为null,例如空链表时,p == head == null
newNode.setNext(p.getNext());
p.setNext(newNode);

如果要插入第一个结点(空链表),上面代码就不通用了,需要特殊处理,head表示链表头结点

1
2
3
if (head == null) {
head = newNode;
}

删除

单链表中,删除结点p的后继结点

1
2
// p.getNext()有可能为null,例如链表只有一个结点时,p == head
p.setNext(p.getNext().getNext());

如果要删除最后一个结点(链表中只有一个结点),上面代码也不通用了,需要特殊处理

1
2
3
if (head.getNext() == null) {
head = null;
}

哨兵

  1. 针对链表的插入和删除操作,需要对插入第一个节点删除最后一个结点的情况进行特殊处理不简洁且容易出错
  2. 哨兵用于解决边界问题,不直接参与业务逻辑
  3. 引入哨兵结点(不存储数据),不管链表是不是为空,head指针都会一直指向哨兵结点,有哨兵结点的链表叫作带头链表
  4. 引入哨兵结点后,可以统一代码实现

边界条件

  1. 链表为
  2. 链表只包含1个结点
  3. 链表只包含2个结点
  4. 处理头结点尾结点

常见链表操作

1
2
3
4
5
6
7
@Data
@NoArgsConstructor
@AllArgsConstructor
public class Node<T> {
private T data;
private Node<T> next;
}
1
2
3
4
5
6
7
@Data
@NoArgsConstructor
@AllArgsConstructor
public class MyLinkedList<T> {
// 哨兵结点
private Node<T> head = new Node<>();
}

单链表反转

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
public void reverse() {
Node<T> prev = head;
Node<T> cur = head.getNext();
Node<T> next;
while (cur != null) {
// 先保留next
next = cur.getNext();

if (cur == head.getNext()) {
// 第一个结点
cur.setNext(null);
} else {
cur.setNext(prev);
}

if (next == null) {
// 最后一个结点
head.setNext(cur);
}

prev = cur;
cur = next;
}
}

检测链表中的环

1
2
3
4
5
6
7
8
9
10
11
12
13
public boolean existRing() {
Node<T> fast = head;
Node<T> slow = head;

while (fast != null && fast.getNext() != null) {
fast = fast.getNext().getNext();
slow = slow.getNext();
if (slow == fast) {
return true;
}
}
return false;
}

合并两个有序链表

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
public static <T extends Comparable> MyLinkedList<T> merge(MyLinkedList<T> l1, MyLinkedList<T> l2) {
Node<T> head = new Node<>();
Node<T> cur = head;
Node<T> cur1 = l1.getHead().getNext();
Node<T> cur2 = l2.getHead().getNext();

while (cur1 != null || cur2 != null) {
// 遍历完l1,只能遍历l2
if (cur1 == null) {
cur.setNext(cur2);
cur = cur.getNext();
cur2 = cur2.getNext();
continue;
}
// 遍历完l2,只能遍历l1
if (cur2 == null) {
cur.setNext(cur1);
cur = cur.getNext();
cur1 = cur1.getNext();
continue;
}
// l1和l2均未遍历完,比较大小
if (cur1.getData().compareTo(cur2.getData()) < 0) {
cur.setNext(cur1);
cur = cur.getNext();
cur1 = cur1.getNext();
} else {
cur.setNext(cur2);
cur = cur.getNext();
cur2 = cur2.getNext();
}
}

return new MyLinkedList<>(head);
}

删除链表倒数第n个结点

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
public MyLinkedList<T> deleteItemReverse(int n) {
if (n <= 0) {
return this;
}

// 先拉开差距
Node<T> first = head;
Node<T> second = head;
for (int i = 0; i < n; i++) {
second = second.getNext();
if (second == null) {
// 链表不够n格结点
return this;
}
}

// 遍历到尾结点
while (second.getNext() != null) {
first = first.getNext();
second = second.getNext();
}

// 删除
first.setNext(first.getNext().getNext());
return this;
}

查找链表的中间结点

1
2
3
4
5
6
7
8
9
10
11
public T findMiddle() {
Node<T> fast = head;
Node<T> slow = head;

while (fast != null && fast.getNext() != null) {
fast = fast.getNext().getNext();
slow = slow.getNext();
}

return slow.getData();
}
0%