目录标题
- 双向链表的定义
- 双向链表的初始化
- 双向链表的创建
- 插入操作
- 删除操作
- 双向链表总代码与调试
双向链表的定义
-
结点结构组成：数据域（data）、指针域（pre）、指针域（next）。其中，
- data存储结点的值
- pre直接前驱结点的地址
- next直接后继结点的地址
-
定义：在单链表中的每一个结点中再增加一个指向其前驱的指针域，该中方式形式的链表成为双向链表。
-
结点示意图
-
双向链表逻辑结构示意图
-
代码定义双向链表结点
class Node:"""定义双向链表结点类型"""def __init__(self, data):# 存储结点中的数据域self.data = data# 指向后继结点的指针域nextself.next = None# 指向前驱结点的指针域preself.pre = None
双向链表的初始化
- 初始化双向链表
class DLinkedList:"""双向链表的定义"""def __init__(self):"""双向链表的初始化"""self.head = Node(None)
- 判断双向链表是否为空
def isEmpty(self):"""判断双向链表是否为空表:return: true or false"""# 如果头结点的next域为none，则返回True，否则返回falsereturn self.head.next is None
- 求双向链表的长度
def getLength(self):"""获取双向链表的长度:return: 当前双向链表中元素的个数"""# length用于计算双向链表的长度length = 0# 声明cur指针，用于遍历表cur = self.head.nextwhile cur != None:length += 1cur = cur.nextreturn length
- 展示双向链表
def display(self):"""遍历双向链表，进行扫描展示:return:"""if self.isEmpty():print("当前双向链表为空")returnprint("双向链表的元素为:", end="")# 循环遍历cur = self.head.nextwhile cur != None:print(cur.data, end="")cur =cur.nextprint()
双向链表的创建
def append(self, data):"""建立双向链表:param data: 待插入的元素:return:"""# 查找尾结点rear = self.headwhile rear.next != None:rear = rear.next# 创建新结点newNode = Node(data)# 将尾结点的next指针指向新结点rear.next = newNode# 将新结点的pre指针指向尾结点newNode.pre = rear
插入操作
-
核心思想
- 在双向链表第index个结点之前插入一个新的结点，通过四个操作调整指针的指向；
- 1.设置指针，指向第index个结点，将新结点的前驱指针指向指针cur所指向的结点的前驱结点
- 2.将指针cur所指向的结点的前驱结点的后继指针指向新结点
- 3.将新结点的后继指针指向cur所指向的结点
- 4.将指针cur所指向的结点的前驱指针指向新结点
-
插入示意图
-
代码定义插入法
def insert(self, index, data):"""双向链表中任意位置插入元素:param index: 待插入的元素位置:param data: 待插入元素的值:return:"""i = 1# 声明指针cur,用于遍历双向链表cur = self.head# 遍历while cur != None and i !=index + 1:cur = cur.nexti += 1# index非法情况if cur == None or i > self.getLength():raise IndexError('index 非法')# 创建新结点newNode = Node(data)# 将新结点的前驱指针指向指针cur所指向的结点的前驱结构newNode.pre = cur.pre# 将指针cur所指向的结点的前驱结点的后继指针指向新结点cur.pre.next = newNode# 将新结点的后继指针指向cur所指向的结点newNode.next = cur# 将指针cur所指向的结点的前驱指针指向新结点cur.pre = newNode
删除操作
- 核心思想
- 设置局域指针cur，遍历表，直到该指针指向要删除结点；
- 将指针cur所指向结点的前驱结点的next指针指向指针cur所指向结点的后继结点
- 将指针cur所指向结点的后继结点的pre指针指向指针cur指向结点的前驱结点
- 删除示意图
- 代码定义删除法
def delete(self, index):"""在双向链表中任意位置删除元素:param index: 待删除元素的位置:return: 被删除的元素"""# 若双向链表为空，抛出异常if self.isEmpty():raise IndexError('当前为空表！')# 找到需要删除结点的前一个结点i = 1cur = self.headwhile cur != None and i != index + 1:cur = cur.nexti += 1# 若index非法if cur == None or i > self.getLength():raise IndexError('index 非法')# 获取被删除元素data = cur.data# 将指针cur所指向结点的前驱结点的next指针指向指针cur所指向结点的后继结点cur.pre.next = cur.next# 将指针cur所指向结点的后继结点的pre指针指向指针cur指向结点的前驱结点cur.next.pre = cur.prereturn data
双向链表总代码与调试
- 双向链表：单链表的一个缺点是无法快速访问前驱结点，当查找某一元素，需要再次从头开始遍历查找，便有了双向链表。
- 相对于单链表，双向链表复杂一些，它多了一个前驱指针，插入与删除操作相对更复杂与易出错。
# 5.双向链表的实现
class Node:"""定义双向链表结点类型"""def __init__(self, data):# 存储结点中的数据域self.data = data# 指向后继结点的指针域nextself.next = None# 指向前驱结点的指针域preself.pre = Noneclass DLinkedList:"""双向链表的定义"""def __init__(self):"""双向链表的初始化"""self.head = Node(None)def isEmpty(self):"""判断双向链表是否为空表:return: true or false"""# 如果头结点的next域为none，则返回True，否则返回falsereturn self.head.next is Nonedef getLength(self):"""获取双向链表的长度:return: 当前双向链表中元素的个数"""# length用于计算双向链表的长度length = 0# 声明cur指针，用于遍历表cur = self.head.nextwhile cur != None:length += 1cur = cur.nextreturn lengthdef display(self):"""遍历双向链表，进行扫描展示:return:"""if self.isEmpty():print("当前双向链表为空")returnprint("双向链表的元素为:", end="")# 循环遍历cur = self.head.nextwhile cur != None:print(cur.data, end="")cur =cur.nextprint()# 建立双向链表def append(self, data):"""建立双向链表:param data: 待插入的元素:return:"""# 查找尾结点rear = self.headwhile rear.next != None:rear = rear.next# 创建新结点newNode = Node(data)# 将尾结点的next指针指向新结点rear.next = newNode# 将新结点的pre指针指向尾结点newNode.pre = reardef insert(self, index, data):"""双向链表中任意位置插入元素:param index: 待插入的元素位置:param data: 待插入元素的值:return:"""i = 1# 声明指针cur,用于遍历双向链表cur = self.head# 遍历while cur != None and i !=index + 1:cur = cur.nexti += 1# index非法情况if cur == None or i > self.getLength():raise IndexError('index 非法')# 创建新结点newNode = Node(data)# 将新结点的前驱指针指向指针cur所指向的结点的前驱结构newNode.pre = cur.pre# 将指针cur所指向的结点的前驱结点的后继指针指向新结点cur.pre.next = newNode# 将新结点的后继指针指向cur所指向的结点newNode.next = cur# 将指针cur所指向的结点的前驱指针指向新结点cur.pre = newNodedef delete(self, index):"""在双向链表中任意位置删除元素:param index: 待删除元素的位置:return: 被删除的元素"""# 若双向链表为空，抛出异常if self.isEmpty():raise IndexError('当前为空表！')# 找到需要删除结点的前一个结点i = 1cur = self.headwhile cur != None and i != index + 1:cur = cur.nexti += 1# 若index非法if cur == None or i > self.getLength():raise IndexError('index 非法')# 获取被删除元素data = cur.data# 将指针cur所指向结点的前驱结点的next指针指向指针cur所指向结点的后继结点cur.pre.next = cur.next# 将指针cur所指向结点的后继结点的pre指针指向指针cur指向结点的前驱结点cur.next.pre = cur.prereturn dataif __name__ == '__main__':# print('PyCharm')# 1.双向链表初始化list = DLinkedList()list.display()# 2.创建双向链表for i in range(10):list.append(chr(ord('A') + i))print('尾插入操作，', end="")list.display()# 3.获取双向链表的长度length = list.getLength()print('双向链表的长度为：', length)# 4.在双向链表中任意位置插入元素list.insert(2, 'Y')list.display()# 4.在双向链表中任意位置删除元素data = list.delete(2)print("被删除元素为：", data)list.display()