Python实现双向链表

之前写的单向链表和环形链表都只是单向的,只能单向遍历,不能根据后面的节点获取前面的节点,除非进行反转操作。

双向链表每个节点都有两个指针,这两个指针分别指向前后两个节点,这样就可以从任意一个节点从两个方向获取其他的所有节点,非常方便。但是由于每个节点有两个指针,所以双向链表比较消耗空间。

在设计双向链表时,通常会加上一个链表头指针,该链表头指针的数据字段不存放任何数据。

双向链表的可以是环形的,也可以不是环形的,如果是环形的话,那么最后一个节点的一个指针将指向链表头,链表头的一个指针将指向最后一个节点;如果不是环形的话,那么最后一个节点的一个指针和链表头的一个指针都将指向None。

我在这里实现的是一个环形的双向链表,这样我就可以从链表头开始,从两个方向中任意选择一个方向来进行操作。

我在这里主要实现了环形双向链表的:双向新增,双向遍历,双向插入,双向删除。

如图为双向环形链表示意图,每一个节点都被两个指针所指向,同时每个节点也指向了两个节点。

实现代码如下:

class Player:
    """节点类"""
    def __init__(self):
        """初始化姓名,分数,指针"""
        self.name = ''
        self.score = 0
        self.rlink = None
        self.llink = None
 
 
def ergodic(head, num=None, is_print=False, left=False):
    """遍历函数,num是遍历到哪一个位置序号,is_print是否触发打印方法,left表示是否由head开始往左遍历"""
    ptr = head
    count = 0
    while True:
        if num == count:
            break
 
        if not left:
            if ptr.rlink != head:
                ptr = ptr.rlink
            else:
                break
        else:
            if ptr.llink != head:
                ptr = ptr.llink
            else:
                break
        count += 1
        if is_print:
            print('No.'+str(count), ptr.llink.name if ptr.llink != head else 'head', '<---',
                  ptr.name, ptr.score, '--->', ptr.rlink.name if ptr.rlink != head else 'head')
    return ptr  # 返回遍历完成后的最后一个节点
 
 
head = Player()  # 初始化一个链表头指针,不用来存放任何数据
head.rlink = head  # 初始化右指针
head.llink = head  # 初始化左指针
 
 
while True:
    select = input("(1).新增   (2).查看   (3).插入   (4).删除   (5).离开\n输入:")
    if select == "1":  # 新增节点,分为右新增和左新增
        direction = input("(1).右新增   (2).左新增\n输入:")
        if direction not in ("1", "2"):
            print("输入错误")
            continue
        new_data = Player()
        new_data.name = input("姓名:")
        new_data.score = input("分数:")
        if direction == "1":  # 右新增
            ptr = ergodic(head)  # 从head开始向右遍历获取最后一个节点
            ptr.rlink = new_data
            new_data.llink = ptr
            new_data.rlink = head
            head.llink = new_data
        else:  # 左新增
            ptr = ergodic(head, left=True)  # 从head开始向左遍历获取最后一个节点
            ptr.llink = new_data
            new_data.rlink = ptr
            new_data.llink = head
            head.rlink = new_data
 
    elif select == "2":  # 遍历查看所有节点,分为右遍历和左遍历
        direction = input("(1).右遍历   (2).左遍历\n输入:")
        if direction == "1":  # 右遍历
            ergodic(head, is_print=True)
        elif direction == "2":  # 左遍历
            ergodic(head, is_print=True, left=True)
        else:
            print("输入错误")
 
    elif select == '3':  # 插入节点,分为右插入和左插入
        direction = input("(1).右插入   (2).左插入\n输入:")
        if direction not in ("1", "2"):
            print("输入错误")
            continue
        try:
            num = int(input("请输入需要插入的节点位置序号:"))  # 输入序号必须是大于0的正整数,如果输入大于最后一个节点的序号则插入到最后一个节点之后
            if num < 1:
                print("输入必须为大于0的正整数")
                continue
        except ValueError:
            print("输入有误")
            continue
        insert_data = Player()
        insert_data.name = input("姓名:")
        insert_data.score = input("分数:")
        if direction == "1":  # 右插入
            ptr = ergodic(head, num - 1)  # 获取需要插入位置的前一个节点,新插入的节点就在这个节点的后面
            insert_data.llink = ptr
            insert_data.rlink = ptr.rlink
            ptr.rlink = insert_data
            insert_data.rlink.llink = insert_data
        else:  # 左插入
            ptr = ergodic(head, num - 1, left=True)
            insert_data.rlink = ptr
            insert_data.llink = ptr.llink
            ptr.llink = insert_data
            insert_data.llink.rlink = insert_data
 
    elif select == '4':  # 删除节点,分为右删除和左删除
        direction = input("(1).右删除   (2).左删除\n输入:")
        if direction not in ("1", "2"):
            print("输入错误")
            continue
        try:
            num = int(input("请输入需要删除的节点位置序号:"))  # 输入序号必须是大于0的正整数,如果输入大于最后一个节点的序号则删除最后一个节点
            if num < 1:
                print("输入必须为大于0的正整数")
                continue
        except ValueError:
            print("输入有误")
            continue
        if direction == "1":  # 右删除
            ptr = ergodic(head, num)  # 获取需要删除的节点
        else:  # 左删除
            ptr = ergodic(head, num, left=True)
        ptr.llink.rlink = ptr.rlink
        ptr.rlink.llink = ptr.llink
 
    elif select == '5':
        print("成功离开")
        break
    else:
        print("输入错误,请重试")

