python实现双链表_python_

class Node:     def __init__(self, data):         self.data = data         self.next = None         self.previous = None class DoubleLinkList:     '''双链表'''     def __init__(self, node=None):         self._head = node

def is_empty(self):         return self._head is None

def length(self):         count = 0         if self.is_empty():             return count         else:             current = self._head             while current is not None:                 count += 1                 current = current.next         return count

def travel(self):         current = self._head         while current is not None:             print("{0}".format(current.data), end=" ")             current = current.next         print("")

def add(self, item):         node = Node(item)         # 如果链表为空，让头指针指向当前节点         if self.is_empty():             self._head = node         # 注意插入的顺序，         else:             node.next = self._head             self._head.previous = node             self._head = node

def append(self, item):         node = Node(item)         # 如果链表为空，则直接让头指针指向该节点         if self.is_empty():             self._head = node         # 需要找到尾节点，然后让尾节点的与新的节点进行连接         else:             current = self._head             while current.next is not None:                 current = current.next             current.next = node             node.previous = current

def search(self, item):         current = self._head         found = False         while current is not None and not found:             if current.data == item:                 found = True             else:                 current = current.next         return found

def insert(self, item, pos):         # 特殊位置，在第一个位置的时候，头插法         if pos <= 0:             self.add(item)         # 在尾部的时候，使用尾插法         elif pos > self.length() - 1:             self.append(item)         # 中间位置         else:             node = Node(item)             current = self._head             count = 0             while count < pos - 1:                 current = current.next                 count += 1             # 找到了要插入位置的前驱之后，进行如下操作             node.previous = current             node.next = current.next             current.next.previous = node             current.next = node

 # 换一个顺序也可以进行 def insert2(self, item, pos):         if pos <= 0:             self.add(item)         elif pos > self.length() - 1:             self.append(item)         else:             node = Node(item)             current = self._head             count = 0             while count < pos:                 current = current.next                 count += 1             node.next = current             node.previous = current.previous             current.previous.next = node             current.previous = node

def remove(self, item):         current = self._head         if self.is_empty():             return         elif current.data == item:             # 第一个节点就是目标节点，那么需要将下一个节点的前驱改为None 然后再将head指向下一个节点             current.next.previous = None             self._head = current.next         else:             # 找到要删除的元素节点             while current is not None and current.data != item:                 current = current.next             if current is None:                 print("not found {0}".format(item))             # 如果尾节点是目标节点，让前驱节点指向None             elif current.next is None:                 current.previous.next = None             # 中间位置，因为是双链表，可以用前驱指针操作             else:                 current.previous.next = current.next                 current.next.previous = current.previous

# 第二种写法     def remove2(self, item):         """删除元素"""         if self.is_empty():             return         else:             cur = self._head             if cur.data == item:                 # 如果首节点的元素即是要删除的元素                 if cur.next is None:                     # 如果链表只有这一个节点                     self._head = None                 else:                     # 将第二个节点的prev设置为None                     cur.next.prev = None                     # 将_head指向第二个节点                     self._head = cur.next                 return             while cur is not None:                 if cur.data == item:                     # 将cur的前一个节点的next指向cur的后一个节点                     cur.prev.next = cur.next                     # 将cur的后一个节点的prev指向cur的前一个节点                     cur.next.prev = cur.prev                     break                 cur = cur.next

my_list = DoubleLinkList() print("add操作") my_list.add(98) my_list.add(99) my_list.add(100) my_list.travel() print("{:#^50}".format("")) print("append操作") my_list.append(86) my_list.append(85) my_list.append(88) my_list.travel() print("{:#^50}".format("")) print("insert2操作") my_list.insert2(66, 3) my_list.insert2(77, 0) my_list.insert2(55, 10) my_list.travel() print("{:#^50}".format("")) print("insert操作") my_list.insert(90, 4) my_list.insert(123, 5) my_list.travel() print("{:#^50}".format("")) print("search操作") print(my_list.search(100)) print(my_list.search(1998)) print("{:#^50}".format("")) print("remove操作") my_list.remove(56) my_list.remove(123) my_list.remove(77) my_list.remove(55) my_list.travel() print("{:#^50}".format("")) print("remove2操作") my_list.travel() my_list.remove2(100) my_list.remove2(99) my_list.remove2(98) my_list.travel()