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

时间:2021-05-22

本文实例讲述了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): node = Node(value) if self.length == 0: node.prev = self.head self.head.next = node else: curnode = self.head.next while curnode.next != None: curnode = curnode.next curnode.next = node node.prev = curnode self.length += 1

双链表头部添加节点:

  • 调用类方法is_Empty()判断是否为空,若为空则直接调用append()方法

  • 当链表非空时

    • 首先创建待添加节点对象node
    • 设置中间变量存放原头指针指向的节点
    • 将头指针重新指向待添加节点
    • 新添加节点后驱指针域指向中间变量(即原第一个节点)
    • 中间变量前驱指针域指向新添加节点
    • 链表长度+1
  • # 头部添加 def add(self, value): if self.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
  • # 删除表头节点 def remove(self): if self.is_Empty(): return False 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

  • # 插入到指定位置 def insert(self, postion, value): node = Node(value) curnode = self.head.next i = 2 while i < postion: i += 1 curnode = curnode.next node.next = curnode.next node.prev = curnode curnode.next.prev = node curnode.next = node self.length += 1

双链表删除指定节点

  • 依旧需要判断是否为空,为空时返回False

  • 链表不为空时:

    • 设置中间变量curnode存放当前节点
    • while循环找到相匹配的值的节点
    • 找到相应节点后,应删除节点的前驱节点的后继节点更改为应删除节点的后继节点;应删除节点的后继节点的前驱更改为应删除节点的前驱;
    • 应删除节点后继指针指向自己
    • 链表长度-1
  • # 删除指定节点 def delete(self, value): if self.is_Empty(): return False curnode = self.head.next while curnode.value != value: curnode = curnode.next curnode.prev.next = curnode.next curnode.next.prev = curnode.prev curnode.next = curnode self.length -= 1

完整代码

class Node(object): def __init__(self, value=None, prev=None, next=None): self.value = value self.prev = prev self.next = nextclass doubleLinked(object): def __init__(self): self.head = Node() self.length = 0 def __iter__(self): for node in self.iter_node(): yield node.value # 对链表进行可迭代操作 def iter_node(self): curnode = self.head.next while curnode.next != None: yield curnode curnode = curnode.next if curnode.next == None: yield curnode # 判断链表是否为空 def is_Empty(self): return self.length == 0 # 尾部添加 def append(self, value): node = Node(value) if self.length == 0: node.prev = self.head self.head.next = node else: curnode = self.head.next while curnode.next != None: curnode = curnode.next curnode.next = node node.prev = curnode self.length += 1 # 头部添加 def add(self, value): if self.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 # 插入到指定位置 def insert(self, postion, value): node = Node(value) curnode = self.head.next i = 2 while i < postion: i += 1 curnode = curnode.next node.next = curnode.next node.prev = curnode curnode.next.prev = node curnode.next = node self.length += 1 # 删除表头节点 def remove(self): if self.is_Empty(): return False curnode = self.head.next self.head = self.head.next self.head.next = curnode.next self.length -= 1 # 删除指定节点 def delete(self, value): if self.is_Empty(): return False curnode = self.head.next while curnode.value != value: curnode = curnode.next curnode.prev.next = curnode.next curnode.next.prev = curnode.prev curnode.next = curnode self.length -= 1# 测试linkedlist = doubleLinked()print(linkedlist.is_Empty())linkedlist.append(1)linkedlist.append(3)linkedlist.append(5)linkedlist.add(4)linkedlist.add(2)linkedlist.insert(3,10)linkedlist.remove()linkedlist.delete(3)# 遍历打印i = 1for node in linkedlist: print("第%d个链表节点的值: %d"%(i, node)) i += 1

运行结果:

True
第1个链表节点的值: 4
第2个链表节点的值: 10
第3个链表节点的值: 1
第4个链表节点的值: 5

更多关于Python相关内容感兴趣的读者可查看本站专题:《Python数据结构与算法教程》、《Python加密解密算法与技巧总结》、《Python编码操作技巧总结》、《Python函数使用技巧总结》、《Python字符串操作技巧汇总》及《Python入门与进阶经典教程》

希望本文所述对大家Python程序设计有所帮助。

声明:本页内容来源网络,仅供用户参考;我单位不保证亦不表示资料全面及准确无误,也不保证亦不表示这些资料为最新信息,如因任何原因,本网内容或者用户因倚赖本网内容造成任何损失或损害,我单位将不会负任何法律责任。如涉及版权问题,请提交至online#300.cn邮箱联系删除。

相关文章