Python数据结构与算法（2.6）——块状链表

• • 0. 学习目标
  • 1. 块状链表简介
  • • 1.1 块状链表介绍
    • 1.2 块状链表中结点类
    • 1.3 块状链表中块类
  • 2. 块状链表的实现
  • • 2.1 块状链表的初始化
    • 2.2 获取块状链表的长度
    • 2.3 读取指定位置元素
    • 2.4 查找指定元素
    • 2.5 在指定位置插入新结点
    • 2.6 删除指定位置元素
    • 2.7 块状链表的动态调整
    • 2.8 其它一些有用的操作
  • 3. 块状链表应用
  • • 3.1 块状链表应用示例
  • 相关链接

0. 学习目标

块状链表 (Unrolled Linked Lists) 是单链表的变体，其降低了访问单链表中指定位置元素的时间复杂度，块状链表中的每个块结点(简称块)中存储了多个数据元素结点，每个块中的结点使用一个循环链表进行连接。本节讲介绍块状链表的基本概念并实现其基本操作。
通过本节学习，应掌握以下内容：

• 块状链表的基本概念及实现方法
• 块状链表基本操作的实现及时间复杂度
• 利用块状链表的基本操作实现复杂算法

1. 块状链表简介

1.1 块状链表介绍

与顺序表相比，链表的最大优势之一是在插入或删除元素并不需要移动数据元素位置，因此进行插入和删除操作更加高效，但是访问链表元素的时间复杂度为 O ( n ) O(n) O(n)，为了提高数据访问操作的效率，单链表有一个简单的变体，称为块状链表。块状链表的每个结点(为了与数据元素结点进行区别，以下我们将其称为块)中都存储多个数据元素结点，在每个块中使用循环链表连接块内的数据元素结点(以下将数据元素结点简称为结点)，块状链表示意图如下所示：

假设块状链表中的结点数量不超过 n n n 个，那么除了最后一个块之外，所有每个块中都包含 ⌈ n ⌉ \lceil \sqrt n \rceil ⌈n ​⌉ 个元素(其中 ⌈ ⌉ \lceil \rceil ⌈⌉ 表示向上取整)。 因此，链表中块的数量不会超过 ⌊ n ⌋ \lfloor \sqrt n \rfloor ⌊n ​⌋ 个(其中 ⌊ ⌋ \lfloor \rfloor ⌊⌋ 表示向下取整)。

1.2 块状链表中结点类

块状链表中的结点与单链表中的结点并无太大差别，我们可以直接使用单链表中的结点类，但为了更快的找到块内循环链表的尾结点(时间复杂度为 O ( 1 ) O(1) O(1)，用以快速执行块状链表的一些操作)，我们使用前驱指针来代替后继指针：

结点类实现如下：

class Node:
    def __init__(self, data=None):
        self.data = data
        self.previous = None
    
    def __str__(self):
        return str(self.data)

1.3 块状链表中块类

每个块类中都包含一个使用上述结点的单向循环链表，因此在此类中还需要包含一些循环链表的基本操作；同时每个块还包括一个指向下一个块的指针 next：

Note：从上图可以看到块中循环链表不带头结点，这样做的原因是令头指针指向链表的第一个结点，获取第一个结点的时间复杂度为 O ( 1 ) O(1) O(1)，可以方便块状链表的一些操作，接下来也可以看到不带头结点的链表与带有头结点的链表操作实现的不同之处。

1.3.1 块的初始化

块的创建需要初始化块的头指针 block_head 以及块的后继指针 next ：

class LinkedBlock:
    def __init__(self, data=None):
        self.block_head = None
        self.next = None
        self.node_count = 0

其中 next 指针指向下一个块，node_count 用于记录块中的节点数。

1.3.2 获取块中链表长度

获取块中链表长度只需要重载 __len__ 返回 node_count 属性即可：

    def __len__(self):
        return self.node_count

1.3.3 获取块中链表指定位置元素

由于使用的是前驱链，遍历块内链表时需要从链尾开始，为了获取元素在链表中的真实序号，我们需要首先获取链表长度，并在每次遍历一个元素后减 1，而位置 0 处的元素我们也可以在遍历开始时获得：

    def __getitem__(self, index):
        count = self.node_count
        current = self.block_head
        if index != 0:
            while count > index:
                current = current.previous
                count -= 1
        return current.data

同样，我们也可以修改块内链表指定位置元素：

    def __setitem__(self, index, value):
        count = self.node_count
        current = self.block_head
        if index != 0:
            while count > index:
                current = current.previous
                count -= 1
        current.data = value

1.3.4 删除块中链表指定位置元素

由于没有头结点，删除块中链表指定位置元素需要分为以下两种情况：

