python 链表数据结构,双链表合并python

　　单链表只有一个指向直接后继的指针来表示节点之间的逻辑关系，可以很容易地从任意一个节点开始寻找它的后继，但是很难找到前任。双链表就是为了解决这个问题，用两个指针来表示节点之间的逻辑关系。本文将重点介绍双向链表的相关操作，有需要的可以参考一下。

　　00-1010 0.学习目标1。双向链表简介1.1双向链表简介1.2节点类1.3双向链表的优缺点2。双向链表的实现2.1双向链表的初始化2.2获取双向链表的长度2.3读取指定位置元素2.4查找指定元素2.5在指定位置插入新元素2.6删除指定位置元素2.7其他有用的操作3 .双向链表的应用3.1双向链表的应用实例3.2利用双向链表的基本运算实现复杂运算。

目录

　　单链表只有一个指向直接后继的指针来表示节点之间的逻辑关系，所以从任意一个节点开始查找它的后继比较方便，但是查找前身比较困难。双向链表就是为了解决这个问题，它用两个指针来表示节点之间的逻辑关系。在上一节中，我们已经讨论了单链表的实现及其相关操作。在本节中，我们将重点介绍双向链表的实现及其相关操作。

　　通过本节，您应掌握以下内容：

　　双向链表的基本概念及其优缺点

　　双向链表基本操作的实现

　　利用双向链表的基本操作实现复杂算法

0. 学习目标

1. 双向链表简介

　　双向链表类似于单向链表。它还使用了节点和指针的相关概念，属于顺序表的链式存储结构。单链表和双链表的唯一区别是双链表用两个指针来表示节点之间的逻辑关系，增加了一个指向其直接前身的指针字段。这样，形成的链表有两个链3354个不同方向的前序链和后继链，所以称为双链表，或双链表。

1.1 双向链表介绍

　　在一个双向链表中，根据一个已知节点找到它的直接前一个节点和找到它的直接后一个节点一样方便。和单链表一样，双链表也可以分为有头节点和无头节点两类。本节只讨论有头节点的双向链表。双向链表的节点示意图如下。每个节点有两个指针，——，指向指向直接后继的下一个指针和指向直接前一个的前一个指针：

　　Python实现的双向链表的节点类如下：

　　类别节点：

　　def __init__(self，data=None):

　　self.data=数据

　　self.next=无

　　self.previous=None

　　def __str__(self):

　　返回字符串(self.data)

　　前一个变量指向紧前一个节点，后一个变量保留对紧后一个节点的引用，数据变量用来存储数据，重载的__str__方法用来方便地打印节点对象。

1.2 双向链表结点类

　　双向链表的优点是给定双向链表中的一个节点，我们可以双向遍历它，直接访问它的前任节点。这样，在需要寻找前任的操作中，我们就不必从头遍历整个链表，大大方便了删除节点等操作。

　　双向链表的主要缺点如下：

　　每个节点都需要一个额外的前任指针，需要更多的空间；节点的插入或删除需要更多的指针修改操作。

1.3 双向链表优缺点

　　类似于单链表，我们来实现一个带头节点的双链表类，用头指针标识链表的开头。如果你还不了解单链表，可以参考《单链表及其操作实现》相关介绍。

2. 双向链表实现

　　双向链表初始化建立一个有前导节点的空单链表，其表长length初始化为0。此时，链表中没有元素节点。

　　只有一个头结点：

class DoublyLinkedList:
　　 def __init__(self, data=None):
　　 self.length = 0
　　 # 初始化头结点
　　 head_node = Node()
　　 self.head = head_node
　　

　　创建双向链表 DoublyLinkedList 对象的时间复杂度为O(1)。

　　NOTE：如果你还记得继承机制的话，我们也可以令 DoublyLinkedList 继承自在《单链表及其操作实现》中实现的 SinglyLinkedList，可以极大的化简双向链表的实现。

2.2 获取双向链表长度

　　求取双向链表长度只需要重载 __len__ 从对象返回 length 的值，因此时间复杂度为O(1)：

 def __len__(self):
　　 return self.length
　　

2.3 读取指定位置元素

　　双向链表中读取指定位置元素的算法与单链表完全相同，只需要使用后继链访问每一个结点即可，因此操作的复杂度同样为O(n)，接下来我们将重载 __getitem__ 操作实现读取链表指定位置元素的操作；同时，我们希望确保索引在可接受的索引范围内，否则将引发 IndexError 异常：

 def __getitem__(self, index):
　　 if index > self.length - 1 or index < 0:
　　 raise IndexError("DoublyLinkedList assignment index out of range")
　　 else:
　　 count = -1
　　 current = self.head
　　 while count < index:
　　 current = current.next
　　 count += 1
　　 return current.data
　　

　　类似的，我们也可以实现修改指定位置元素的操作，只需要重载 __setitem__ 操作，其复杂度同样为O(n)：

  def __setitem__(self, index, value):
　　        if index > self.length - 1 or index < 0:
　　            raise IndexError("DoublyLinkedList assignment index out of range")
　　        else:
　　            count = -1
　　            current = self.head
　　            while count < index:
　　                current = current.next
　　                count += 1
　　            current.data = value

