Python 与数据结构 —— 链表及其应用

发表于 | 分类于 | | 阅读次数:
字数统计: 6.8k | 阅读时长 ≈ 0:07

list 的局限

Python 的 list 类是经过高度优化的，在需要存储数据时是一个很优秀的选择。但仍有以下几点需要注意的劣势：

  • 动态数组的长度通常会大于实际存储的元素的数量
  • 当存储的元素数量不断增长时，动态数组扩展边界的性能较低
  • 靠近数组中间位置的插入和删除操作性能相对较低

基于数组的序列和链表都能够以特定顺序存储元素，但是各自实现的方式差异很大。
数组提供了一种更为“中心化”的表示方式，用一大段连续的内存存储多个元素的引用；而链表则更为“分散化”，将每个元素表示为轻量的节点（Node），每个节点都维护着包含元素本身及一个或多个相邻节点的引用，通过引用将多个节点最终连接成线性顺序的序列。

链表无法高效地通过数字索引读取其中元素的值，但是可以避免前面提到过的基于数组的序列的三点劣势。

单链表

单链表是最简单的一种形式，组成线性序列的每个节点都包含元素本身及下一个节点的引用。
singly linked list

第一个和最后一个节点分别称为 head 和 tail。从 head 节点开始，跟随每个节点的 next 引用从首节点一直移动到尾部节点的过程，即为链表遍历。

向链表头部插入新元素的步骤：

  • 创建包含新元素的新的节点对象
  • 将新节点的 next 引用指向当前的 head 节点
  • 将新节点设置为链表的新 head 节点

insert to head

向链表尾部插入新元素的步骤：

  • 创建一个包含新元素的新的节点
  • 将新节点的 next 引用指向 None 作为新的 tail 节点
  • 将当前 tail 节点的 next 引用改为指向上面的新节点

insert to tail

通过单链表实现 Stack 数据结构

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
36
37
38
39
40
# linkstack.py
class EmptyError(Exception):
    pass


class Node:
    __slots__ = '_element', '_next'

    def __init__(self, element, next):
        self._element = element
        self._next = next


class LinkedStack:
    def __init__(self):
        self._head = None
        self._size = 0

    def __len__(self):
        return self._size

    def is_empty(self):
        return self._size == 0

    def push(self, e):
        self._head = Node(e, self._head)
        self._size += 1

    def top(self):
        if self.is_empty():
            raise EmptyError('Stack is empty')
        return self._head._element

    def pop(self):
        if self.is_empty():
            raise EmptyError('Stack is empty')
        answer = self._head._element
        self._head = self._head._next
        self._size -= 1
        return answer

运行效果如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
>>> from linkstack import LinkedStack
>>> s = LinkedStack()
>>> s.push(1)
>>> s.push(2)
>>> s.push(3)
>>> len(s)
3
>>> s.pop()
3
>>> s.pop()
2
>>> s.pop()
1
>>> s.pop()
Traceback (most recent call last):
  File "<stdin>", line 1, in <module>
  File "/home/starky/program/python/algorithm/linkstack.py", line 35, in pop
    raise EmptyError('Stack is empty')
linkstack.EmptyError: Stack is empty

性能
操作 时间
S.push(e) O(1)
S.pop() O(1)
S.top() O(1)
len(S) O(1)
S.is_empty() O(1)

单链表实现 Queue 数据结构

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
36
37
38
39
40
41
42
43
44
45
46
47
class Node:
    __slots__ = '_element', '_next'

    def __init__(self, element, next):
        self._element = element
        self._next = next


class EmptyError(Exception):
    pass


class LinkedQueue:
    def __init__(self):
        self._head = None
        self._tail = None
        self._size = 0

    def __len__(self):
        return self._size

    def is_empty(self):
        return self._size == 0

    def first(self):
        if self.is_empty():
            raise EmptyError('Queue is empty')
        return self._head._element

    def dequeue(self):
        if self.is_empty():
            raise EmptyError('Queue is empty')
        answer = self._head._element
        self._head = self._head._next
        self._size -= 1
        if self.is_empty():
            self._tail = None
        return answer

    def enqueue(self, e):
        newest = Node(e, None)
        if self.is_empty():
            self._head = newest
        else:
            self._tail._next = newest
        self._tail = newest
        self._size += 1

