线性-链表

定义

链表（Linked List）是一种线性表，但是并不会按线性的顺序存储数据，而是在每一个节点里存到下一个节点或上一个节点的指针(Pointer)。

  • 访问：O(n)

  • 增删：O(1)

特点

  1. 增删O(1)，查找O(n)

  2. 不用像数组那样预先分配存储空间的大小

  3. 无法进行回溯操作，如不能从尾节点倒序访问头节点

空间利用

  • 不用预先知道数据大小，充分利用内存空间，可灵活管理内存

  • 增加节点的指针域，空间开销较大

分类

  1. 单链表

  2. 双链表

  3. 循环链表

  4. 块状链表

存储结构

  1. 共享存储空间

    • 优点：不需要提前分配内存，可存储无限多的内容

    • 缺点：内容分散，不利于调试

  2. 独立存储空间（数组模拟链表）：用表示在数组中的位置的下标索引代替了指向内存地址的指针，这种下标索引其实也是逻辑上的指针

    • 优点：可以自动获得一个附加数据——唯一的编号，并且方便调试

    • 缺点：不能动态分配内容，但是可以在上面加一层块状链表用来分配内存

用途

用于组织检索较少，而删除、添加、遍历较多的数据

应用与扩展

  • 其他数据结构的基础：堆、栈、队列

  • 基于多个线性链表：跳表

  • 非线性链表：树、图

单链表

定义

包含两个域，一个信息域和一个指针域。节点的指针域指向链表中的下一个节点，而最后一个节点则指向一个空值。

访问

从一个节点开始（如root节点），通过指针域每次访问下一个节点，一直访问到需要的位置。也可以直接把一个节点的位置（指针）存储起来，以便下一次直接从该节点开始访问。

变形

最后一个节点指针指向头节点，可构成循环链表。或者在逻辑上实现：当访问到最后一个节点时，手动跳转到头节点。

题型

  1. 单链表反转

单链表反转

# @lc code=start
# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, x):
#         self.val = x
#         self.next = None

class Solution:
    def reverseList(self, head: ListNode) -> ListNode:
        prev = None
        curr = head

        while curr:
            next = curr.next
            curr.next = prev
            prev = curr
            curr = next

        return prev

双链表

定义

每个节点有两个指针：一个指向前一个节点，（当此指针为第一个指针时，指向空值或者空列表）；而另一个指向下一个节点，（当此指针为最后一个指针时，指向空值或者空列表）。

访问

双链表不仅有指向后一个节点的指针，还有指向前一个节点的指针。这样可以从任何一个节点访问前一个节点，当然也可以访问后一个节点，以至整个链表。

变形

尾节点指向下一个节点的指针指向头节点，头节点指向前一个节点的指针指向尾节点，构成循环链表。

题型

  1. 回文链表

循环链表

定义

首节点和末节点被连接在一起。第一个节点之前就是最后一个节点，反之亦然。

题型

  1. 判断链表是否有环

  2. 找到环中第一个节点

块状链表

定义

块状链表本身是一个链表，但是链表储存的并不是一般的数据，而是由这些数据组成的顺序表。每一个块状链表的节点，也就是顺序表，可以被叫做一个块。

各操作的时间复杂度为O(sqrt(n))

操作

  1. 定位：先定位元素所在的链表节点，然后再定位该元素在数组中的位置。

  2. 分裂：将某个链表节点分裂成两个节点。

  3. 插入：首先定位要插入的位置，然后将所在节点分裂成两个节点，并将数据放到第一个节点的末尾。 如果要插入的是一大块数据，首先要将数据切成多个block（每个block对应一个块状链表的一个节点）并将这些block链起来，然后将它们插入那两个节点之间。

  4. 删除：首先定位删除元素的位置，然后按照数组删除元素的方法删除该数据。如果删除一大块数据，首先要定位数据块首元素和末元素所在的位置，然后分别将它们所在的节点分裂成两个节点，最后删除首元素和末元素之间的节点即可

核心

确定链表长度和每个节点的数组长度，以及怎么保证这个长度值？设块状链表中元素总个数为X，链表长度为n，每个节点中数据长度为m，则当m=n=sqrt(X)时，可保证m和n同时最小，此时各种操作的时间复杂度最低。在实际应用时，需维持块状链表的每个节点大小在[sqrt(n)/2, 2*sqrt(n)]，否则，块状链表会退化。维护方法是，适当的时候，对节点进行合并与分裂（维护本身不会使复杂度增加）

参考

  1. WIKI

  2. 单链表常见面试题

  3. 块状链表

  4. OI-WIKI

Previous动态规划Next排序

Last updated