Python-链表之双向链表

基本概念：

前驱节点：当前节点的前一个节点

后继节点：当前节点的下一个节点

每个节点中包含：数据区，pre（前区域），next（后区域）

双链表和单链表的区别就在于多了一个前区域，所以只有添加，删除，插入等操作和单链表不同，其他操作例如测试是否为空，遍历，测算长度等都相同，可以通过继承的思想来使用。

操作：

添加节点：

特别注意要理清楚节点前后的关系，可执行的代码不止一种，根据代码的先后顺序来判断节点关系。

删除节点：

要注意删除的节点是否是首节点或者末节点，需要加入额外的判断条件

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.is_empty(): self._head = node else: cur = self._head while cur.next is not None: cur = cur.next cur.next = node node.prev = cur def insert(self, pos, item): # 指定位置添加元素 if pos <= 0: self.add(item) elif pos >= (self.length() - 1): self.append(item) else: cur = self._head count = 0 while count < (pos - 1): count += 1 cur = cur.next # 当循环退出后，pre指向pos-1的位置 node = Node(item) node.next = cur node.prev = cur.prev cur.prev.next = node cur.prev = node def remove(self, item): # 删除节点 pos 从0开始 cur = self._head while cur is not None: if cur.elem == item: if cur == self._head: self._head = cur.next if cur.next: # 判断链表是否只有一个节点 cur.next.prev = None else: cur.prev.next = cur.next if cur.next: cur.next.prev = cur.prev break else: cur = cur.next

单项循环链表：

和单链表唯一的区别就是，最后一个节点的Next不指向None，而是指向首节点

在单向循环链表中，特别需要注意remove方法：

首先需要考虑删除节点是首节点，尾节点，中间节点。其次考虑这个链表是否为空链表，单个链表，需要每种情况都考虑进去，同时循环退出条件也很重要，建议结合图形来完成代码

class Node(object): # 节点 def __init__(self, elem): self.elem = elem self.next = None pass class SingelCycleList(object): # 单项循环链表 def __init__(self, node=None): self._head = node if node: node.next = node def is_empty(self): # 链表是否为空 return self._head is None def length(self): # 链表长度 if self.is_empty(): return 0 cur = self._head count = 1 while cur.next is not self._head: count = count + 1 cur = cur.next return count def travel(self): # 遍历整个链表 if self.is_empty(): return cur = self._head while cur.next is not self._head: print(cur.elem, end=" ") cur = cur.next # 退出循环，cur指向尾节点，但是尾节点元素并未打印 print(cur.elem) print("") def add(self, item): # 链表头部添加元素 node = Node(item) if self.is_empty(): self._head = node node.next = self._head else: node.next = self._head cur = self._head while cur.next is not self._head: cur = cur.next cur.next = node self._head = node def append(self, item): # 链表尾部添加元素 node = Node(item) if self.is_empty(): self._head = node node.next = self._head else: cur = self._head while cur.next is not self._head: cur = cur.next cur.next = node node.next = self._head def insert(self, pos, item): # 指定位置添加元素 if pos <= 0: self.add(item) elif pos >= (self.length() - 1): self.append(item) else: node = Node(item) cur = self._head count = 0 while count < (pos - 1): count += 1 cur = cur.next # 当循环退出后，pre指向pos-1的位置 node.next = cur.next cur.next = node def remove(self, item): # 删除节点 pos 从0开始 if self.is_empty(): return cur = self._head pre = None while cur.next is not self._head: if cur.elem == item:#判断是否为头节点 if cur == self._head: # 头节点 # 找位尾节点 rear = self._head while rear.next is not self._head: rear = rear.next self._head = cur.next rear.next = self._head else: # 中间节点 pre.next = cur.next return else: pre = cur cur = cur.next # 退出循环，代表尾节点 if cur.elem is item: if cur is self._head: # 链表中只有一个节点 self._head = None else: pre.next = cur.next def search(self, item): # 查找节点是否存在 if self.is_empty(): return False cur = self._head while cur.next is not self._head: if cur.elem == item: return True else: cur = cur.next if cur.elem is item: return True return False