• 要删除的结点是第一个结点，即头指针指向的结点
  • 遍历得到第一个结点的后继节点 tmp;
  • 令 tmp 的前驱结点指向第一个结点的前驱结点；
  • 令头指针指向 tmp 结点即可
  • 如果链表中只有一个结点，那么只需要删除该结点，并令头结点指向 None

• 要删除的结点不是第一个结点
  • 遍历到待删除位置结点 current；
  • 将待删除结点的后继节点 next 的 previous 指针指向待删除结点的前驱结点。

    def __delitem__(self, index):
        count = self.node_count
        current = self.block_head
        if index != 0:
            while count > index:
                next_node = current
                current = current.previous
                count -= 1
            next_node.previous = current.previous
        else:
            if self.node_count == 1:
                # 如果链表中只有一个结点
                self.block_head = None
            else:
                tmp = current
                while tmp.previous != self.block_head:
                    tmp = tmp.previous
                tmp.previous = self.block_head.previous
                self.block_head = tmp
        self.node_count -= 1
        del current

1.3.5 在块中链表指定位置插入结点

与删除操作类似，插入结点时也需要分为两种情况：

• 插入链表头部
  • 如果链表为空，只需要将链表头指针指向待插结点，然后将其 previous 指针指向自身；
  • 否则，将当前链表的第一个结点的 previous 指针指向待插结点，待插结点的 previous 指针指向链尾结点，并将链表头指针指向待插结点。

• 插入链表头部以外位置
  • 遍历链表找到插入位置结点 current；
  • 将待插结点的 previous 指针指向 current 结点的前驱结点；
  • 将 current 结点的 previous 指针指向待插结点。

    def insert_first(self, node):
        if self.node_count == 0:
            # 链表为空
            node.previous = node
        else:
            node.previous = self.block_head.previous
            self.block_head.previous = node
        self.block_head = node
        self.node_count += 1 
    def insert(self, index, node):
        if index == 0:
            # 在链表头插入结点
            self.insert_first(node)
        else:
            # 在其它位置插入节点
            count = self.node_count
            current = self.block_head
            while count > index:
                # 查找插入位置
                current = current.previous
                count -= 1
            # 插入新结点
            node.previous = current.previous
            current.previous = node
            self.node_count += 1

由于第一个结点的 previous 指针指向链尾结点，因此可以方便的实现 append 函数用于追加元素：

    def append(self, node):
        if self.node_count == 0:
            node.previous = node
            self.block_head = node
        else:
            node.previous = self.block_head.previous
            self.block_head.previous = node        
        self.node_count += 1

1.3.6 打印块中链表

使用 str 函数调用对象上的 __str__ 方法可以创建适合打印的字符串表示：

    def __str__(self):
        """使用|作为块与块之间的分割符"""
        s = "|"
        if self.block_head:
            current = self.block_head.previous
            count = 0
            while current != self.block_head:
                count += 1
                s = str(current) + s
                current = current.previous
                if count < self.node_count:
                    s = '<--' + s 
            s = str(self.block_head)  + s
        s = '|' + s
        return s

2. 块状链表的实现

块状链表中的块以单链表的形式进行连接，除了最后一个块，和第一个块外，都有一个前驱块和一个后继块。

2.1 块状链表的初始化

块状链表的初始化，首先实例化一个块，然后将链表的头指针 list_head 指向它，并初始化链表长度和每个块容纳的最大结点数。

import math

class UnrolledLinkedList:
    def __init__(self):
        block = LinkedBlock()
        self.list_head = block
        self.length = 0
        self.block_size = 4

其中 length 表示链表长度，block_size 表示每个块能容纳的最大结点数了，由于每个块中的节点数为 ⌈ n ⌉ \lceil \sqrt n \rceil ⌈n ​⌉，因此 block_size 的大小会随着链表长度的变化动态改变。

2.2 获取块状链表的长度

重载 __len__ 从对象返回 length 的值用于求取块状链表长度：

    def __len__(self):
        return self.length

2.3 读取指定位置元素

在块状链表中，读取指定位置元素的时间复杂度为 O ( n ) O(\sqrt n) O(n ​)：

1. 首先查找包含第 i i i 个结点的块，即第 ⌈ k ⌈ n ⌉ ⌉ \lceil \frac k {\lceil \sqrt n \rceil} \rceil ⌈⌈n ​⌉k​⌉ 个块，其时间复杂度为 O ( n ) O(\sqrt n) O(n ​)，因为我们可以通过遍历不超过 ( n ) (\sqrt n) (n ​) 个块找到它；
2. 在该块中找到第 k % ⌈ n ⌉ k \% \lceil \sqrt n\rceil k%⌈n ​⌉ 个结点，其中 % \% % 表示求模运算；此步骤的时间复杂度同样为 ( n ) (\sqrt n) (n ​)，因为单个块中的节点数不超过 ⌈ n ⌉ \lceil \sqrt n \rceil ⌈n ​⌉。

    def __getitem__(self, index):
        if index > self.length - 1 or index < 0:
            raise IndexError("UnrolledLinkedList assignment index out of range")
        else:
            # 查找块号
            block_size = self.block_size
            i = (index + block_size) // block_size
            current_b = self.list_head
            i -= 1
            while i > 0:
                current_b = current_b.next
                i -= 1
            # 查找结点
            j = index % block_size
            value = current_b[j]
            return value

