写给自己看的笔记, 很多坑
标准版
class Node(object): def __init__(self, item): self.elem = item self.prev = None self.next = None class TwoLinkList(object): def __init__(self, node=None): self.__head = node def is_empty(self): return self.__head == None def length(self): cur = self.__head count = 0 while cur != None: count += 1 cur = cur.next return count def tarvel(self): cur = self.__head while cur != None: print(cur.elem, end=" ") cur = cur.next print("") def add(self, item): node = Node(item) node.next = self.__head self.__head.prev = node self.__head = node def append(self, item): node = Node(item) if self.__head is None: self.__head = node else: cur = self.__head while cur.next != None: cur = cur.next cur.next = node node.prev = cur def insert(self, pos, item): if self.__head is None: self.add(item) elif pos <= 0: self.add(item) elif pos > (self.length()-1): self.append(item) else: node = Node(item) count = 0 cur = self.__head while count != pos: count += 1 cur = cur.next node.prev = cur.prev node.next = cur cur.prev.next = node cur.prev = node def search(self, item): if self.__head is None: return False else: cur = self.__head while cur != None: if cur.elem == item: return True else: cur = cur.next return False def remove(self, item): if self.__head is None: return False else: cur = self.__head while cur != None: if cur.elem == item: if cur == self.__head: self.__head = cur.next if cur.next: cur.prev = None else: cur.prev.next = cur.next if cur.next: cur.next.prev = cur.prev break else: pro = cur cur = cur.next return False
注释版
class Node(object): """节点类""" def __init__(self, item): """初始化函数""" self.elem = item self.prev = None self.next = None # 默认创建的节点，前驱指向，以及后继指向都为None class TwoLinkList(object): """双链表类""" def __init__(self, node=None): """初始化函数""" self.__head = node # self.__head是链表的首节点 # 双链表跟单链表一样，链表可以没有节点，但必须存在首节点【是有些矛盾】 # 即: 如果self.__head is None，首节点指向None， 表示链表为空 def is_empty(self): """链表是否为空""" return self.__head == None # 如果链表为空,那么首节点的指向为None def length(self): """链表的长度""" cur = self.__head # 创建游标cur,起始指向首节点 count = 0 # 用计数的方式来测量链表的长度 while cur != None: # 遍历所有节点 count += 1 # 计数加一 cur = cur.next # cur后移一位 return count # 遍历完毕，返回计数值 def tarvel(self): """遍历所有元素""" cur = self.__head # 创建游标cur,起始指向首节点 while cur != None: # 遍历所有节点 print(cur.elem, end=" ") # 打印当前节点的elem值 cur = cur.next # cur后移一位 print("") # 换行操作 def add(self, item): """首插法""" node = Node(item) # 创建新节点node node.next = self.__head # 将node的next域指向链表原先的首节点 self.__head.prev = node # 将链表原先的首节点prev域指向node self.__head = node # 执行上面两步后新节点node已经跟原先的首节点关联好, 然后将链表的首节点指向node def append(self, item): """尾插法""" node = Node(item) # 创建新节点node if self.__head is None: # 如果链表没有节点 self.__head = node # 让链表的首节点指向新节点node """注意: 因为双链表的首节点的prev域是指向None的,创建新节点的node,node的prev域默认是指向None的,所以不用修改node 的prev域""" else: cur = self.__head # 创建游标cur while cur.next != None: # 如果当前游标cur的next域指向的不是None,则一直寻 cur = cur.next # 游标向后移动一位 """注:当游标cur的next域指向None的时候,是不进入循环的,所以上面循环结束后,游标cur指向的是链表的尾节点,然后对尾节点进行操作""" cur.next = node # 让cur的next域,指向新节点node node.prev = cur # 让新节点node的prev域指向cur """注: 双链表的尾节点的next域默认是指向None的,新节点node的next域也是指向None的,所以不必进行操作""" def insert(self, pos, item): """指定位置插入节点""" if self.__head is None: # 先判断链表是否为空 self.add(item) elif pos <= 0: # 如果pos小于等于0, 执行首插法 self.add(item) elif pos > (self.length()-1): # 如果pos大于尾节点的下标,执行尾插法 self.append(item) else: node = Node(item) # 创建新节点node count = 0 # 用计数的方式来确定节点的下标 cur = self.__head # 创建游标cur while count != pos: # 如果count不等于pos,则一直循环 count += 1 # 计数加一 cur = cur.next # cur后移一位 # 当上面循环结束后, cur指向的是pos下标处的节点 node.prev = cur.prev # 让新节点node的prev域指向cur的前驱节点 node.next = cur # 让新节点node的next域指向cur cur.prev.next = node # 让cur前驱节点的next域指向新节点node cur.prev = node # 让cur的prev域指向新节点node def search(self, item): """查找节点是否存在""" if self.__head is None: # 判断链表是否为空 return False else: cur = self.__head # 创建游标cur while cur != None: # 遍历所有节点 if cur.elem == item: # 判断当前节点的elem是否等于item # 注意: cur.elem == item 不能写成 cur == item return True else: cur = cur.next # 向后移动一位 return False # 如果循环内找到了与item一样的节点, 就直接返回True了[结束函数的运行] # 如果循环结束,没有找到与item一样的节点,返回False def remove(self, item): """删除节点""" if self.__head is None: # 判断链表是否为空 return False else: cur = self.__head # 创建游标cur while cur != None: # 遍历所有节点 if cur.elem == item: # 找到elem与item一样的节点cur if cur == self.__head: # 先判断要删除的节点item是否为首节点 self.__head = cur.next # 如果cur是首节点,让首节点直接指向cur的后继节点 if cur.next: # 判断链表是否只有一个节点 """注: 如果cur.next不为None,表示cur后面还有节点,当你删除cur(链表原先的首节点)之后, cur的后继节点会变成链表的首节点, 原先cur的后继节点的prev域是有值,现在要将他变成链表的首节点, 所以要将他的prev域置为None""" cur.prev = None # 将cur的prev域指向None else: cur.prev.next = cur.next # 让cur的前驱节点的next域指向cur的后继节点 if cur.next: # 如果cur不是链表的尾节点,让cur的后继节点的prev域指向cur的前驱节点pro cur.next.prev = cur.prev break # 找到item的之后,执行完上面的代码体就该跳出了 else: pro = cur cur = cur.next # 向后移动一位 return False # 如果循环内找到了与item一样的节点, 就直接返回True了 # 如果循环结束,没有找到与item一样的节点,当然返回False
测试代码
if __name__ == "__main__": tll = TwoLinkList() print(tll.is_empty()) print(tll.length()) tll.append(1) tll.tarvel() print(tll.is_empty()) print(tll.length()) tll.add(2) tll.tarvel() tll.append(1) tll.append(2) tll.append(4) tll.append(5) tll.append(6) tll.tarvel() tll.insert(1, 3) tll.tarvel() print(tll.search(2)) print(tll.search(9)) tll.remove(3) tll.tarvel() tll.remove(2) tll.tarvel() tll.remove(1) tll.tarvel() print(tll.search(1)) print(tll.search(10))