Python 数据结构之链表:单向链表,双向链表,循环链表实现。

女爷i 2023-07-25 09:25 13阅读 0赞

1. 链表

我们在 Python 序列:列表 (list),元组(tuple),字符串(str)深入分析(包括扩容和摊销)。 和 Python:栈和队列的 python 列表实现 中可以看出列表是存在一定问题的:

  1. 由于动态数组,底层的数组长度可能会超过实际存储元素的个数,造成空间上的浪费。
  2. 我们 append 的平均时间复杂度是 O(1),但是这是摊销的结果,某一次的时间复杂度最坏为 O(n)。
  3. 队列的一般实现,每次出队的时间复杂度是 O(n)

于是就有了另外一种结构,就是链表。链表和列表可以对其中的元素保持一定的顺序,但是实现方式不同:

  1. 数组采用一种集中式,一个大的内存区域进行元素的存放。
  2. 链表是一种分布式的方法,每个元素是一个节点。每个节点有当前节点自身元素的值(引用方式,也就是存放的是指向真正对象的地址),还有一个下一对象的引用(指向下一对象)。这样链表的元素实际存放在不同的区域,靠着指向来保证遍历和顺序。

2. 链表的实现(单链表)

  1. class Node:
  2. def __init__(self, val):
  3. self.val = val
  4. self.next = None
  5. class SingleLinkedList:
  6. def __init__(self, node=None):
  7. self.head = node
  8. if node:
  9. self.size = 1
  10. else:
  11. self.size = 0
  12. def is_empty(self):
  13. return self.size == 0
  14. def length(self):
  15. return self.size
  16. def add_first(self, val):
  17. node = Node(val)
  18. node.next = self.head
  19. self.head = node
  20. self.size += 1
  21. def append(self, val):
  22. node = Node(val)
  23. current = self.head
  24. if current is None:
  25. self.head = node
  26. else:
  27. while current.next:
  28. current = current.next
  29. current.next = node
  30. self.size += 1
  31. def insert_by_position(self, pos, val):
  32. if pos > self.size or pos < 0:
  33. print('Out of linked list index!')
  34. elif pos == 0:
  35. self.add_first(val)
  36. else:
  37. node = Node(val)
  38. count = 0
  39. pre = self.head
  40. while count < (pos-1):
  41. pre = pre.next
  42. count = count + 1
  43. node.next = pre.next
  44. pre.next = node
  45. self.size += 1
  46. def remove_by_value(self, val):
  47. current = self.head
  48. pre = None
  49. while current:
  50. if current.val == val:
  51. if pre:
  52. pre.next = current.next
  53. else:
  54. self.head = current.next
  55. self.size -= 1
  56. return
  57. pre = current
  58. current = current.next
  59. print('Not found value!')
  60. def search(self, val):
  61. current = self.head
  62. while current:
  63. if current.val == val:
  64. return True
  65. else:
  66. current = current.next
  67. return False
  68. def travel(self):
  69. current = self.head
  70. while current:
  71. print(current.val, end=' ')
  72. current = current.next
  73. print()
  74. if __name__ == '__main__':
  75. pass
  76. class Node:
  77. def __init__(self, val):
  78. self.val = val
  79. self.next = None

定义我们的节点,节点中 val 为本节点的值,next 指向下一个节点(如果没有则为空)

  1. class SingleLinkedList:
  2. def __init__(self, node=None):
  3. self.head = node
  4. if node:
  5. self.size = 1
  6. else:
  7. self.size = 0

初始化我们的单链表,简单的提供了两种初始化方法,一种是空的初始化,一种使用一个节点初始化。为了直接返回链表的长度,不必遍历整个链表,因此保存了一个链表长度的变量,时间复杂度为 O(1)。
注意:如果没有 size 变量,那么求链表的长度的时间复杂度为 O(n),因为我们只有链表的头结点,我们不知道尾节点(当然你也可以用一个变量来保存,每次操作的时候要考虑尾节点是否变化),因此只能根据头结点的 next 来遍历整个链表,然后计数才能知道链表的长度。
我们实现的方法有:



















































方法 操作 时间复杂度
is_empty 判断是否为空链表 O(1)
length 链表长度 O(1)
add_first 在头部添加元素 O(1)
append 在尾部添加元素 O(n)
insert_by_position 按位置插入 O(k)
remove_by_value 删除链表中包含改值的第一个节点 O(k)
search 查找某元素 O(k)
travel 遍历打印元素 O(n)

