python实现单链表,双链表合并python
本文主要详细介绍了基于python的双向链表的实现。本文中的示例代码非常详细,具有一定的参考价值。感兴趣的朋友可以参考一下。
00-1010一、建立链表节点二。实现一个链表类III。在一些面试或扣分题中要求用双向链表实现测试逻辑。下面是一个基于python的双向链表实现。
目录
类别节点:
def __init__(self,key,value):
初始化方法
:参数键:
:参数值:
self.key=key
自我价值=价值
self.prev=无
self.next=无
def __str__(self):
val={%s: %s} % (self.key,self.value)
返回值
def __repr__(self):
val={%s: %s} % (self.key,self.value)
返回值
除了一些节点的基本属性,还有__str__方法自定义print(node)的字符串描述(类似Java的toString()),以及__repr__方法自定义直接调用node类时的字符串描述。
一、构建链表节点
逻辑主要包括添加头、添加尾、删除头、删除尾、删除任意节点。所有对双向链表的操作都是基于这些方法,具体流程写在注释里。
class DoubleLinkedList:
def __init__(self,capacity=0xffffffff):
双向链表
:param capacity:链表容量初始化为int 2 32-1的最大值
:返回:
自我能力=能力
self.size=0
self.head=无
self.tail=无
def __add_head(self,node):
向链表头添加一个节点。
头节点不存在。新添加的节点是头节点和尾节点。
头节点已经存在。新添加的节点是新的头节点。
3360 ParamNode 3360要添加的节点
:返回:个添加的节点
#标题节点为空
如果不是自己. head:
self.head=node
self.tail=node
self.head.next=无
self.tail.prev=None
#头节点不为空
else:
node.next=self.head
self.head.prev=node
self.head=node
self.head.prev=None
self.size=1
返回节点
def __add_tail(self,node):
向链表的末尾添加一个节点
尾节点不存在。新添加的节点是头节点和尾节点。
尾节点已经存在。新添加的节点是新的尾节点。
3360参数节点3360添加的节点
:返回:个添加的节点
#尾节点为空。
如果不是self.tail:
self.tail=node
self.head=node
self.head.next=无
self.tail.prev=None
#尾巴
部节点不为空
else:
node.prev = self.tail
self.tail.next = node
self.tail = node
self.tail.next = None
self.size += 1
return node
def __remove_head(self):
"""
删除头部节点
头部节点不存在 返回None
头部节点已存在 判断链表节点数量 删除头部节点
:return: 头部节点
"""
# 头部节点不存在
if not self.head:
return None
# 链表至少存在两个节点
head = self.head
if head.next:
head.next.prev = None
self.head = head.next
# 只存在头部节点
else:
self.head = self.tail = None
self.size -= 1
return head
def __remove_tail(self):
"""
删除尾部节点
尾部节点不存在 返回None
尾部节点已存在 判断链表节点数量 删除尾部节点
:return: 尾部节点
"""
# 尾部节点不存在
if not self.tail:
return None
# 链表至少存在两个节点
tail = self.tail
if tail.prev:
tail.prev.next = None
self.tail = tail.prev
# 只存在尾部节点
else:
self.head = self.tail = None
self.size -= 1
return tail
def __remove(self, node):
"""
删除任意节点
被删除的节点不存在 默认删除尾部节点
删除头部节点
删除尾部节点
删除其他节点
:param node: 被删除的节点
:return: 被删除的节点
"""
# 被删除的节点不存在
if not node:
node = self.tail
# 删除的是头部节点
if node == self.head:
self.__remove_head()
# 删除的是尾部节点
elif node == self.tail:
self.__remove_tail()
# 删除的既不是头部也不是尾部节点
else:
node.next.prev = node.prev
node.prev.next = node.next
self.size -= 1
return node
def pop(self):
"""
弹出头部节点
:return: 头部节点
"""
return self.__remove_head()
def append(self, node):
"""
添加尾部节点
:param node: 待追加的节点
:return: 尾部节点
"""
return self.__add_tail(node)
def append_front(self, node):
"""
添加头部节点
:param node: 待添加的节点
:return: 已添加的节点
"""
return self.__add_head(node)
def remove(self, node=None):
"""
删除任意节点
:param node: 待删除的节点
:return: 已删除的节点
"""
return self.__remove(node)
def print(self):
"""
打印当前链表
:return:
"""
node = self.head
line =
while node:
line += %s % node
node = node.next
if node:
line += =>
print(line)
三、测试逻辑
if __name__ == __main__:double_linked_list = DoubleLinkedList(10)
nodes = []
# 构建十个节点的双向列表
for i in range(10):
node_item = Node(i, i)
nodes.append(node_item)
double_linked_list.append(nodes[0])
double_linked_list.print()
double_linked_list.append(nodes[1])
double_linked_list.print()
double_linked_list.pop()
double_linked_list.print()
double_linked_list.append_front(nodes[2])
double_linked_list.print()
double_linked_list.append(nodes[3])
double_linked_list.print()
double_linked_list.remove(nodes[3])
double_linked_list.print()
double_linked_list.remove()
double_linked_list.print()
测试结果:
以上就是本文的全部内容,希望对大家的学习有所帮助,也希望大家多多支持盛行IT软件开发工作室。
郑重声明:本文由网友发布,不代表盛行IT的观点,版权归原作者所有,仅为传播更多信息之目的,如有侵权请联系,我们将第一时间修改或删除,多谢。