数据结构与算法: 链表

本系列文章是在学习数据结构和算法时记录的学习笔记，概念讲解部分主要引用自《极客时间》的相关专栏，代码实践部分由本人采用 Python 实现。

版权归极客时间所有。

概念

链表（Linked List）与数组一样，也是一种线性表数据结构，不过它不用一组连续的内存空间，而是通过指针的形式，将零散的内存块串联起来。

每一个内存块称为链表的 节点 。为了将所有的结点串起来，每个链表的结点除了存储数据之外，还需要记录链上的相邻结点的地址，记录下一个节点的指针叫作 后继指针 next ，记录上一个节点的指针叫作 前驱指针 previous 。

最常见的链表结构有：单链表、双向链表和循环链表。

单链表（Linked List）

单链表的特点：

• 节点存储内容：当前节点的数据 data 、后继指针 next
• 头结点：记录链表 基地址 ，有了它，我们就可以遍历得到整条链表
• 两个尾结点：后继指针指向 空地址NULL ，遍历时作为尾结点的判断条件

双向链表（Doubly Linked List）

双向链表的特点：

• 节点存储内容：当前节点的数据 data 、后继指针 next 、前驱指针 previous ，相比于单链表，双向链表会占用更多的内存空间
• 头结点：记录链表 基地址 ，前驱指针指向 空地址NULL ，有了它，我们就可以遍历得到整条链表
• 尾结点：后继指针指向 空地址NULL ，遍历时作为尾结点的判断条件

复杂度分析

相比于数组，链表主要有以下优势：

• 改善“插入”和“删除”的效率
• 不受内存连续性的限制，可以存储大量元素，例如 blockchain

对应的弊端就是，随机访问效率较低，需要根据指针一个结点一个结点地依次遍历，直到找到相应的结点。

单链表和双向链表在随机访问、查询操作时的时间复杂度相同：

• Access: O(n)
• Search: O(n)

在对链表进行“删除”操作时，存在两种情况：

（1）删除结点中“值等于某个给定值”的结点 q

（2）删除给定指针指向的结点 q

对于第一种情况，不管是单链表还是双向链表，为了查找到值等于给定值的结点，都需要从头结点开始一个一个依次遍历对比，直到找到值等于给定值的结点，然后再进行删除操作。查询时间复杂度 O(n)，删除时间复杂度 O(1)，因此总体时间复杂度为 O(1)。

对于第二种情况，已经确定了要删除的结点，但是删除某个结点 q 需要知道其前驱节点，因此在此情况下单链表和双向链表就存在较大差异：

• 单链表：需要从头节点依次遍历，找到 q 节点的前驱节点 p（p->next = q）；查询时间复杂度 O(n)，删除时间复杂度 O(1)，因此总体时间复杂度为 O(n)。
• 双向链表：可直接获取 q 节点的前驱节点 p（q->previous）；查询时间复杂度 O(1)，删除时间复杂度 O(1)，因此总体时间复杂度为 O(n)。

删除的伪代码：

// 单链表
while p->next {
  if (p->next = q) {
    break;
  }
  p = p->next;
}
p->next = q->next;
q->next = null;

// 双向链表
q->previous->next = q->next;
q->next = null;

在对链表进行“插入”操作时，比如在链表的某个指定结点（q）前面插入一个结点（x），双向链表也有更大的优势：

• 单链表：需要从头节点依次遍历，找到 q 节点的前驱节点 p（p->next = q）；查询时间复杂度 O(n)，插入时间复杂度 O(1)，因此总体时间复杂度为 O(n)。
• 双向链表：可直接获取 q 节点的前驱节点 p（q->previous）；查询时间复杂度 O(1)，插入时间复杂度 O(1)，因此总体时间复杂度为 O(1)。

插入的伪代码：

// 单链表
while p->next {
  if (p->next = q) {
    break;
  }
  p = p->next;
}
p->next = x;
x->next = q;

// 双向链表
q->previous->next = x;
x->next = q;

使用 Python 实现链表数据结构

在 Python 语言中没有链表的数据结构，需要模拟进行实现。

定义链表

定义单链表：

class Node(object):
    def __init__(self, data, next_node=None):
        self.data = data
        self.next_node = next_node

定义双向链表：

class BiNode(object):
    def __init__(self, data, previous_node=None, next_node=None):
        self.data = data
        self.previous_node = previous_node
        self.next_node = next_node

单链表常用操作

创建单链表（5->4->3->2->1）：

head = None

for data in range(1,6):
    head = Node(data, head)

遍历单链表：

# 输出 5、4、3、2、1
# head 当前对应节点 5
while head is not None:
    print(head.data)
    head = head.next_node

# 遍历完成后，head is None，链表结构消失

# 若需要在遍历完成仍保留链表结构，则需使用一个临时变量
probe = head
while probe is not None:
    print(probe.data)
    probe = probe.next_node

# 遍历完成后，probe is None，head 当前对应节点 5

插入单链表，将 20 插入到 3 和 2 之间：

# head 当前对应节点 5
probe = head
while probe is not None:
    if probe.data == 3:
        new_node = Node(20, None)
        new_node.next_node = probe.next_node
        probe.next_node = new_node
        break
    else:
        probe = probe.next_node

双向链表常用操作

实战

典型问题

1、实现单链表、循环链表、双向链表，支持增删操作

2、实现单链表反转

3、实现两个有序的链表合并为一个有序链表

4、实现求链表的中间结点