7

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

 3 years ago
source link: https://rollingstarky.github.io/2020/10/13/python-and-data-structure-linked-list/
Go to the source link to view the article. You can view the picture content, updated content and better typesetting reading experience. If the link is broken, please click the button below to view the snapshot at that time.
neoserver,ios ssh client

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

2020-10-13

| 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

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) 时间。

Data Structures and Algorithms in Python


report

Recommend

About Joyk


Aggregate valuable and interesting links.
Joyk means Joy of geeK