部分运行效果如下:

以上就是本文的全部内容,希望对大家的学习有所帮助,也希望大家多多支持我们。

(0)

相关推荐

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

  • Python数据结构之双向链表详解

    目录 0. 学习目标 1. 双向链表简介 1.1 双向链表介绍 1.2 双向链表结点类 1.3 双向链表优缺点 2. 双向链表实现 2.1 双向链表的初始化 2.2 获取双向链表长度 2.3 读取指定位置元素 2.4 查找指定元素 2.5 在指定位置插入新元素 2.6 删除指定位置元素 2.7 其它一些有用的操作 3. 双向链表应用 3.1 双向链表应用示例 3.2 利用双向链表基本操作实现复杂操作 0. 学习目标 单链表只有一个指向直接后继的指针来表示结点间的逻辑关系,因此可以方便的从任一结点

  • 使用python实现链表操作

    一.概念梳理 链表是计算机科学里面应用应用最广泛的数据结构之一.它是最简单的数据结构之一,同时也是比较高阶的数据结构(例如棧.环形缓冲和队列) 简单的说,一个列表就是单数据通过索引集合在一起.在C里面这叫做指针.比方说,一个数据元素可以由地址元素,地理元素.路由信息活着交易细节等等组成.但是链表里面的元素类型都是一样的,是一种特殊的列表. 一个单独的列表元素叫做一个节点.这些节点不像数组一样都按顺序存储在内存当中,相反,你可以通过一个节点指向另外一个节点的指针在内存不同的地方找到这些元素.列表最

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

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

  • Python实现环形链表

    本文实例为大家分享了Python实现环形链表的具体代码,供大家参考,具体内容如下 我们将单向链表的最后一个节点的指针指向链表的头部(第一个节点),那么就形成了一个环形链表.环形节点可以从任意节点开始遍历其他的节点. 这里主要实现了环形链表节点的遍历.添加.插入.删除,反转. 代码如下: class Player:     """节点类"""     def __init__(self):         """初始化

  • Python实现单向链表

    单向链表每个节点都是由两部分组成:数据字段和指针,指针指向下一个元素在内存中的位置. 单向链表的第一个节点节点是链表头指针,而最后一个节点的指针设为None,不指向任何元素.(链表头指针相当重要!!!) 使用Python实现单向链表,我们可以使用一个节点类来封装节点,每创建一个节点就生成一个节点类的实例. 这里主要实现了单向链表节点的遍历.添加.插入.删除,反转. 代码如下: class Player:     """节点类"""     def

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

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

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

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

  • 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

随机推荐