【数据结构Python描述】位置列表简介与Python版手工实现

文章目录

• 一、关于位置的描述
• • 1. 使用结点引用描述位置的弊端
  • 2. 使用类似编辑器光标描述位置
  • 3. 用于描述元素位置的代码抽象
• 二、位置列表的ADT
• • 1. 非修改类操作
  • 2. 修改类操作
  • 3. ADT功能期望
• 三、位置列表的实现
• • 1. 私有实用方法
  • • `_validate(p)`
    • `_node2pos(node)`
    • `_insert_between(e, predecessor, successor)`
  • 2. 非修改类方法
  • 3. 修改类方法
  • • `add_first(e)`
    • `add_last(e)`
    • `add_before(p, e)`
    • `add_after(p, e)`
    • `delete(p)`
    • `replace(p, e)`
• 四、位置列表实现测试

在文章【数据结构与算法Python描述】双向链表简介、Python实现及应用，我们基于双向链表实现了在头尾均可高效地插入或删除对象元素的双端队列，但实际生活中对于队列模型的要求更高，如：

• 一个处于队列中间的顾客可能觉得队列过长提前结束排队；
• 一个处于队列中间的游客可能正在代替朋友排队，等到朋友到达后出队然后其朋友插入该位置。

即我们希望实现一种可以在任意指定位置插入和删除元素的更一般性队列（以下简称“一般队列”），本文所要讨论的基于双向链表实现的位置列表（Positional List）就可以满足这一要求。

一、关于位置的描述

既然需要在任意指定位置插入和删除元素，那么首先需要进行位置的描述，第一反应可能是使用元素的整数索引来描述，但这存在以下问题：

• 对于使用链表作为对象元素存储容器的队列来说，使用整数索引需要从头遍历链表，故而效率很低；
• 在一些情况下使用整数索引来描述位置不准确，例如当对象元素前方发生了数次的插入和删除操作后，该对象元素的索引基本不可能是原先的数值。

1. 使用结点引用描述位置的弊端

通过文章【数据结构与算法Python描述】单向线性链表简介、Python实现及应用，我们已经知道链表的一大优势在于，如果知道某任意结点的引用，可以在该结点附近进行$O(1)$时间复杂度的插入和删除操作，因此你可能考虑使用结点的引用来描述位置。

实际上，文章【数据结构与算法Python描述】双向链表简介、Python实现及应用中的_DoublyLinkedBase类，其_insert_between和_delete_node两个方法的确接收结点引用作为参数，但在暴露给用户的接口中（这也是为什么_DoublyLinkedBase类及其上述两个方法都定义为非公有的缘故）这么做却有如下几个缺陷：

• 可能导致接口友好性降低，例如：用户使用_DoublyLinkedBase类中的_insert_between和_delete_node方法需要了解其内部使用了哨兵结点的技巧；
• 可能使得数据结构的鲁棒性降低，例如：用户向_DoublyLinkedBase类中的_insert_between和_delete_node方法传入不符合链表可接受格式的结点时，程序就会崩溃。

2. 使用类似编辑器光标描述位置

实际上，为了准确描述位置列表中对象元素的位置，可以从文本编辑器的光标找到启发：在如Word等文本编辑器中，可以将光标放在某任意位置，然后在该位置插入和删除字符。

因此，如果将文本编辑器的光标在代码中抽象成一个Position类，就可以用其实例对象描述位置列表中对象元素的位置。

3. 用于描述元素位置的代码抽象

为实现位置列表的ADT，首先需要定义用于描述元素位置的Position类，在位置Position类实例的内部，该实例维护了：

• 一个指向位置列表实例的引用，如此可以提高数据结构的鲁棒性，即当传入的位置实例不属于位置列表时，可以抛出适当的异常；
• 一个指向位置列表结点的引用，如此可以提高位置列表接口的友好性，因为这通过封装的方式隐藏了底层依然使用结点引用进行操作的事实。

除此之外，由于数据结构的使用者最关心的地方之一是通过位置获取位置列表中对象元素，因此Position类中还定义了一个element()方法，用以返回该位置对应的对象元素。

基于上述分析，下面给出Position类的完整代码：

class _Position:
    """代表对象元素在位置列表中位置的抽象"""

    def __init__(self, container, node):
        self.container = container
        self.node = node

    def element(self):
        """返回某一位置处的对象元素"""
        return self.node.element

    def __eq__(self, other):
        """如果两个Position实例代表了同一个位置，则返回True"""
        return type(other) is type(self) and other.node is self.node
    
    def __ne__(self, other):
        """如果两个Position的实例代表不同位置，则返回True"""
        return not (self == other)

二、位置列表的ADT

位置列表的ADT大致可以分为以下两个大类：

1. 非修改类操作

2. 修改类操作

对于上述所有接受位置p作为参数的方法，如果该位置不合法则抛出异常。

3. ADT功能期望

在后面实现位置列表ADT之前，为了让读者先对其中的各个方法有一个感性认识，下面给出了使用上述一系列方法对一个初始为空的位置列表进行一系列操作后的期望结果，其中$p_i$表示Position的实例对象：