运行效果如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
>>> from linkqueue import LinkedQueue
>>> q = LinkedQueue()
>>> q.enqueue(1)
>>> q.enqueue(2)
>>> q.enqueue(3)
>>> len(q)
3
>>> q.dequeue()
1
>>> q.dequeue()
2
>>> q.dequeue()
3
>>> q.dequeue()
Traceback (most recent call last):
  File "<stdin>", line 1, in <module>
  File "/home/starky/program/python/algorithm/linkqueue.py", line 32, in dequeue
    raise EmptyError('Queue is empty')
linkqueue.EmptyError: Queue is empty

双链表

doubly linked list

图中的 header 和 trailer 节点实际上不保存任何元素，这些“dummy”节点称为 sentinels。目的是保证逻辑的一致性，即任何情况下插入新节点，都能确保其左右两边至少各有一个旧节点。

插入新节点示意图：
insert element

代码实现：

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
36
37
38
39
40
# doublylinked.py
class Node:
    __slots__ = '_element', '_prev', '_next'

    def __init__(self, element, prev, next):
        self._element = element
        self._prev = prev
        self._next = next


class DoublyLinkedBase:
    def __init__(self):
        self._header = Node(None, None, None)
        self._trailer = Node(None, None, None)
        self._header._next = self._trailer
        self._trailer._prev = self._header
        self._size = 0

    def __len__(self):
        return self._size

    def is_empty(self):
        return self._size == 0

    def _insert_between(self, e, predecessor, successor):
        newest = Node(e, predecessor, successor)
        predecessor._next = newest
        successor._prev = newest
        self._size += 1
        return newest

    def _delete_node(self, node):
        predecessor = node._prev
        successor = node._next
        predecessor._next = successor
        successor._prev = predecessor
        self._size -= 1
        element = node._element
        node._prev = node._next = node._element = None
        return element

双链表实现 Deque 数据结构
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
# linkdeque.py
from doublylinked import DoublyLinkedBase


class EmptyError(Exception):
    pass


class LinkedDeque(DoublyLinkedBase):
    def first(self):
        if self.is_empty():
            raise EmptyError("Deque is empty")
        return self._header._next._element

    def last(self):
        if self.is_empty():
            raise Empty("Deque is empty")
        return self._trailer._prev._element

    def insert_first(self, e):
        self._insert_between(e, self._header, self._header._next)

    def insert_last(self, e):
        self._insert_between(e, self._trailer._prev, self._trailer)

    def delete_first(self):
        if self.is_empty():
            raise EmptyError("Deque is empty")
        return self._delete_node(self._header._next)

    def delete_last(self):
        if self.is_empty():
            raise EmptyError("Deque is empty")
        return self._delete_node(self._trailer._prev)

运行效果如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
>>> from linkdeque import LinkedDeque
>>> dq = LinkedDeque()
>>> dq.insert_first(2)
>>> dq.insert_first(1)
>>> dq.insert_last(3)
>>> dq.insert_last(4)
>>> len(dq)
4
>>> dq.delete_first()
1
>>> dq.delete_last()
4
>>> len(dq)
2

Array-Based 序列的优势：

  • 提供 O(1) 时间下基于整数索引（index）对元素的访问。而链表访问第 k 个元素则需要 O(k) 时间（从链表头部开始遍历）
  • 在不考虑动态数组边界扩展的情况下，各种操作在基于数组的序列中性能更高（步骤相对较少），虽然整体上和链表一样时间都是 O(1)
  • 与链表结构相比，基于数组的序列需要更少的内存。基于数组或链表的序列实际上保存的都是对象的引用，因此这部分占据的内存空间是一致的。数组在最差的情况下（即刚刚扩展过边界的动态数组）需要为 2n 个对象引用收集内存；而单链表本身就需要为 2n 个对象引用提供空间（每个节点都包含元素本身和下一个节点的引用），双链表则为 3n

Link-Based 序列的优势：

链表结构能够支持任意位置下插入和删除操作只耗费 O(1) 时间。而基于数组的序列在尾部插入和删除元素是常数时间，在任意索引为 k 的位置插入或移除元素则需要 O(n - k + 1) 时间。

参考资料

Data Structures and Algorithms in Python