Python 与数据结构 —— 链表及其应用
2020-10-13 本文已影响0人
rollingstarky
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 数据结构
# 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
运行效果如下：
>>> 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 数据结构
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
运行效果如下：
>>> 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
代码实现：
# 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 数据结构
# 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)
运行效果如下：
>>> 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
Link-Based vs. Array-Based
Array-Based 序列的优势：
- 提供
O(1)时间下基于整数索引（index）对元素的访问。而链表访问第 k 个元素则需要O(k)时间（从链表头部开始遍历） - 在不考虑动态数组边界扩展的情况下，各种操作在基于数组的序列中性能更高（步骤相对较少），虽然整体上和链表一样时间都是
O(1) - 与链表结构相比，基于数组的序列需要更少的内存。基于数组或链表的序列实际上保存的都是对象的引用，因此这部分占据的内存空间是一致的。数组在最差的情况下（即刚刚扩展过边界的动态数组）需要为
2n个对象引用收集内存；而单链表本身就需要为2n个对象引用提供空间（每个节点都包含元素本身和下一个节点的引用），双链表则为3n
Link-Based 序列的优势：
链表结构能够支持任意位置下插入和删除操作只耗费 O(1) 时间。而基于数组的序列在尾部插入和删除元素是常数时间，在任意索引为 k 的位置插入或移除元素则需要 O(n - k + 1) 时间。
