说明
1、更复杂的链表是双向链表或双面链表。每个节点有两个链接:一个指向前一个节点，这个节点是第一个。
2、一个节点指向空值，另一个指向下一个节点，当该节点指向最后一个节点时指向空值。
操作方法
is_empty()链表是否为空。
length(链表长度。
travel)经历链表。
添加add(item)链表头部。
添加到append(item)链表的尾部。
添加insert(pos、item)指定位置。
remove删除节点。
搜索节点是否存在。
实例
class Node(object): def __init__(self, elem): """ :param elem: 表元素域 next：下一结点链接域 cursor(cur)：游标 """ self.elem = elem # 定义next指向空 self.next = None # 定义next指向空 self.prev = None class DoubleLinkList(object): """ 一种更复杂的链表是“双向链表"或“双面链表"。每个节点有两个链接: 一个指向前一个节点，当此节点为第 一个节点时，指向空值;而另一个指向下一个节点，当此节点为最后一个节点时，指向空值。 """ def __init__(self, node=None): self._head = node # node.elem node.next def is_empty(self): """链表是否为空 """ return self._head is None def length(self): """链表长度""" # cur游标，用来移动遍历节点 cur = self._head count = 0 while cur is not None: count += 1 cur = cur.next # count 记录数量 return count def travel(self): """遍历整个链表""" cur = self._head while cur is not None: print(cur.elem, end=' ') cur = cur.next def add(self, item): """链表头部添加元素：头插法""" node = Node(item) # node的next指向_head node.next = self._head # _head指向新节点 self._head = node node.next.prev = 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): """ pos: pos从0开始 pre:指定节点前一节点，相当于游标 node：插入的指定节点 指定位置添加元素 """ # if pos<=0 头插法 if pos <= 0: self.add(item) # elif pos>(self.length()-1) 尾插法 elif pos > (self.length() - 1): self.append(item) # else 插入法 else: cur = self._head count = 0 # 当循环退出后，cur指向pos while count < pos: count += 1 cur = cur.next # 当循环退出后，cur指向pos位置 node = Node(item) # 方式1： node.next = cur node.prev = cur.prev cur.prev.next = node cur.prev = node # 方式2： # node.next = cur # node.prev = cur.prev # cur.prev = node # node.prev.next = node def remove(self, item): """删除元素""" # 考虑删除头部、尾部、中间节点 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 def search(self, item): """查找节点是否存在""" # 1. 创建游标 cur = self._head # 2. 遍历游标 while cur is not None: # 3. cur.elem = item if cur.elem == item: return True else: cur = cur.next return False if __name__ == '__main__': DLL = DoubleLinkList() DLL.is_empty() l1 = DLL.length() print(l1) DLL.append(55) DLL.is_empty() l2 = DLL.length() print(l2) DLL.append(2) DLL.add(8) DLL.append(3) DLL.append(4) DLL.append(5) # 55 1 8 2 3 4 DLL.insert(-1, 9) # 9 8 55 2 1 8 2345 DLL.insert(2, 100) # 9 8 100 55 2 1 8 2345 DLL.travel()
以上就是python双向链表的概念介绍，希望对大家有所帮助。更多Python学习指路：
本文教程操作环境：windows7系统、Python 3.9.1，DELL G3电脑。