Python双链表原理与实现方法详解

2023-07-31 20:17:03 71

本文实例讲述了Python双链表原理与实现方法。分享给大家供大家参考，具体如下：

Python实现双链表

文章目录

Python实现双链表
- 单链表与双链表比较
- 双链表的实现
  - 定义链表节点
  - 初始化双链表
  - 判断链表是否为空
  - 双链表尾部添加元素
  - 双链表头部添加节点：
  - 双链表表头删除
  - 双链表按位置插入
  - 双链表删除指定节点
  - 完整代码

单链表与双链表比较

双链表比单链表多一个前驱指针位置，空间效率不占优势
由于双链表中的节点既可以向前也可以向后，相比单链表在查找方面效率更高（可使用二分法）

双链表的实现

定义链表节点

classNode(object):
def__init__(self,value=None,prev=None,next=None):
self.value=value	#节点数据域
self.prev=prev	#节点前驱指针
self.next=next	#节点后继指针

初始化双链表

在双链表类的构造方法中定义头指针以及链表长度属性

classdoubleLinked(object):

def__init__(self):
self.head=Node()	#头指针节点，用于确定链表第一个节点，不计入链表实际长度
self.length=0

判断链表是否为空

通过实例属性self.length是否为0判断链表是否为空

#判断链表是否为空
defis_Empty(self):
returnself.length==0

双链表尾部添加元素

根据传入的value值创建node节点对象
判断是否为空，若为空则插入节点的前驱节点为head头指针节点,head头指针指向node
如果链表非空：
- 通过while循环判断当前节点的后继节点是否为None，找到尾节点
- 找到尾节点后，将尾节点指向待添加节点，待添加节点前驱节点域指向原伪节点
- 长度+1

#尾部添加
defappend(self,value):
node=Node(value)
ifself.length==0:
node.prev=self.head
self.head.next=node
else:
curnode=self.head.next
whilecurnode.next!=None:
curnode=curnode.next
curnode.next=node
node.prev=curnode
self.length+=1

双链表头部添加节点：

调用类方法is_Empty()判断是否为空，若为空则直接调用append()方法
当链表非空时
- 首先创建待添加节点对象node
- 设置中间变量存放原头指针指向的节点
- 将头指针重新指向待添加节点
- 新添加节点后驱指针域指向中间变量(即原第一个节点)
- 中间变量前驱指针域指向新添加节点
- 链表长度+1

#头部添加
defadd(self,value):
ifself.is_Empty():
self.append(value)
node=Node(value)
curnode=self.head.next
self.head.next=node
node.next=curnode
curnode.prev=node
self.length+=1

双链表表头删除

老样子，依旧要先判断原链表是否为空，为空的时候返回False
链表不为空时：
- 将头指针指向的节点存放到中间变量curnode
- 将头指针指向的节点指向头指针(也就是第一个节点现在变成了头指针)
- 新头指针指向中间变量的后驱节点
- 链表长度-1

#删除表头节点
defremove(self):
ifself.is_Empty():
returnFalse
curnode=self.head.next
self.head=self.head.next
self.head.next=curnode.next
self.length-=1

双链表按位置插入

接收两个位置参数，postion和value
创建待插入节点对象
变量curnode存放当前节点，变量i初始值为2(位置参数<2时，默认插入到第二个位置，>2时，通过while循环找到指定位置节点再进行插入)
找到指定位置后，待插入节点的后驱指针指向当前节点curnode的后继节点，待插入节点的前驱节点为当前节点。
当前节点的原后驱节点的前驱指针域指向待插入节点，当前节点curnode的后驱节点变更为插入节点
链表长度+1

#插入到指定位置
definsert(self,postion,value):
node=Node(value)
curnode=self.head.next
i=2
whilei

双链表删除指定节点

依旧需要判断是否为空，为空时返回False
链表不为空时：
- 设置中间变量curnode存放当前节点
- while循环找到相匹配的值的节点
- 找到相应节点后，应删除节点的前驱节点的后继节点更改为应删除节点的后继节点；应删除节点的后继节点的前驱更改为应删除节点的前驱；
- 应删除节点后继指针指向自己
- 链表长度-1

#删除指定节点
defdelete(self,value):
ifself.is_Empty():
returnFalse
curnode=self.head.next
whilecurnode.value!=value:
curnode=curnode.next
curnode.prev.next=curnode.next
curnode.next.prev=curnode.prev
curnode.next=curnode
self.length-=1

完整代码

classNode(object):
def__init__(self,value=None,prev=None,next=None):
self.value=value
self.prev=prev
self.next=next


classdoubleLinked(object):

def__init__(self):
self.head=Node()
self.length=0

def__iter__(self):
fornodeinself.iter_node():
yieldnode.value

#对链表进行可迭代操作
defiter_node(self):
curnode=self.head.next
whilecurnode.next!=None:
yieldcurnode
curnode=curnode.next
ifcurnode.next==None:
yieldcurnode

#判断链表是否为空
defis_Empty(self):
returnself.length==0

#尾部添加
defappend(self,value):
node=Node(value)
ifself.length==0:
node.prev=self.head
self.head.next=node
else:
curnode=self.head.next
whilecurnode.next!=None:
curnode=curnode.next
curnode.next=node
node.prev=curnode
self.length+=1

#头部添加
defadd(self,value):
ifself.is_Empty():
self.append(value)
node=Node(value)
curnode=self.head.next
self.head.next=node
node.next=curnode
curnode.prev=node
self.length+=1

#插入到指定位置
definsert(self,postion,value):
node=Node(value)
curnode=self.head.next
i=2
whilei
运行结果：

True

第1个链表节点的值:4

第2个链表节点的值:10

第3个链表节点的值:1

第4个链表节点的值:5

更多关于Python相关内容感兴趣的读者可查看本站专题：《Python数据结构与算法教程》、《Python加密解密算法与技巧总结》、《Python编码操作技巧总结》、《Python函数使用技巧总结》、《Python字符串操作技巧汇总》及《Python入门与进阶经典教程》
希望本文所述对大家Python程序设计有所帮助。
声明：本文内容来源于网络，版权归原作者所有，内容由互联网用户自发贡献自行上传，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任。如果您发现有涉嫌版权的内容，欢迎发送邮件至：czq8825#qq.com（发邮件时，请将#更换为@）进行举报，并提供相关证据，一经查实，本站将立刻删除涉嫌侵权内容。

Python双链表原理与实现方法详解

Python实现双链表

文章目录

单链表与双链表比较

双链表的实现

定义链表节点

初始化双链表

判断链表是否为空

双链表尾部添加元素

双链表头部添加节点：

双链表表头删除

双链表按位置插入

双链表删除指定节点

完整代码

热门推荐

随机推荐