Python3 实现双向链表
双向链表
定义：双向链表是链表中的一种，双向链表也叫双链表，它由多个节点组成，每个节点由一个数据域和两个指针域组成，一个指针指向前驱元素，一个指向后继元素
双向链表一般用来构造循环链表，这个后面我们也会学习到
定义简单的双向链表
class Node:"""The nodes of double linked list"""def __init__(self, item):self.prev = Noneself.item = itemself.next = Noneclass DoubleLinkedList:def __init__(self):self.head = Noneif __name__ == "__main__":DLL = DoubleLinkedList()DLL.head = Node(2)DLL.head.next = Node(1)DLL.head.next.prev = DLL.headprint(DLL.head.item)# Point to the second Nodeprint(DLL.head.next.item)# Point to the headprint(DLL.head.next.prev.item)print(DLL.head.next.next)
用起来实在很复杂，举了两个例子，要写一大串
那么我们为它实现一些常用的功能：
链表长度self.len，这次使用初始化属性，根据操作的影响改变长度的方法判断是否为空is_empty()展示所有节点show_items()，结果可用list()转换获取元素get_value_by_index()，以偏移量获取元素的值，超出偏移量会报错IndexErorr，可以是负偏移在指定index的前面插入节点insert_before()，当超过实际长度，在最后插入；当为负数倒序选择插入，负数的绝对值大于实际长度则在最前面插入在指定index之后插入节点insert_after()在链表尾部追加append()正序遍历traverse_forward()，定义遍历方法，要改写到类中的__iter__()和__next__()反序遍历traverse_backward()，类似正序遍历移除指定index元素remove()，偏移可以为负偏移，但超出偏移范围会报错判断元素是否存在is_exist()查找指定元素第一次出现的偏移indexOf()清空链表clear()链表的反转reverse() 点我跳到链表反转
代码实现定义节点
class Node:"""The nodes of double linked list"""def __init__(self, item):self.prev = Noneself.item = itemself.next = None
重写正向遍历方法：（不记得的同学可以参考两个示例：重写遍历方法示例）
class ForwardIterator:"""Define a forward-direction iterator"""def __init__(self, node):self.head = node.headself.cur = self.headdef __iter__(self):return selfdef __next__(self):"""Return the next item's value of iterator"""try:self.temp = self.curself.cur = self.cur.nextreturn self.temp.itemexcept AttributeError as e:raise StopIteration
重写反向遍历方法：(跟正序遍历差不多，只是指针的名字不同)
class ReversalIterator:"""Define a reverse-direction iterator"""def __init__(self, tail):self.cur = taildef __iter__(self):return selfdef __next__(self):"""Return the next item's value of iterator"""try:self.temp = self.curself.cur = self.cur.prevreturn self.temp.itemexcept AttributeError as e:raise StopIteration
功能实现
class DoubleLinkedList:def __init__(self):"""Initialize the head and the length of double linked list"""self.head = Noneself.len = 0def is_empty(self):"""Judge if a linked list is empty"""return self.head is Nonedef show_items(self):"""Show all the elements of linked list"""if self.is_empty():return Nonecur = self.headwhile cur.next:yield cur.itemcur = cur.nextyield cur.itemdef get_value_by_index(self, index):"""Get a value by index"""cur = self.headindex = self.len + index if index < 0 else indexif index < 0:raise IndexError('index out of range')try:for i in range(index):cur = cur.nextreturn cur.itemexcept AttributeError as e:raise IndexError('index out of range')# def length(self):#"""Return the elements number of a linked list"""#return self.lendef insert_before(self, index, item):"""Insert an element before the given index of a node"""node = Node(item)cur = self.headif not cur:self.head = nodeelse:if -self.len < index < 0:index += self.lenprint(index)if index > 0: # 0 < index or 0 < (index + self.len)while cur.next:index -= 1if index <= 0:breakcur = cur.nextif cur.next:node.next = cur.nextcur.next.prev = nodecur.next = nodenode.prev = curelse:# node.next = cur.next # Not necessarycur.next = nodenode.prev = curelif index <= -self.len or index == 0: # index < -self.len or index == 0node.next = self.headself.head.prev = nodeself.head = nodeself.len += 1def insert_after(self, index, item):"""Insert an element after the given index of a node"""if index >= 0:self.insert_before(index+1, item)elif -self.len-1 <= index < 0: # insert_before(self.len+index+1) equals to insert_after(index)self.insert_before(self.len+index+1, item)else:self.insert_before(0, item)# Use insert_before(), so as to no self.len+=1def append(self, item):"""Append an element to the end of a linked list"""node = Node(item)if self.is_empty():self.head = nodeelse:cur = self.headwhile cur.next:cur = cur.next# node.next = cur.next # Not necessarycur.next = nodenode.prev = curself.len += 1def traverse_forward(self):"""Travel from the head and return the node one by one"""return ForwardIterator(self)def traverse_backward(self):"""Travel from the tail and return the node one by one"""cur = self.headwhile cur.next:cur = cur.nextreturn ReversalIterator(cur)def remove(self, index):"""Remove an element by index"""if not -self.len - 1 < index < self.len:raise IndexError('remove index out of range')if index < 0:index += self.lenif index == 0:self.head = self.head.nextelse:cur = self.headpre = curwhile index > 0:pre = curcur = cur.nextindex -= 1pre.next = cur.nextself.len -= 1def is_exist(self, item):"""Judge if an element in linked list"""return item in self.show_items()def indexOf(self, item):"""Find the first-appears-index of Node(item)"""return list(self.show_items()).index(item)def clear(self):"""CLear all nodes"""self.head = Noneself.len = 0def reverse(self):"""Reverse the linked list"""cur = self.headif not cur:returndef reverse(cur):if not cur.next:self.head = curreturn curprev = reverse(cur.next)prev.next = curcur.next = Nonereturn curreverse(cur)
验证功能
if __name__ == '__main__':DLL = DoubleLinkedList()print(f"Is empty? {DLL.is_empty()}")for i in range(5):DLL.append(i)print(f"Show all items:{list(DLL.show_items())}")_index, _item = -6, 11DLL.insert_before(_index, _item)print(f"Insert {_item} before linked list[{_index}]: {list(DLL.show_items())}")_index, _item = -3, 22DLL.insert_after(_index, _item)print(f"Insert {_item} after linked list[{_index}]: {list(DLL.show_items())}")_item = 33DLL.append(_item)print(f"Append an element[{_item}] to the end: {list(DLL.show_items())}")import collections# Travel backwardprint("DLL.traverse_backward() is Iterable??", isinstance(DLL.traverse_backward(), collections.Iterable))print([i for i in iter(DLL.traverse_backward())])# for i in DLL.traverse_forward():#print(i)# Travel forwardprint("DLL.traverse_forward() is Iterable??", isinstance(DLL.traverse_forward(), collections.Iterable))print([i for i in iter(DLL.traverse_forward())])# for i in DLL.traverse_forward():#print(i)_index = -1DLL.remove(_index)print(f"Remove an element by index[{_index}]: {list(DLL.show_items())}")_item = 22print(f"Is item [{_item}] exists in this list? {DLL.is_exist(_item)}")_item = 1print(f"The first-appears-index of item [{_item}] in this list is {DLL.indexOf(_item)}")print(f"Clear all: {DLL.clear()}, the length of the list: {DLL.len} ")for i in range(3):DLL.append(i)print(f"Before reverse: {list(DLL.show_items())}")DLL.reverse()print(f"After reverse: {list(DLL.show_items())}")
输出结果：
Is empty? TrueShow all items:[0, 1, 2, 3, 4]Insert 11 before linked list[-5]: [11, 0, 1, 2, 3, 4]Insert 22 after linked list[5]: [11, 0, 1, 2, 3, 4, 22]Append an element[33] to the end: [11, 0, 1, 2, 3, 4, 22, 33]DLL.traverse_backward() is Iterable?? True[33, 22, 4, 3, 2, 1, 0, 11]DLL.traverse_forward() is Iterable?? True[11, 0, 1, 2, 3, 4, 22, 33]Remove an element by index[-1]: [11, 0, 1, 2, 3, 4, 22]Is item [22] exists in this list? TrueThe first-appears-index of item [1] in this list is 2[11, 0, 1, 55, 2, 3, 4, 22]Clear all: None, the length of the list: 0 Before reverse: [0, 1, 2]After reverse: [2, 1, 0]
时间复杂度分析点击回到代码实现
show_items()每次查询都需要遍历整条链表，while循环n次，时间复杂度为O(n)get_value_by_index()每一次获取元素，都需要从头结点开始，向后for循环遍历，循环次数与查询的index成正比，为n次，时间复杂度为O(n)insert_before()最坏情况是在链表最后插入，需要while循环n次，时间复杂度为O(n)insert_after()同insert_before()，最多需要循环n次，时间复杂度为O(n)append()每次追加都要循环完毕列表，执行n次，时间复杂度为O(n)remove()最坏情况下需要循环n次，时间复杂度为O(n)
总结相较于顺序表，链表的插入和删除操作时间复杂度虽然也是O(n)，但是实际链表操作的动作更加简洁，因为链表的内存地址无需连续，大小随时可变，在插入和删除时无需改变容量来调整合适的大小，此外插入和删除时，其他的元素也不用改变位置，因此当查询和插入操作较多时，推荐使用链表如果实际情况中使用查询操作较多时，链表相对顺序表而言操作性能会更低，此时建议使用顺序表
附加——链表的反转点击回到代码实现
def reverse(self):"""Reverse the linked list"""cur = self.headif not cur:returndef reverse(cur):if not cur.next:self.head = curreturn curprev = reverse(cur.next)prev.next = curcur.next = Nonereturn curreverse(cur)
链表的反转通过递归实现将链表的head移动到尾节点
递归算法所体现的“重复”一般有三个要求：
一是每次调用在规模上都有所缩小(通常是减半)；二是相邻两次重复之间有紧密的联系，前一次要为后一次做准备(通常前一次的输出就作为后一次的输入)；三是在问题的规模极小时必须用直接给出解答而不再进行递归调用，因而每次递归调用都是有条件的(以规模未达到直接解答的大小为条件)，无条件递归调用将会成为死循环而不能正常结束。
链表反转：
分析递归达成的反转过程：
重写遍历方法示例
Example1import collectionsclass MyIter(object):def __init__(self, num):self.num = numdef __next__(self):if self.num == 0:raise StopIterationself.num -= 1return self.numdef __iter__(self):return selffor i in MyIter(4):print(i)print(iter(MyIter(4)))print(isinstance(MyIter(4), collections.Iterable))
Example2
# Example2class Iteration:def __init__(self, iterable): # [1, 2, 3, 4]self.iterable = iterableself.stop = len(iterable)self.start = 0def __iter__(self):return selfdef __next__(self):"""Return the next item's value of iterator"""if self.start < self.stop:start = self.startself.start += 1return self.iterable[start]else:raise StopIterationdef add(self, item):self.iterable.append(item)alist = [1, 2, 3, 4]IT = Iteration(alist)print(f"[{IT.__class__.__name__}] is iterable? {isinstance(IT, collections.Iterable)}")print(f"[{IT.__class__.__name__}] is iterable? {iter(IT)}")for i in IT:print(i)
结果只需要用isinstance(IT, collections.Iterable)来判断它两是否相等即可，为True则可遍历，为False则不可遍历；用iter(object)也可以判断，但是如果不可遍历会报错
回到代码实现
