python双向循环链表实例详解

作者:python-行者 时间:2023-08-04 04:53:06 

使用python实现双向循环链表,供大家参考,具体内容如下

双向循环链表: 将所有的数据存放到节点中,每一个节点相连接,首尾链接,
每一个节点中有一个数据存储区,和两个链接区,一个链接前一个节点,一个链接下一个节点

双向链表操作

1、链表是否为空
2、链表的长度
3、遍历链表
4、链表头部添加元素
5、链表尾部添加元素
6、链表指定位置添加元素
7、链表删除节点
8、查找节点是否存在

代码实现

# Functions  函数声明
class Node():
    """实例化节点类"""
    def __init__(self, item):
        self.item = item
        self.prev = None
        self.next = None

class Linklist():
    """
    存放节点类
    """
    def __init__(self):
        self.head = None

    # 1. 链表是否为空
    def is_empty(self):
        return self.head == None

    # 2. 链表的长度
    def length(self):
        """
        返回链表中所有数据的个数
        实例化游标,遍历链表,使用计数器自增一
        空链表

        """
        # 实例化游标
        cur = self.head
        # 判断是否为空
        if self.is_empty():
            return 0
        else:
            # 不为空
            # 定义计数
            count = 1
            while cur.next != self.head:
                count+=1
                cur = cur.next
            return count
            pass

    # 3. 遍历链表
    def travel(self):
        """
        遍历链表
        实例化游标,遍历链表,每次输出节点的数据
        空链表
        只有头节点
        """
        # 实例化游标
        cur = self.head
        # 判断是否为空
        if self.is_empty():
            return None
        else:
            # 不为空的情况
            while cur.next != self.head:
                print(cur.item, end=' ')
                cur = cur.next
            print(cur.item)
            pass

    # 4. 链表头部添加元素
    def add(self, item):
        """
        头节点添加
        实例化节点,
        """
        # 实例化节点
        node = Node(item)
        # 实例化游标
        cur = self.head
        # 判断是否为空
        if self.is_empty():
            node.next = node
            node.prev = node
            self.head = node
        else:
            # 链表不为空的情况
            # 只有一个节点的情况
            # node.next = self.head
            node.next = cur
            node.prev = cur
            if cur.next == self.head:
                # print(cur.item)
                cur.prev = node
                cur.next = node
                self.head = node
            elif cur.next != self.head:
                pro = self.head
                while cur.next != self.head:
                    cur = cur.next
                pro.prev = node
                cur.next = node
                self.head = node
                pass

    # 5. 链表尾部添加元素
    def append(self, item):
        """
        链表尾部添加数据
        实例化节点,实例化游标,指向尾部节点,修改指向
        链表为空
        """
        # 实例化节点
        node = Node(item)
        # 实例化游标
        cur = self.head
        if self.is_empty():
            self.add(item)
        else:
            # 不为空的情况
            # 指针指向最后一个节点
            self.head.prev = node
            node.next = self.head
            while cur.next != self.head:
                cur = cur.next
            node.prev = cur
            cur.next = node
            pass

    # 6. 链表指定位置添加元素
    def insert(self, index, item):
        """
        指定位置添加数据
        实例化节点, 实例化游标
        移动游标到索引位置,更改指向
        输入索引大小判断
        链表是否为空
        """
        # 实例化节点
        node = Node(item)
        # 实例化游标
        cur = self.head
        if index <= 0:
            self.add(item)
        elif index > (self.length()-1):
            self.append(item)
        else:
            # 中间添加数据
            # 声明计数
            count = 0
            print(index)
            while count < index-1:
                count+=1
                cur = cur.next
            # print(cur.item)
            node.next = cur.next
            node.prev = cur
            cur.next.prev = node
            cur.next = node
            pass

    # 7. 链表删除节点
    def remove(self, item):
        """
        删除数据
        实例化游标,遍历链表,查找有没有改数据
        有,对改数据两侧的节点进行指向修改
        """
        # 实例化游标
        cur = self.head
        # 判断是否为空
        if self.is_empty():
            return None
        else:
            # 不为空的情况下
            # 如果删除的是头节点
            if cur.item == item:
                # 如果只有一个头节点
                if cur.next == self.head:
                   self.head = None
                else:
                    # self.head = cur.next
                    pro = cur.next
                    while cur.next != self.head:
                        cur = cur.next
                    cur.next = pro
                    pro.prev = cur
                    self.head = pro
                    pass
            else:
                while cur.next != self.head:
                    if cur.item == item:
                        # print(cur.item)
                        pro = cur.prev
                        nex = cur.next
                        pro.next = cur.next
                        nex.prev = pro
                        return True
                    else:
                        cur = cur.next
                # 如果是最后一个节点
                if cur.item == item:
                    cur.prev.next = self.head
                    self.head.prev = cur.prev

    # 8. 查找节点是否存在
    def search(self, item):
        """
        查询指定的数据是否存在
        实例化游标
        遍历所有的节点。每个节点中判断数据是否相等,相等,返回True
        """
        # 实例化游标
        cur = self.head
        # 判断是否为空
        if self.is_empty():
            return None
        else:
            # 不为空的情况
            # 遍历所有的节点
            while cur.next != self.head:
                if cur.item == item:
                    return True
                else:
                    cur = cur.next
            if cur.item == item:
                return True
            pass

