【3】数据结构的双向链表章

双向链表的定义

• 结点结构组成：数据域（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()