其中 k 是第几个节点或位置满足条件。

注意:我们的实现中 append 的复杂度是 O(n),这是为了和一般的链表实现一致,只有头结点,一个简单的方法降为 O(1) 的操作是,链表中用一个变量保存尾节点的引用。这样只需要尾节点的 next 指向新加入的节点即可。

在上面中,我们发现删除节点:

  1. def remove_by_value(self, val):
  2. current = self.head
  3. pre = None
  4. while current:
  5. if current.val == val:
  6. if pre:
  7. pre.next = current.next
  8. else:
  9. self.head = current.next
  10. self.size -= 1
  11. return
  12. pre = current
  13. current = current.next
  14. print('Not found value!')

需要维护一个 pre 变量指向此元素的上一个元素,因为每个节点只有 next 指向下一节点,并没有指向前一节点,删除的时候要修改上一指针的 next 指向。所以添加了一个辅助节点来指向当前节点的上一节点,这个方法在链表中很常用,这个节点一般叫哨兵节点。为了可以方便的访问之前和之后节点,于是有了双向链表。

3. 双向链表的实现

  1. class Node:
  2. def __init__(self, val):
  3. self.val = val
  4. self.next = None
  5. self.pre = None
  6. class DoubleLinkedList:
  7. def __init__(self, node=None):
  8. self.head = node
  9. if node:
  10. self.size = 1
  11. else:
  12. self.size = 0
  13. def is_empty(self):
  14. return self.size == 0
  15. def length(self):
  16. return self.size
  17. def travel(self):
  18. current = self.head
  19. while current:
  20. print(current.val, end=' ')
  21. current = current.next
  22. print()
  23. def add_first(self, val):
  24. node = Node(val)
  25. current = self.head
  26. if current:
  27. node.next = current
  28. current.pre = node
  29. self.head = node
  30. else:
  31. self.head = node
  32. self.size += 1
  33. def append(self, val):
  34. node = Node(val)
  35. current = self.head
  36. if self.head:
  37. while current.next:
  38. current = current.next
  39. current.next = node
  40. node.pre = current
  41. else:
  42. self.head = node
  43. self.size += 1
  44. def insert_by_position(self, pos, val):
  45. if pos < 0 or pos > self.size:
  46. print('Out of linked list index!')
  47. elif pos == 0:
  48. self.add_first(val)
  49. else:
  50. count = 0
  51. node = Node(val)
  52. current = self.head
  53. while current < pos - 1:
  54. current = current.next
  55. count += 1
  56. node.next = current.next
  57. node.pre = current
  58. current.next.pre = node
  59. current.next = node
  60. self.size += 1
  61. def remove_by_value(self, val):
  62. current = self.head
  63. if current:
  64. if current.val == val:
  65. if current.next is None:
  66. self.head = None
  67. else:
  68. current.next.pre = None
  69. self.head = current.next
  70. self.size -= 1
  71. return
  72. while current:
  73. if current.val == val:
  74. current.pre.next = current.next
  75. current.next.pre = current.pre
  76. self.size -= 1
  77. return
  78. else:
  79. current = current.next
  80. print('Not found value!')
  81. else:
  82. print('Not found value!')
  83. def search(self, val):
  84. current = self.head
  85. while current:
  86. if current.val == val:
  87. return True
  88. else:
  89. current = current.next
  90. return False
  91. if __name__ == "__main__":
  92. pass
  93. class Node:
  94. def __init__(self, val):
  95. self.val = val
  96. self.next = None
  97. self.pre = None

双向链表的节点相对于担心链表的节点多了一个 pre 变量指向上一节点(如果是头结点,则为空)。