2.4 查找指定元素

　　与单链表相同，当查找指定元素时，需要设置一个跟踪链表结点的指针 current，令其顺着 next 域依次指向每个结点，每指向一个结点就判断其值是否等于指定值 value，若是则返回该结点索引；否则继续往后搜索，如果链表中无此元素，则引发 ValueError 异常，其时间复杂度为O(n)：

 def locate(self, value):
　　 count = -1
　　 current = self.head
　　 while current != None and current.data != value:
　　 count += 1
　　 current = current.next
　　 if current and current.data == value:
　　 return count
　　 else:
　　 raise ValueError("{} is not in sequential list".format(value))
　　

2.5 在指定位置插入新元素

　　在指定位置插入新元素有两种不同的方法，一种是找到待插入位置的结点 current，然后将待插结点插入 current 之前；另一种方法是找到待插入位置结点的前驱结点 prev，然后待插结点插入 prev 之后，两种方法的操作略有不同，这里以第二种方法的操作为例，第一种方法的具体操作留给大家进行推导。

　　由于 prev 指向待插入位置的后继结点，因此如果插入位置为列表末尾，由于 prev.next = None，无法使用 prev.next.previous，而在链表中间部位 prev.next.previous = prev，所以显然插入链表中间位置和链表末尾的操作有所不同。

　　(1) 在双向链表的末尾插入一个结点步骤如下：

• 遍历列表直到最后一个结点，创建新结点；
• 将新节点的 previous 指针指向链表的最后一个结点；
• 更新原链表最后一个结点的 next 指针指向新结点。

　　(2) 在双链表中间插入结点与单链表类似，但是需要更多的步骤用于修改指针：

• 首先遍历链表到插入位置的前驱结点 prev，创建新结点；
• 新结点的 next 指针指向要插入新结点位置的下一个节点，新结点的 previous 指针指向 prev；
• 插入位置后继节点的 previous 指向新节点，prev 结点的 next 指针指向新节点。

　　算法实现如下所示：

 def insert(self, index, data):
　　 count = 0
　　 prev = self.head
　　 # 判断插入位置的合法性
　　 if index > self.length or index < 0:
　　 raise IndexError("DoublyLinkedList assignment index out of range")
　　 else:
　　 new_node = Node(data)
　　 while count < index:
　　 prev = prev.next
　　 count += 1
　　 new_node.previous = prev
　　 self.length += 1
　　 if prev.next:
　　 # 链表中间插入结点
　　 new_node.next = prev.next
　　 prev.next.previous = new_node
　　 prev.next = new_node
　　 else:
　　 # 链尾插入结点
　　 prev.next = new_node
　　

2.6 删除指定位置元素

　　删除指定位置元素，只需要找到相应位置结点 current，修改指针后，删除结点即可。需要注意的是，除了需要将 current 的前驱结点的 next 指针指向 current 的后继节点外，如果删除的并非链尾元素，还需要将 current 的后继节点的 previous 指针指向 current 的前驱结点：

　　算法实现如下所示：

 def get_node(self, index):
　　 """辅助函数，用于根据位置返回结点"""
　　 if index > self.length - 1 or index < 0:
　　 raise IndexError("SinglyLinkedList assignment index out of range")
　　 count = -1
　　 current = self.head
　　 while count < index:
　　 current = current.next
　　 count += 1
　　 return current
　　 def __delitem__(self, index):
　　 """删除指定位置元素"""
　　 if index > self.length - 1 or index < 0:
　　 raise IndexError("SinglyLinkedList assignment index out of range")
　　 else:
　　 current = self.get_node(index)
　　 if current:
　　 current.previous.next = current.next
　　 # 如果删除的并非最后一个结点
　　 if current.next:
　　 current.next.previous = current.previous
　　 self.length -= 1
　　 del current
　　

　　在插入和删除操作中，都是先确定操作位置，然后再进行插入和删除操作，所以其时间复杂度均为O(n)。

2.7 其它一些有用的操作

　　2.7.1 链表元素输出操作

　　将双向链表转换为字符串以便进行打印，使用 str 函数调用对象上的 __str__ 方法可以创建适合打印的字符串表示：

 def __str__(self):
　　 s = "["
　　 current = self.head.next
　　 count = 0
　　 while current != None:
　　 count += 1
　　 s += str(current)
　　 current = current.next
　　 if count < self.length:
　　 s += <-->
　　 s += "]"
　　 return s
　　

　　2.7.2 删除指定元素

　　与删除指定位置元素略有不同，删除指定元素需要在链表中删除第一个具有与给定值相同数据元素的结点，但修改指针的操作是类似的，其时间复杂度同样为O(n)：

 def del_value(self, value):
　　 current = self.head
　　 while current:
　　 if current.data == value:
　　 current.previous.next = current.next
　　 if current.next:
　　 current.next.previous = current.previous
　　 self.length -= 1 
　　 del current
　　 return
　　 else:
　　 current = current.next
　　 raise ValueError("The value provided is not present!")
　　

