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):
        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 = next

class 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 = 1
for 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程序设计有所帮助。

(0)

相关推荐

  • Python双向循环链表实现方法分析

    本文实例讲述了Python双向循环链表实现方法.分享给大家供大家参考,具体如下: 最近身边的朋友在研究用python来实现数据结构.遇到一个问题就是双向循环链表的实现,改指向的时候总是发蒙. 我自己尝实现了一个python的双向循环链表.附上代码,希望对大家有帮助. 如果不懂什么是双向循环链表的伙伴,需要补习一下数据结构的基础之后哦~~~ 在python当中 用一个类Node 来实现链表的节点,节点数据有三个变量: prev:前驱指针: 用于指向当前节点前一个节点 next: 后继指针  用于指

  • python双向链表实现实例代码

    示意图: python双向链表实现代码: 复制代码 代码如下: #!/usr/bin/python# -*- coding: utf-8 -*- class Node(object):    def __init__(self,val,p=0):        self.data = val        self.next = p        self.prev = p class LinkList(object):    def __init__(self):        self.he

  • Python编程实现双链表,栈,队列及二叉树的方法示例

    本文实例讲述了Python编程实现双链表,栈,队列及二叉树的方法.分享给大家供大家参考,具体如下: 1.双链表 class Node(object): def __init__(self, value=None): self._prev = None self.data = value self._next = None def __str__(self): return "Node(%s)"%self.data class DoubleLinkedList(object): def

  • Python单向链表和双向链表原理与用法实例详解

    本文实例讲述了Python单向链表和双向链表原理与用法.分享给大家供大家参考,具体如下: 链表是一种数据结构,链表在循环遍历的时候效率不高,但是在插入和删除时优势比较大. 链表由一个个节点组成. 单向链表的节点分为两个部分:存储的对象和对下一个节点的引用.注意是指向下一个节点. 而双向链表区别于单向链表的是它是由三个部分组成:存储的对象.对下一个节点的引用.对上一个节点的引用,可以实现双向遍历. 单向列表的结构如下图: head是头节点,tail是尾节点,每个节点由Data存储对象和Next对下

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

    本文实例讲述了Python单链表原理与实现方法.分享给大家供大家参考,具体如下: Python实现单链表 关于链表 链表(Linked List)是由许多相同数据类型的数据项按照特定顺序排列而成的线性表. 链表中个数据项在计算机内存中的位置是不连续且随机的,数组在内存中是连续的. 链表数据的插入和删除很方便,但查找数据效率低下,不能像数组一样随机读取数据. 单链表的实现 一个单向链表的节点由数据字段和指针组成,指针指向下一个元素所在内存地址 定义一个链表节点类,self.value实例属性表示节

  • Python二叉搜索树与双向链表转换实现方法

    本文实例讲述了Python二叉搜索树与双向链表实现方法.分享给大家供大家参考,具体如下: # encoding=utf8 ''' 题目:输入一棵二叉搜索树,将该二叉搜索树转换成一个排序的双向链表. 要求不能创建任何新的结点,只能调整树中结点指针的指向. ''' class BinaryTreeNode(): def __init__(self, value, left = None, right = None): self.value = value self.left = left self.

  • python双向链表原理与实现方法详解

    本文实例讲述了python双向链表原理与实现方法.分享给大家供大家参考,具体如下: 双向链表 一种更复杂的链表是"双向链表"或"双面链表".每个节点有两个链接:一个指向前一个节点,当此节点为第一个节点时,指向空值:而另一个指向下一个节点,当此节点为最后一个节点时,指向空值. 操作 is_empty() 链表是否为空 length() 链表长度 travel() 遍历链表 add(item) 链表头部添加 append(item) 链表尾部添加 insert(pos,

  • Python二叉搜索树与双向链表转换算法示例

    本文实例讲述了Python二叉搜索树与双向链表转换算法.分享给大家供大家参考,具体如下: 题目描述 输入一棵二叉搜索树,将该二叉搜索树转换成一个排序的双向链表.要求不能创建任何新的结点,只能调整树中结点指针的指向. 普通的二叉树也可以转换成双向链表,只不过不是排序的 思路: 1. 与中序遍历相同 2. 采用递归,先链接左指针,再链接右指针 代码1,更改doubleLinkedList,最后返回list的第一个元素: class TreeNode: def __init__(self, x): s

  • python如何实现单链表的反转

    这篇文章主要介绍了python如何实现单链表的反转,文中通过示例代码介绍的非常详细,对大家的学习或者工作具有一定的参考学习价值,需要的朋友可以参考下 代码如下 # coding=utf-8 class Node: def __init__(self, data=None, next=None): self.data = data self.next = next def Reserver(link): pre = link cur = link.next pre.next = None whil

  • Python数据结构之双向链表的定义与使用方法示例

    本文实例讲述了Python数据结构之双向链表的定义与使用方法.分享给大家供大家参考,具体如下: 和单链表类似,只不过是增加了一个指向前面一个元素的指针而已. 示意图: python 实现代码: #!/usr/bin/python # -*- coding: utf-8 -*- class Node(object): def __init__(self,val,p=0): self.data = val self.next = p self.prev = p class LinkList(obje

随机推荐