4. 循环链表的实现:

  1. class Node:
  2. def __init__(self, val):
  3. self.val = val
  4. self.next = None
  5. class SingleLinkedList:
  6. def __init__(self, node=None):
  7. self.head = node
  8. if node:
  9. self.size = 1
  10. else:
  11. self.size = 0
  12. def is_empty(self):
  13. return self.size == 0
  14. def length(self):
  15. return self.size
  16. def add_first(self, val):
  17. node = Node(val)
  18. if self.is_empty():
  19. self.head = node
  20. node.next = self.head
  21. else:
  22. node.next = self.head
  23. current = self.head
  24. while current.next != self.head:
  25. current = current.next
  26. current.next = node
  27. self.head = node
  28. self.size += 1
  29. def append(self, val):
  30. node = Node(val)
  31. current = self.head
  32. if current is None:
  33. self.head = node
  34. node.next = self.head
  35. else:
  36. while current.next != self.head:
  37. current = current.next
  38. current.next = node
  39. node.next = self.head
  40. self.size += 1
  41. def insert_by_position(self, pos, val):
  42. if pos > self.size or pos < 0:
  43. print('Out of linked list index!')
  44. elif pos == 0:
  45. self.add_first(val)
  46. else:
  47. node = Node(val)
  48. count = 0
  49. pre = self.head
  50. while count < (pos-1):
  51. pre = pre.next
  52. count = count + 1
  53. node.next = pre.next
  54. pre.next = node
  55. self.size += 1
  56. def remove_by_value(self, val):
  57. if self.is_empty():
  58. print('Not found value!')
  59. return
  60. current = self.head
  61. pre = None
  62. if current.val == val:
  63. if current.next != self.head:
  64. while current.next != self.head:
  65. current = current.next
  66. current.next = self.head.next
  67. self.head = self.head.next
  68. else:
  69. self.head = None
  70. self.size -= 1
  71. else:
  72. pre = self.head
  73. while current.next != self.head:
  74. if current.val == val:
  75. pre.next = current.next
  76. self.size -= 1
  77. return
  78. else:
  79. pre = current
  80. current = current.next
  81. if current.val == val:
  82. pre.next = current.next
  83. self.size -= 1
  84. print('Not found value!')
  85. def search(self, val):
  86. if self.is_empty():
  87. return False
  88. current = self.head
  89. if current.val == val:
  90. return True
  91. while current.next != self.head:
  92. current = current.next
  93. if current.val == val:
  94. return True
  95. return False
  96. def travel(self):
  97. current = self.head
  98. for _ in range(self.size):
  99. print(current.val, end=' ')
  100. current = current.next
  101. print()
  102. if __name__ == '__main__':
  103. pass

循环链表值得是链表尾节点的 next 不是指向 None,而是指向头结点。最大的改变就是遍历的时候,尾节点的判断条件不是 next == None,而是 next == self.head。另外也可以加一个计数变量来比较和链表长度的关系。

5. 基于链表的栈和队列

  1. 栈:前面提到可以增加尾节点变量使得操作链头链尾的时间复杂度变为 O(1),因此栈的实现就很自然了。
  2. 队列:同样的,假如有尾节点变量可以很简单地实现。时间复杂度都是 O(1)。

6. 链表和列表的对比:

6.1 列表的优点:

  1. 基于整数索引访问一个元素的时间复杂度为 O(1),一般的链表只能从头开始计数遍历。
  2. 大部分操作列表和链表时间复杂度一样,但是常数项更小。比如添加元素,链表涉及节点实例化,节点之间指向改变等。而列表只需要添加元素即可(不考虑底部数组扩容)。
  3. 列表需要的存储更少:这可能有悖于直觉,因为列表是基于动态数组,底层数组可能没有完全使用,但是我们知道列表和链表都是引用结构的,所以存储的都是地址,地址指向的对象大小之和是一样的。对于列表,长度为 n,最坏情况,底层数组为 2n (假设刚刚扩容,且为 2 倍扩容)。对于链表,由于每个节点除了存放本节点元素的引用还要存放下一元素的引用,因此长度为 n 的链表需要至少存放 2n 个引用。一个最多,一个至少。
  4. 查找速度快 (已排序的列表二分查找 logn)

6.2 链表的优点:

  1. 链表提供了最坏的时间界限:以保存了尾节点的链表的 append 操作为例:append 操作的最坏情况也只是 O(1),而列表是平均摊销为 O(1),最坏情况为 O(n)(扩容的时候)。再就是头部元素的删除,列表的时间复杂度为 O(n),而链表为 O(1)——栈和队列的实现上表现很明显。
  2. 和列表不一样,申请内存的时候不一定要一块连续的内存空间。
  3. 插入删除简单,只需要改变节点之间指向,而列表需要移动元素。

发表评论

表情:
评论列表 (有 0 条评论,13人围观)

还没有评论,来说两句吧...

相关阅读