类似的，我们也可以实现修改指定位置元素的操作，只需要重载 __setitem__ 操作，它的时间复杂度同样为 O ( n ) O(\sqrt n) O(n ​)：

    def __setitem__(self, index, value):
        if index > self.length - 1 or index < 0:
            raise IndexError("UnrolledLinkedList assignment index out of range")
        else:
            # 查找块号
            block_size = self.block_size
            i = (index + block_size) // block_size
            current_b = self.list_head
            i -= 1
            while i > 0:
                current_b = current_b.next
                i -= 1
            # 查找结点
            j = index % block_size
            current_b[j] = value

2.4 查找指定元素

查找指定元素的操作与其它链表类似，遍历整个链表，如果在链表中发现与指定元素相同的数据节点，返回其在链表中的序号，此操作的时间复杂度为 O ( n ) O(n) O(n)：

    def locate(self, value):
        current = self.list_head
        count = 0
        while current:
            index = current.locate(value)
            if index >= 0:
                count += index
                return count
            else:
                count = count + self.block_size + 1
                current = current.next
        raise ValueError("{} is not in sequential list".format(value))

2.5 在指定位置插入新结点

假设我们在位置 index 处插入一个结点 node，并且 node 应该放在第 i i i 个块中，那么第 i i i 个块中的结点和第 i i i 个块之后的块中的结点必须进行移位操作——向链表尾部移动，以保证每个块中的结点数不超过 ⌈ n ⌉ \lceil \sqrt n \rceil ⌈n ​⌉，如果链表的最后一个块空间不足——结点数超过 ⌈ n ⌉ \lceil \sqrt n \rceil ⌈n ​⌉，则需要在尾部添加一个新块。完成上述操作后，可能还需要对块状链表进行动态调整，以满足块状链表规则。

    def insert(self, index, node):
        if index > self.length or index < 0:
            raise IndexError("UnrolledLinkedList assignment index out of range")
        else:
            # 查找块号
            block_size = self.block_size
            i = (index + block_size - 1) // block_size
            current_b = self.list_head
            i -= 1
            while i > 0:
                current_b = current_b.next
                i -= 1
            # 查找结点
            j = index % block_size
            if index > 0 and j == 0:
                j = block_size
            current_b.insert(j, node)
            self.length += 1
            if current_b.node_count > self.block_size:
                # 移位
                self.shift(current_b)
            # 链表动态调整
            self.balance()

插入操作本身很容易理解，查找到对应块后调用块类的插入操作即可；接下来我们详细介绍移位操作：

1. 使用指针 tmp 保存当前块 current_b 中链表的尾结点，并将第一个结点的 previous 指针指向尾结点的前驱结点；

2. 将 tmp 的 previous 指针指向当前块的后继块 current 中链表的尾结点，并将 current 的第一个结点的 previous 指针指向 tmp，将 current 的头指针指向 tmp；

3. 按照上述步骤完成后续所有块的移位操作。

    def shift(self, current_b):
        """移位操作"""
        current = current_b
        while(current_b.node_count > self.block_size):
            if (current_b.next == None):
                current_b.next = LinkedBlock()
                current = current_b.next
                tmp = current_b.block_head.previous
                current_b.block_head.previous = tmp.previous
                current.append(tmp)
                current_b.node_count -= 1
                current_b = current
            else:
                current = current_b.next
                tmp = current_b.block_head.previous
                current_b.block_head.previous = tmp.previous
                current.insert(0, tmp)
                current_b.node_count -= 1
                current_b = current

每个移位操作，包括从块中循环链表的尾部删除一个结点，并在后继块中将此结点插入到循环链表的头部，时间复杂度为 O ( 1 ) O(1) O(1)，由于最多有 O ( n ) O(\sqrt n) O(n ​) 个块，因此块状链表插入操作的时间复杂度为 O ( n ) O(\sqrt n) O(n ​)。

2.6 删除指定位置元素