　　2.7.3 在链表尾部追加新元素

　　为了方便的在链表尾部追加新元素，可以实现函数 append：

 def append(self, data):
　　 new_node = Node(data)
　　 current = self.head
　　 while current.next:
　　 current = current.next
　　 current.next = new_node
　　 new_node.previous = current
　　 self.length += 1
　　

　　此算法的时间复杂度为O(n)，如果需要经常在链表尾部追加新元素，可以使用增加尾指针 tail 用于追踪链表的最后一个元素，利用尾指针在链表尾部追加新元素时间复杂度可以降至O(1)。

3. 双向链表应用

　　接下来，我们首先测试上述实现的双向链表，以验证操作的有效性，然后利用实现的基本操作来实现更复杂的算法。

3.1 双向链表应用示例

　　首先初始化一个链表 dllist，并在其中追加若干元素：

dllist = DoublyLinkedList()
　　# 在链表末尾追加元素
　　dllist.append(apple)
　　dllist.append(banana)
　　dllist.append(orange)
　　# 在指定位置插入元素
　　dllist.insert(0, grape)
　　dllist.insert(4, lemon)
　　

　　我们可以直接打印链表中的数据元素、链表长度等信息：

print(双向链表 sllist 为：, dllist)
　　print(双向链表 sllist 长度为：, len(dllist))
　　print(双向链表 sllist 第0个元素为：, dllist[0])
　　# 修改数据元素
　　dllist[0] = pear
　　del(dllist[3])
　　print(双向修改链表 sllist 数据后：, dllist)
　　

　　以上代码输出如下：

双向链表 dllist 为： [grape<-->apple<-->banana<-->orange<-->lemon]
双向链表 dllist 长度为： 5
双向链表 dllist 第0个元素为： grape
修改双向链表 dllist 数据后： [pear<-->apple<-->banana<-->lemon]

　　

　　接下来，我们将演示在指定位置添加/删除元素、以及如何查找指定元素等：

# 修改数据元素
　　dllist[0] = pear
　　print(修改双向链表 dllist 数据后：, dllist)
　　dllist.insert(0, watermelon)
　　print(在位置 0 添加 watermelon 后双向链表链表 ddlist 数据：, dllist)
　　del(dllist[3])
　　print(删除位置 3 处元素后双向链表 ddlist 数据：, dllist)
　　dllist.append(lemon)
　　print(在尾部追加元素 lemon 后双向链表 ddlist 数据：, dllist)
　　dllist.del_value(lemon)
　　print(删除 lemon 后双向链表 dllist 数据：, dllist)
　　print(watermelon 在双向链表 dllist 中的索引为：, dllist.locate(orange))
　　

　　以上代码输出如下：

修改双向链表 dllist 数据后： [pear<-->apple<-->banana<-->orange<-->lemon]
在位置 0 添加 watermelon 后双向链表链表 ddlist 数据： [watermelon<-->pear<-->apple<-->banana<-->orange<-->lemon]
删除位置 3 后双向链表 ddlist 数据： [watermelon<-->pear<-->apple<-->orange<-->lemon]
在尾部追加元素 lemon 后双向链表 ddlist 数据： [watermelon<-->pear<-->apple<-->orange<-->lemon<-->lemon]
删除 lemon 后双向链表 dllist 数据： [watermelon<-->pear<-->apple<-->orange<-->lemon]
watermelon 在双向链表 dllist 中的索引为： 3

　　

3.2 利用双向链表基本操作实现复杂操作

　　[1] 利用双向链表的基本操作，合并两个双向链表：

def merge(dllist1, dllist2):
　　 current = dllist1.head
　　 while current.next:
　　 current = current.next
　　 if dllist2.head.next:
　　 tmp = dllist2.head.next
　　 current.next = tmp
　　 tmp.previous = current
　　 dllist1.length += len(dllist2)
　　 return dllist1
　　# 算法测试
　　dllist1 = DoublyLinkedList()
　　dllist2 = DoublyLinkedList()
　　for i in range(5):
　　 dllist1.append(i)
　　 dllist2.append((i+1)*5)
　　print(双向链表 dllist1：, dllist1)
　　print(双向链表 dllist2：, dllist2)
　　dllist = merge(dllist1, dllist2)
　　print(链表合并结果：, dllist)
　　

　　程序输出结果如下：

双向链表 dllist1： [0<-->1<-->2<-->3<-->4]
双向链表 dllist2： [5<-->10<-->15<-->20<-->25]
链表合并结果： [0<-->1<-->2<-->3<-->4<-->5<-->10<-->15<-->20<-->25]

　　

　　到此这篇关于Python数据结构之双向链表详解的文章就介绍到这了,更多相关Python双向链表内容请搜索盛行IT软件开发工作室以前的文章或继续浏览下面的相关文章希望大家以后多多支持盛行IT软件开发工作室！

郑重声明：本文由网友发布，不代表盛行IT的观点，版权归原作者所有，仅为传播更多信息之目的，如有侵权请联系，我们将第一时间修改或删除，多谢。