链式结构
本节我们讲解最常见的单链表和双链表。
上一节我们分析了 list 的各种操作是如何实现的,如果你还有印象的话,list 在头部进行插入是个相当耗时的操作(需要把后边的元素一个一个挪个位置)。
假如你需要频繁在数组两头增删,list 就不太合适。
今天我们介绍的链式结构将摆脱这个缺陷,当然了链式结构本身也有缺陷,比如你不能像数组一样随机根据下标访问,你想查找一个元素只能老老实实从头遍历。 所以嘛,学习和了解数据结构的原理和实现你才能准确地选择到底什么时候该用什么数据结构,而不是瞎选导致代码性能很差。
单链表
和线性结构不同,链式结构内存不连续的,而是一个个串起来的,这个时候就需要每个链接表的节点保存一个指向下一个节点的指针。 这里可不要混淆了列表和链表(它们的中文发音类似,但是列表 list 底层其实还是线性结构,链表才是真的通过指针关联的链式结构)。 看到指针你也不用怕,这里我们用的 python,你只需要一个简单赋值操作就能实现,不用担心 c 语言里复杂的指针。
先来定义一个链接表的节点,刚才说到有一个指针保存下一个节点的位置,我们叫它 next, 当然还需要一个 value 属性保存值
class Node:
def __init__(self, value, next=None):
self.value = value
self.next = next
然后就是我们的单链表 LinkedList ADT:
class LinkedList(object):
""" 链接表 ADT
[root] -> [node0] -> [node1] -> [node2]
"""
来看下时间复杂度:
链表操作 | 平均时间复杂度 |
---|---|
linked_list.append(value) | O(1) |
linked_list.appendleft(value) | O(1) |
linked_list.find(value) | O(n) |
linked_list.remove(value) | O(n) |
代码实现:
class Node():
def __init__(self,value=None,next=None):
self.value = value
self.next = next
def __str__(self):
return 'Node:{}'.format(self.value)
class LinkedList():
def __init__(self):
self.root = Node()
self.size = 0 #记录有多少元素
self.next = None #增加新数据时,将新数据的地址与谁关联
def append(self,value):
node = Node(value)
# 判断是否已经有数据
if not self.next: #如果没有节点时
self.root.next = node #将新节点挂到root后面
else:
self.next.next = node #将新节点挂到最后一个节点上
self.next = node
self.size += 1
def append_first(self,value):
node = Node(value)
if not self.next:
self.root.next = node
self.next = node
else:
temp = self.root.next # 获取原来root后面的那个节点
self.root.next = node # 将新的节点挂到root上
node.next = temp # 新的节点的下一个节点是原来的root后的节点
self.size += 1
def __iter__(self):
current = self.root.next
if current:
while current is not self.next:
yield current.value
current = current.next
yield current.value
def find(self,value):
for v in self.__iter__():
if v == value:
return True
def find2(self,value):
current = self.root.next
if current:
while current is not self.next:
if current.value == value:
return current
current = current.next
def remove(self,value):
current = self.root.next
if current:
while current is not self.next:
if current.value == value:
temp.next = current.next
del current
self.size -= 1
return True
temp = current
current = current.next
if __name__ == "__main__":
link = LinkedList()
link.append('孙悟空')
link.append('猪八戒')
link.append_first('唐僧')
for v in link:
print(v)
# print(link.find('孙悟空'))
# print(link.find('六儿猕猴'))
# print(link.find2('孙悟空'))
# print(link.find2('六儿猕猴'))
print('-'*30)
link.remove('孙悟空')
for v in link:
print(v)
双链表
上边我们亲自实现了一个单链表,但是能看到很明显的问题,单链表虽然 append 是 O(1),但是它的 find 和 remove 都是 O(n)的, 因为删除你也需要先查找,而单链表查找只有一个方式就是从头找到尾,中间找到才退出。 我们需要在一个链表里能高效的删除元素, 并把它追加到访问表的最后一个位置,这个时候单链表就满足不了了。
这里就要使用到双链表了,相比单链表来说,每个节点既保存了指向下一个节点的指针,同时还保存了上一个节点的指针。
class Node(object):
# 如果节点很多,我们可以用 __slots__ 来节省内存,把属性保存在一个 tuple 而不是 dict 里
# 感兴趣可以自行搜索 python __slots__
__slots__ = ('value', 'prev', 'next')
def __init__(self, value=None, prev=None, next=None):
self.value, self.prev, self.next = value, prev, next
对, 就多了 prev,有啥优势嘛?
- 看似我们反过来遍历双链表了。反过来从哪里开始呢?我们只要让 root 的 prev 指向 tail 节点,不就串起来了吗?
- 直接删除节点,当然如果给的是一个值,我们还是需要查找这个值在哪个节点? - 但是如果给了一个节点,我们把它拿掉,直接让它的前后节点互相指过去不就行了?哇欧,删除就是 O(1) 了,两步操作就行啦
循环双端链表操作 | 平均时间复杂度 |
---|---|
cdll.append(value) | O(1) |
cdll.appendleft(value) | O(1) |
cdll.remove(node),注意这里参数是 node | O(1) |
cdll.headnode() | O(1) |
cdll.tailnode() | O(1) |
代码:
class Node():
def __init__(self,value=None,prev= None, next=None):
self.value = value
self.prev = prev
self.next = next
def __str__(self):
return 'Node: value:{}'.format(self.value)
class DoubleLinkedList():
def __init__(self):
self.root = Node()
self.size = 0 #记录有多少元素
self.next = None #增加新数据时,将新数据的地址与谁关联
def append(self,value):
node = Node(value)
# 判断是否已经有数据
if not self.next: #如果没有节点时
self.root.next = node # 将新节点挂到root后面
node.prev = self.root # 设置新节点的上一个节点为root节点
else:
self.next.next = node #将新节点挂到最后一个节点上
node.prev = self.next # 设置新节点的上一个节点了,之前的最后一个节点
self.next = node # 更新最后一个节点为新加的node
self.size += 1
def append_first(self,value):
node = Node(value)
if not self.next:
node.prev = self.root # 设置新节点的上一个节点为root节点
self.next = node
else:
temp = self.root.next # 获取原来root后面的那个节点
node.prev = self.root # 设置新node的上一个节点为root
node.next = temp # 新的节点的下一个节点是原来的root后的节点
temp.prev = node # 原来Node的上个节点是新的节点
self.root.next = node # 将新的节点挂到root上
self.size += 1
def __iter__(self):
current = self.root.next
if current:
while current is not self.next:
yield current.value
current = current.next
yield current.value
def revese_iter(self):
current = self.next #获取最后一节点
if current:
while current is not self.root:
yield current
current = current.prev
def find(self,value):
for v in self.__iter__():
if v == value:
return True
def find2(self,value):
current = self.root.next
if current:
while current is not self.next:
if current.value == value:
return current
current = current.next
def remove(self):
if self.end is None:
return -1
else:
temp_node = self.root.next
self.root.next = temp_node.next
temp_node.next.top = self.root
self.size -= 1
return 1
if __name__ == "__main__":
link = DoubleLinkedList()
link.append('孙悟空')
link.append('猪八戒')
link.append_first('唐僧')
for v in link.revese_iter():
print(v)
练习:
- 手动实现双端链表
- 是否可以实现循环链表