Python双链表原理与实现方法详解
需积分: 9 159 浏览量
2020-12-20
15:16:55
上传
评论
收藏 62KB PDF 举报
Python双链表原理与实现方法详解双链表原理与实现方法详解
本文实例讲述了Python双链表原理与实现方法。分享给大家供大家参考，具体如下：
Python实现双链表实现双链表
文章目录文章目录
Python实现双链表
单链表与双链表比较
双链表的实现
定义链表节点
初始化双链表
判断链表是否为空
双链表尾部添加元素
双链表头部添加节点：
双链表表头删除
双链表按位置插入
双链表删除指定节点
完整代码
单链表与双链表比较单链表与双链表比较
双链表比单链表多一个前驱指针位置，空间效率不占优势
由于双链表中的节点既可以向前也可以向后，相比单链表在查找方面效率更高（可使用二分法）
双链表的实现双链表的实现
定义链表节点定义链表节点
class Node(object):
def __init__(self, value=None, prev=None, next=None):
self.value = value # 节点数据域
self.prev = prev # 节点前驱指针
self.next = next # 节点后继指针
初始化双链表初始化双链表
在双链表类的构造方法中定义头指针以及链表长度属性
class doubleLinked(object):
def __init__(self):
self.head = Node() # 头指针节点，用于确定链表第一个节点，不计入链表实际长度
self.length = 0
判断链表是否为空判断链表是否为空
通过实例属性self.length是否为0判断链表是否为空
# 判断链表是否为空
def is_Empty(self):
return self.length == 0
双链表尾部添加元素双链表尾部添加元素
根据传入的value值创建node节点对象
判断是否为空，若为空则插入节点的前驱节点为head头指针节点,head头指针指向node
如果链表非空：
通过while循环判断当前节点的后继节点是否为None，找到尾节点
找到尾节点后，将尾节点指向待添加节点，待添加节点前驱节点域指向原伪节点
长度+1
# 尾部添加
def append(self, value):
weixin_38557768
- 粉丝: 7
- 资源: 923
评论0