尾部添加元素如下所示:
指定位置插入元素如下所示:
上面的对的可以比照下面的图片看，node2节点相当于上图中的cur节点，如下所示:
代码等价于:
node.next = cur <===> node.next = node2
node.prev = cur.prev <===> node.prev = node1
cur.prev.next = node <===> node1.next = node
cur.prev = node <===> node2.prev = node
删除元素如下所示:
结合下图查看，如下所示:
具体代码如下所示:
# -*-coding=utf-8-*-class Node(object):"""结点"""def __init__(self,item):self.elem = itemself.next = Noneself.prev = Noneclass DoubleLinkList(object):"""双链表"""def __init__(self,node=None):self.__head = Nonedef is_empty(self):"""链表是否为空"""return self.__head is Nonedef length(self):"""链表长度"""#cur游标，用来移动遍历节点cur = self.__head#count 记录数量count = 0while cur != None:count+=1cur = cur.nextreturn countdef travel(self):"""遍历整个链表"""cur = self.__headwhile cur != None:print(cur.elem,end=" ")cur = cur.nextprint("")def add(self,item):"""链表头部添加元素，头插法"""node = Node(item)#先写箭头指向右边的代码，node节点先写next方向的，再写prev方向的node.next = self.__headself.__head = node#最后写箭头指向左边的代码node.next.prev = nodedef append(self,item):"""链表尾部添加元素，尾插法"""node = Node(item)if self.is_empty():self.__head = nodeelse:cur = self.__headwhile cur.next != None:cur = cur.nextcur.next = nodenode.prev = curdef insert(self, pos, item):"""链表指定位置添加元素:param pos 从0开始"""# 若指定位置pos为第一个元素之前，则执行头部插入if pos <= 0: # 头插法self.add(item)# 若指定位置超过链表尾部，则执行尾部插入elif pos > (self.length() - 1): # 尾插法self.append(item)# 找到指定位置else:# pre用来指向指定位置pos的前一个位置pos-1，初始从头节点开始移动到指定位置cur = self.__headcount = 0while count < pos:count += 1cur = cur.next# 当循环退出后,cur指向pos位置node = Node(item)node.next = curnode.prev = cur.prevcur.prev.next = nodecur.prev = nodedef remove(self, item):"""删除节点"""cur = self.__headwhile cur != None:# 找到了指定元素if cur.elem == item:# 先判断此节点是否是头节点# 头节点 # 如果第一个就是删除的节点if cur == self.__head:# 将头指针指向头节点的后一个节点self.__head = cur.nextif cur.next:#判断链表是否只有一个节点cur.next.prev = Noneelse:cur.prev.next = cur.nextif cur.next:cur.next.prev = cur.prevbreak # 删除后再退出循环,需要一个总的break退出else:# 继续按链表后移节点cur = cur.nextdef search(self, item):"""查找节点是否存在""""""链表查找节点是否存在，并返回True或者False"""cur = self.__headwhile cur != None:if cur.elem == item:return Trueelse:cur = cur.nextreturn Falseif __name__ == "__main__":# node = Node(100)ll = DoubleLinkList()print(ll.is_empty()) # Trueprint(ll.length()) # 0ll.append(1)print(ll.is_empty()) # Falseprint(ll.length()) # 1ll.append(2)ll.add(8)ll.append(3)ll.append(4)ll.append(5)ll.append(6)# 8 1 2 3 4 5 6ll.insert(-1, 9)ll.travel() # 9 8 1 2 3 4 5 6ll.insert(3, 100)ll.travel() # 9 8 1 100 2 3 4 5 6ll.insert(10, 200)ll.travel() # 9 8 1 100 2 3 4 5 6 200ll.remove(100)ll.travel() # 9 8 1 2 3 4 5 6 200ll.remove(9)ll.travel() # 8 1 2 3 4 5 6 200ll.remove(200)ll.travel() # 8 1 2 3 4 5 6
参考:来源网上
/Se7eN-HOU/p/11103891.html