假设我们要删除位置 index 处结点 node，并且 node 应该在第 i i i 个块中，那么第 i i i 个块中的结点和第 i i i 个块之后的块中的结点必须向链表头部移动，以保证每个块中的结点数量，如果链表的最后一个块空间没有结点，则需要删除该块。完成上述操作后，可能还需要对块状链表进行动态调整，以满足块状链表规则。

    def __delitem__(self, index):
        if index > self.length - 1 or index < 0:
            raise IndexError("UnrolledLinkedList assignment index out of range")
        else:
            # 查找块号
            block_size = self.block_size
            i = (index + block_size) // block_size
            current_b = self.list_head
            i -= 1
            while i > 0:
                prev = current_b
                current_b = current_b.next
                i -= 1
            # 查找结点
            j = index % block_size
            self.length -= 1
            del current_b[j]
            if current_b.next != None:
                # 块的填充
                self.fill(current_b)
            if current_b.node_count == 0:
                prev.next = None
            self.balance()

块的填充操作与移位操作类似：

    def fill(self, current_b):
        """填充操作，结点向链表头部移动"""
        current = current_b
        while(current_b.next != None):
            current = current_b.next
            tmp = current.block_head
            new_head = current.block_head
            while new_head.previous != current.block_head:
                new_head = new_head.previous
            new_head.previous = tmp.previous
            current.block_head = new_head
            current.node_count -= 1
            current_b.append(tmp)
            if current.node_count == 0:
                current_b.next = None
            current_b = current

2.7 块状链表的动态调整

我们已经知道块状链表的块的最大容量会随着链表长度的变化动态改变，这是为了：(1) 保证块的数量不超过 n \sqrt n n ​；(2) 每个块中的结点数都不超过 ⌈ n ⌉ \lceil \sqrt n \rceil ⌈n ​⌉。为了维持块状链表的稳定性，需要对块状链表的动态调整，其过程类似与移位操作，具体的实现可以参考《块状链表的动态调整》中的 balance 函数。

2.8 其它一些有用的操作

2.8.1 链表元素输出操作

将块状链表转换为字符串以便进行打印，使用 str 函数调用对象上的 __str__ 方法可以创建适合打印的字符串表示：

    def __str__(self):
        s = "["
        current = self.list_head
        while current.next:
            s += str(current)
            current = current.next
            s += '-->'
        s += str(current)
        s += "]"
        return s

2.7.2 在链表尾部追加新结点

为了方便的在链表尾部追加新元素，可以实现函数 append：

    def append(self, node):
        block_size = self.block_size
        # 计算当前块数
        i = (self.length + block_size - 1) // block_size
        current_b = self.list_head
        i -= 1
        while i > 0:
            current_b = current_b.next
            i -= 1
        # 追加结点
        current_b.append(node)
        self.length += 1
        if current_b.node_count > self.block_size:
            self.shift(current_b)
        self.balance()

此算法的时间复杂度为 O ( n ) O(\sqrt n) O(n ​)。

3. 块状链表应用

接下来，我们测试上述实现的块状链表，以验证操作的有效性。

3.1 块状链表应用示例

首先初始化一个链表 ullist，并在其中追加若干元素：

ullist = UnrolledLinkedList()
# 在链表末尾追加元素
for i in range(15):
    ullist.append(Node(i+15))
# 在指定位置插入元素
ullist.insert(0, Node(0))

我们可以直接打印链表中的数据元素、链表长度等信息：

print('双向链表 sllist 为：', dllist)
print('双向链表 sllist 长度为：', len(dllist))
print('双向链表 sllist 第0个元素为：', dllist[0])
# 修改数据元素
dllist[0] = 'pear'
del(dllist[3])
print('双向修改链表 sllist 数据后：', dllist)

以上代码输出如下：

块状链表 ullist 为： [|0<--15<--16<--17|-->|18<--19<--20<--21|-->|22<--23<--24<--25|-->|26<--27<--28<--29|]
块状链表 ullist 长度为： 16
块状链表 ullist 第0个元素为： 0
修改块状链表 ullist 数据后：  [|0<--1<--16<--17|-->|18<--19<--20<--21|-->|22<--23<--24<--25|-->|26<--27<--28<--29|]

接下来，我们将演示在指定位置添加/删除元素、以及如何查找指定元素等：

ullist.insert(2, Node(2))
print('在位置 2 添加 2 后块状链表链表 ullist 数据：', ullist)
del(ullist[3])
print('删除位置 3 处元素后块状链表 ullist 数据：', ullist)
print('17 在块状链表 ullist 中的索引为：', ullist.locate(17))

以上代码输出如下，观察以下输出可以看到块状链表的动态调整：

在位置 2 添加 2 后双向链表链表 ullist 数据： [|0<--1<--2<--16<--17|-->|18<--19<--20<--21<--22|-->|23<--24<--25<--26<--27|-->|28<--29|]
删除位置 3 处元素后双向链表 ullist 数据： [|0<--1<--2<--17|-->|18<--19<--20<--21|-->|22<--23<--24<--25|-->|26<--27<--28<--29|]
17 在双向链表 ullist 中的索引为： 3

相关链接

线性表基本概念
单链表及其操作实现
循环链表及其操作实现
块状链表的动态调整