双向链表及其基本操作

　　双向链表是对单向链表的一种升级改造，具备prev和next两个指针，本文从双向链表的实现开始，逐步实现对双向链表的判空、求长度、遍历、添加、删除等操作。由于双向链表的操作与单链表相似，部分注释可参考【单链表及其基本操作：https://www.cnblogs.com/kongzimengzixiaozhuzi/p/12951670.html】。

1.定义链表节点

　　双向链表相比于单向链表，多了prev指针，用于指向当前节点的前一个节点。

1 class Node(object):
2     """节点"""
3     def __init__(self, element):
4         self.elem = element
5         self.next = None
6         self.prev = None

2.初始化双向链表

　　初始化链表时，需要一个对象属性指向头结点。

1 class DoubleLinkList(object):
2     """双链表"""
3     def __init__(self, node = None): 
4         self. __head = node

3.双向链表基本操作

3.1.链表判空

　　空链表的头一定是指向None的。

1     def is_empty(self):
2         """链表是否为空"""
3         return self.__head is None

3.2.求链表长度

　　求链表长度就是统计链表节点的个数，可以使用一个游标cur遍历节点，使用一个计数器count记录节点个数。

1     def length(self):
2         """链表长度"""
3         """cur作为游标，移动遍历元素"""
4         cur = self.__head
5         count = 0
6         while cur is not None:
7             count += 1
8             cur = cur.next
9         return count

3.3.遍历链表

1     def travel(self):
2         """遍历链表"""
3         cur = self.__head
4         while cur is not None:
5             print(cur.elem, end=" ")  # end=" "关闭换行功能,print() 的原型,print默认是以end="
"结尾.
6             cur = cur.next
7         print(end="
")

3.4.往链表头部添加元素

　　往链表中添加元素就相当远添加数据节点，需要传入节点的数据。

1     def add(self, item):
2         """在链表头部添加元素"""
3         node = Node(item)
4         node.next = self.__head
5         self.__head = node
6         node.next.prev = node

3.5.往链表尾部添加元素

 1     def append(self, item):
 2         """链表尾部添加元素"""
 3         node = Node(item)
 4         if self.is_empty():
 5             self.__head = node
 6         else:
 7             cur = self.__head
 8             while cur.next is not None:
 9                 cur = cur.next
10             cur.next = node
11             node.prev = cur

3.6.往链表指定位置添加元素

　　往双向链表中添加元素涉及到打开prev和next两个指针。需要考虑添加位置的边界条件：如果添加的位置是链表头部，可以直接调用add()函数。如果添加的位置是链表尾部，可以直接调用append()函数。

 1     def insert(self, pos, item):
 2         """在指定位置添加元素"""
 3         if pos <= 0:
 4             self.add(item)
 5         elif pos > self.length()-1:
 6             self.append(item)
 7         else:
 8             node = Node(item)
 9             cur = self.__head
10             count = 0
11             while count < pos:
12                 count += 1
13                 cur = cur.next
14             node.next = cur
15             node.prev = cur.prev
16             cur.prev.next = node
17             cur.prev = node

3.7.删除节点

 1     def remove(self, item):  # 删除具体的数据
 2         """删除节点"""
 3         cur = self.__head
 4         while cur is not None:
 5             if cur.elem == item:
 6                 if cur == self.__head:  # 头节点特殊处理
 7                     self.__head = cur.next
 8                     if cur.next:  # 判断链表是否只有一个节点
 9                         cur.next.prev = None
10                 else:
11                     cur.prev.next = cur.next
12                     if cur.next:
13                         cur.next.prev = cur.prev
14                 break
15             else:
16                 cur = cur.next

3.8.查找节点

1     def search(self, item):
2         """查找节点是否存在"""
3         cur = self.__head
4         while cur is not None:
5             if cur.elem == item:
6                 return True
7             else:
8                 cur = cur.next
9         return False

3.9.测试与结果

 1 # 测试
 2 if __name__ == "__main__":
 3     li = DoubleLinkList()
 4     print(li.is_empty())       # True
 5     print(li.length())         # 0
 6 
 7     li.append(1)
 8     print(li.is_empty())       # False
 9     print(li.length())         # 1
10 
11     li.append(2)
12     li.add(8)
13     li.append(3)
14     li.append(4)
15     li.append(5)
16     li.append(6)
17     li.insert(-1, 9)  
18     li.insert(2, 100)  
19     li.insert(10, 200)  
20     li.travel()                # 9 8 100 1 2 3 4 5 6 200 
21     li.remove(100)                
22     li.travel()                # 9 8 1 2 3 4 5 6 200 
23     li.remove(9) 
24     li.travel()                # 8 1 2 3 4 5 6 200 
25     li.remove(200)  
26     li.travel()                # 8 1 2 3 4 5 6