测试运行

# 程序的入口
if __name__ == "__main__":
    a = Linklist()
    a .add(400)
    a .add(300)
    a .add(200)
    a .add(100)
    a.append(10)
    a.append(11)
    a.add(1)
    a.insert(30, 12) # 1 100 200 300 400 10 11 12
    a.remove(1)    # 100 200 300 400 10 11 12
    a.remove(12)   # 100 200 300 400 10 11
    a.remove(400)  # # 100 200 300  10 11
    a.remove(4000)
    print(a.search(100))  # True
    print(a.search(11))   # True
    print(a.search(111))  # None
    print(a.is_empty())   # False
    a.travel()            # 100 200 300 10 11
    print(a.length())     # 5
    pass

来源:https://blog.csdn.net/Dhaihaihai/article/details/111304544

标签:python,链表
0
投稿

猜你喜欢

  • python OpenCV 图像通道数判断

    2023-10-15 18:21:22
  • Python3读写Excel文件(使用xlrd,xlsxwriter,openpyxl3种方式读写实例与优劣)

    2022-10-10 18:17:38
  • Oracle中字符串截取常用方法总结【推荐】

    2024-01-26 16:55:02
  • mysql 8.0.12 解压版安装教程 个人亲测!

    2024-01-28 10:22:05
  • Python中的MongoDB基本操作:连接、查询实例

    2021-12-21 07:38:06
  • asp当中判断函数一览

    2010-05-27 12:15:00
  • Pytorch 保存模型生成图片方式

    2023-04-20 17:42:17
  • Python之维度dim的定义及其理解使用方式

    2021-06-10 12:33:04
  • python 虚拟环境的创建与使用方法

    2022-11-09 18:21:50
  • python实现弹窗祝福效果

    2021-09-08 04:22:15
  • Keras多线程机制与flask多线程冲突的解决方案

    2023-09-12 02:10:51
  • 如何用CSS实现图像替换链接文本显示并保证链接可点击

    2011-03-03 12:37:00
  • python机器学习基础K近邻算法详解KNN

    2024-01-01 05:44:57
  • pyecharts如何实现显示数据为百分比的柱状图

    2021-06-27 17:11:52
  • 在keras里面实现计算f1-score的代码

    2021-12-13 08:39:43
  • 使用Filter实现信息的二次检索

    2007-10-08 19:19:00
  • Python实现按照指定要求逆序输出一个数字的方法

    2023-12-21 23:37:46
  • “生活”设计

    2009-03-03 12:14:00
  • 关于JS中变量的显式声明和隐式声明

    2008-10-06 13:22:00
  • 配置Git并从GitHub上克隆项目

    2023-03-13 12:38:16
  • asp之家 网络编程 m.aspxhome.com