python-实现双链表

  1 # encoding=utf-8
  2 
  3 
  4 class Node(object):
  5     def __init__(self, item):
  6         self.item = item
  7         self.next = None
  8         self.pre = None
  9 
 10 
 11 class DoubleLink(object):
 12     """双向链表"""
 13     def __init__(self, node=None):
 14         self.__head = node
 15 
 16     def is_empty(self):
 17         """链表是否为空"""
 18         return self.__head is None
 19 
 20     def length(self):
 21         """链表长度"""
 22         current = self.__head
 23         count = 0
 24         while current is not None:
 25             count += 1
 26             current = current.next
 27 
 28         return count
 29 
 30     def travel(self):
 31         """遍历整个链表 要考虑空链表如果是空链表判断条件不成立也就不输出任何信息"""
 32         current = self.__head
 33         while current is not None:
 34             print(current.item, end=" ")
 35             current = current.next
 36 
 37         print("")  # 多输出换行
 38 
 39     def search(self, item):
 40         """
 41         查找节点是否存在
 42         :param item: 要查找的element
 43         :return:
 44         """
 45         cur = self.__head
 46 
 47         while cur is not None:
 48             if cur.item == item:
 49                 return True
 50             cur = cur.next
 51 
 52         return False
 53 
 54     def add(self, item):
 55         """"在链表头部插入元素"""
 56         node = Node(item)
 57         if self.is_empty():
 58             self.__head = node
 59         else:
 60             node.next = self.__head
 61             self.__head.pre = node
 62             self.__head = node
 63 
 64     def append(self, item):
 65         """"在链表尾部插入节点"""
 66         node = Node(item)
 67         if self.is_empty():
 68             self.__head = node
 69         else:
 70             # 寻找尾节点
 71             cur = self.__head
 72             while cur.next is not None:
 73                 cur = cur.next
 74             cur.next = node
 75             node.pre = cur
 76 
 77 
 78     def insert(self, pos, item):
 79         """指定位置添加元素"""
 80         # 在头结点插入元素
 81         if pos <=0:
 82             self.add(item)
 83         # 在链表的尾部添加元素
 84         elif pos >= self.length():
 85             self.append(item)
 86         # 在链表的任意位置添加元素
 87         else:
 88             cur = self.__head
 89             count = 0
 90             # 找到添加位置
 91             while count < pos:
 92                 count += 1
 93                 cur = cur.next
 94             node = Node(item)
 95 
 96             node.next = cur
 97             node.pre = cur.pre
 98             cur.pre = node
 99             node.pre.next = node
100 
101 
102     def remove(self, item):
103         """
104         删除节点
105         :param item:　要删除的元素
106         :return:
107         """
108 
109         cur = self.__head
110         while cur is not None:
111             # 找到了元素
112             if cur.item == item:
113                 # 在头部找到了元素
114                 if cur == self.__head:
115                     self.__head = cur.next
116                     if cur.next:
117                         cur.next.pre = None
118                 else:
119                     cur.pre.next = cur.next
120                     if cur.next:
121                         cur.next.pre = cur.pre
122 
123                 return
124             cur = cur.next
125 
126 
127 
128 if __name__ == '__main__':
129     ll = DoubleLink()
130     print(ll.length())
131 
132     ll.append(1)   # 1
133     print(ll.length())
134     ll.travel()
135 
136     ll.append(2)   #1 2
137     print(ll.length())
138     ll.travel()
139 
140     ll.add(3)   # 3 1 2
141     ll.travel()
142 
143     ll.add(4) # 4 3 1 2
144     ll.travel()
145 
146     ll.insert(0, 5)  # 5 4 3 1 2
147     ll.travel()
148 
149     ll.insert(10, 6)  # 5 4 3 1 2  6
150     ll.travel()
151 
152     ll.insert(3, 7)  # 5 4 3  7 1 2  6
153     ll.travel()
154 
155     ll.remove(5)  #  4 3  7 1 2  6)
156     ll.travel()
157 
158     ll.remove(6)  #  4 3  7 1 2
159     ll.travel()
160 
161     ll.remove(7)  #  4 3  1 2
162     ll.travel()
163 
164     ll.remove(4)  #  3  1 2
165     ll.travel()
166     ll.remove(3)  #   1 2
167     ll.travel()
168     ll.remove(1)  #  2
169     ll.travel()
170     ll.remove(2)
171     ll.travel()