线性表、单循环链表学习

背景：
在这里插入图片描述

单循环链表是一种链表结构，其中最后一个节点指向第一个节点，从而形成一个环。

实现单循环链表通常涉及节点定义、插入节点、删除节点以及遍历链表等操作。以下是如何在Python中实现单循环链表的示例。

单循环链表的实现

1. 节点类

首先，定义链表的节点类，每个节点包含数据和指向下一个节点的指针。

class Node:def __init__(self, data):self.data = dataself.next = None
2. 单循环链表类

接下来，定义单循环链表类，包含插入、删除和遍历等方法。

class CircularLinkedList:def __init__(self):self.head = Nonedef insert(self, data):new_node = Node(data)if not self.head:self.head = new_nodeself.head.next = self.headelse:current = self.headwhile current.next != self.head:current = current.nextcurrent.next = new_nodenew_node.next = self.headdef delete(self, key):if self.head is None:returncurrent = self.headprev = Nonewhile True:if current.data == key:if prev:prev.next = current.nextelse:# Deleting the head nodeif current.next == self.head:self.head = Noneelse:tail = self.headwhile tail.next != self.head:tail = tail.nexttail.next = current.nextself.head = current.nextreturnprev = currentcurrent = current.nextif current == self.head:breakdef display(self):if self.head is None:print("List is empty")returncurrent = self.headwhile True:print(current.data, end=" -> ")current = current.nextif current == self.head:breakprint()# 示例使用
cll = CircularLinkedList()
cll.insert(1)
cll.insert(2)
cll.insert(3)
cll.display()  # 输出: 1 -> 2 -> 3 -> cll.delete(2)
cll.display()  # 输出: 1 -> 3 ->

代码解释

  1. 节点类 (Node):

    • __init__: 初始化节点的数据和指向下一个节点的指针。

  2. 单循环链表类 (CircularLinkedList):

    • __init__: 初始化链表的头指针。
    • insert: 在链表中插入新节点。
      • 如果链表为空，插入第一个节点并使其指向自己。
      • 如果链表不为空，找到最后一个节点并将其next指针指向新节点，然后将新节点的next指针指向头节点。
    • delete: 删除包含指定数据的节点。
      • 如果链表为空，直接返回。
      • 找到要删除的节点并更新前一个节点的next指针。
      • 如果删除的是头节点，处理特殊情况，找到尾节点并更新其next指针指向新的头节点。
    • display: 遍历并打印链表中的所有节点。

总结

单循环链表是一种方便的数据结构，适用于需要循环访问数据的场景。上面的代码展示了如何在Python中实现单循环链表的基本操作，包括插入、删除和遍历。

线性表和单链表都是常见的数据结构，用于存储和管理数据元素。它们有各自的特点和应用场景。下面详细介绍它们的概念、特点、优缺点，以及适用的场景。

线性表

概念

线性表（Linear List）是具有相同数据类型的 n 个元素的有限序列。在逻辑结构上，线性表中的数据元素具有线性关系，即每个元素有且只有一个前驱和一个后继（除第一个和最后一个元素外）。

特点
  • 有序性：线性表中的元素按线性顺序排列。
  • 唯一的前驱和后继：每个元素除了第一个元素没有前驱和最后一个元素没有后继外，其余元素都有唯一的前驱和后继。
  • 长度可变：线性表的长度是可变的，可以动态增删元素。
实现方式
  1. 顺序存储结构（数组）
  2. 链式存储结构（链表）

单链表

概念

单链表（Singly Linked List）是一种链式存储结构，其中每个节点包含数据域和指向下一个节点的指针。链表中的最后一个节点的指针指向空（None），表示链表的结束。

特点
  • 动态存储：不需要预先分配存储空间，可以动态地进行内存分配。
  • 插入和删除操作高效：在已知位置进行插入和删除操作时，无需移动其他元素，只需改变指针指向。
  • 顺序访问：只能从头节点开始顺序访问各节点，无法直接随机访问。
结构
  • 节点：包含数据域（存储数据）和指针域（指向下一个节点）。
  • 头指针：指向链表的第一个节点。

比较与对比

共同点
  • 线性结构：线性表和单链表都属于线性结构，元素之间具有线性关系。
  • 基本操作：都支持插入、删除、查找、更新、遍历等基本操作。
不同点
特点线性表（顺序存储）单链表
存储方式数组链表
内存分配需预先分配连续空间动态分配
随机访问支持不支持
插入和删除效率低，需移动元素高，只需修改指针
空间利用率可能存在空间浪费高效
实现难度简单较复杂
适用场景

  • 线性表（数组）：

    • 适用于元素数量固定且变化不大的场景。
    • 适用于需要频繁随机访问元素的场景。
    • 适用于存储大小一致的数据（如基本数据类型）。

  • 单链表：

    • 适用于元素数量变化频繁的场景。
    • 适用于插入和删除操作较多的场景。
    • 适用于数据量较大且不确定的场景。

示例代码

顺序存储（数组实现）
class LinearList:def __init__(self):self.data = []def insert(self, index, element):if index < 0 or index > len(self.data):raise IndexError("Index out of bounds")self.data.insert(index, element)def delete(self, index):if index < 0 or index >= len(self.data):raise IndexError("Index out of bounds")return self.data.pop(index)def get(self, index):if index < 0 or index >= len(self.data):raise IndexError("Index out of bounds")return self.data[index]def update(self, index, element):if index < 0 or index >= len(self.data):raise IndexError("Index out of bounds")self.data[index] = elementdef length(self):return len(self.data)def display(self):print(self.data)# 示例使用
linear_list = LinearList()
linear_list.insert(0, 1)
linear_list.insert(1, 2)
linear_list.insert(2, 3)
linear_list.display()  # 输出: [1, 2, 3]linear_list.update(1, 5)
linear_list.display()  # 输出: [1, 5, 3]linear_list.delete(2)
linear_list.display()  # 输出: [1, 5]print(linear_list.get(1))  # 输出: 5
print(linear_list.length())  # 输出: 2
单链表实现
class Node:def __init__(self, data):self.data = dataself.next = Noneclass LinkedList:def __init__(self):self.head = Nonedef insert(self, index, element):new_node = Node(element)if index == 0:new_node.next = self.headself.head = new_nodereturncurrent = self.headfor _ in range(index - 1):if current is None:raise IndexError("Index out of bounds")current = current.nextnew_node.next = current.nextcurrent.next = new_nodedef delete(self, index):if self.head is None:raise IndexError("Index out of bounds")if index == 0:self.head = self.head.nextreturncurrent = self.headfor _ in range(index - 1):if current.next is None:raise IndexError("Index out of bounds")current = current.nextif current.next is None:raise IndexError("Index out of bounds")current.next = current.next.nextdef get(self, index):current = self.headfor _ in range(index):if current is None:raise IndexError("Index out of bounds")current = current.nextif current is None:raise IndexError("Index out of bounds")return current.datadef update(self, index, element):current = self.headfor _ in range(index):if current is None:raise IndexError("Index out of bounds")current = current.nextif current is None:raise IndexError("Index out of bounds")current.data = elementdef length(self):count = 0current = self.headwhile current:count += 1current = current.nextreturn countdef display(self):current = self.headwhile current:print(current.data, end=" -> ")current = current.nextprint("None")# 示例使用
linked_list = LinkedList()
linked_list.insert(0, 1)
linked_list.insert(1, 2)
linked_list.insert(2, 3)
linked_list.display()  # 输出: 1 -> 2 -> 3 -> Nonelinked_list.update(1, 5)
linked_list.display()  # 输出: 1 -> 5 -> 3 -> Nonelinked_list.delete(2)
linked_list.display()  # 输出: 1 -> 5 -> Noneprint(linked_list.get(1))  # 输出: 5
print(linked_list.length())  # 输出: 2

总结

线性表和单链表各有优缺点和适用场景。选择使用哪种数据结构，取决于具体的应用需求和操作频率。在需要频繁随机访问数据的场景下，线性表（数组）更为合适；在需要频繁插入和删除操作的场景下，单链表则更为高效。

本文来自互联网用户投稿，该文观点仅代表作者本人，不代表本站立场。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如若转载，请注明出处：http://www.rhkb.cn/news/341369.html

如若内容造成侵权/违法违规/事实不符，请联系长河编程网进行投诉反馈email:809451989@qq.com，一经查实，立即删除！

相关文章

掌握ChatGPT的正确打开方式

掌握ChatGPT的正确打开方式

引言 随着人工智能技术的飞速发展&#xff0c;自然语言处理&#xff08;NLP&#xff09;领域取得了显著的突破。其中&#xff0c;聊天生成预训练变换器&#xff08;ChatGPT&#xff09;作为一种新型的对话式AI模型&#xff0c;引起了广泛关注。本文将详细介绍ChatGPT的正确使用…
阅读更多...
使用html2canvas和jspdf导出pdf包含跨页以及页脚

使用html2canvas和jspdf导出pdf包含跨页以及页脚

首先要下载两个文件&#xff0c;一个为html2canvas.min.js&#xff0c;另一个是jspdf.umd.min.js这两个文件分别下载的地址我也附录上&#xff0c;都在官网git&#xff1a; html2canvas.min.js: https://html2canvas.hertzen.com/dist/html2canvas.min.js jspdf.umd.min.js: …
阅读更多...
vue-pdf 部分中文显示错误，第二次打开是空白，解决方法

vue-pdf 部分中文显示错误，第二次打开是空白，解决方法

首先鸣谢 1. https://blog.csdn.net/m0_71537867/article/details/131614868?spm1001.2014.3001.5506 2. https://blog.csdn.net/weixin_43763952/article/details/133769647 3. https://github.com/FranckFreiburger/vue-pdf/issues/229 4. https://blog.csdn.net/weixin_449…
阅读更多...
康谋技术 | 自动驾驶：揭秘高精度时间同步技术（一）

康谋技术 | 自动驾驶：揭秘高精度时间同步技术（一）

众所周知&#xff0c;在自动驾驶中&#xff0c;主要涵盖感知、规划、控制三个关键的技术层面。在感知层面&#xff0c;单一传感器采集外界信息&#xff0c;各有优劣&#xff0c;比如摄像头采集信息分辨率高&#xff0c;但是受外界条件影响较大&#xff0c;一般缺少深度信息&…
阅读更多...
推荐一个免费的相亲工具

推荐一个免费的相亲工具

推荐一个免费的相亲工具&#xff0c;步骤如下&#xff1a; 1&#xff09;微信里面搜索公众号“光源桥”&#xff0c;并关注 2&#xff09;输入搜索条件进行搜索对象 例如下面搜索&#xff1a;
阅读更多...
Pinterest免费引流实操演示

Pinterest免费引流实操演示

这篇文章中你将了解到 1.Pinterest网站介绍&#xff0c;用户群体&#xff0c;适合做什么品类。 2.现在的商家都在上面做什么&#xff1f;案例展示。 3.我们在这个站免费引流要怎么做以及注意事项。 1.Pinterest网站介绍&#xff0c;用户群体&#xff0c;适合做什么品类。 P…
阅读更多...
【Excel】Excel中将日期格式转换为文本格式，并按日期显示。

【Excel】Excel中将日期格式转换为文本格式，并按日期显示。

【问题需求】 在使用excel进行数据导入的过程中&#xff0c; 有的软件要求日期列必须是文本格式。 但是直接将日期列的格式改为文本后&#xff0c;显示一串数字&#xff0c;而不按日期显示。 进而无法导入使用。 【解决方法】 使用【TXET】函数公式进行处理&#xff0c; 在单…
阅读更多...
百度ERNIE系列预训练语言模型浅析(4)-总结篇

百度ERNIE系列预训练语言模型浅析(4)-总结篇

总结&#xff1a;ERNIE 3.0与ERNIE 2.0比较 &#xff08;1&#xff09;相同点&#xff1a; 采用连续学习 采用了多个语义层级的预训练任务 &#xff08;2&#xff09;不同点&#xff1a; ERNIE 3.0 Transformer-XL Encoder(自回归自编码), ERNIE 2.0 Transformer Encode…
阅读更多...
泛微开发修炼之旅--05Ecode入门讲解、接口调用源码示例及踩坑总结

泛微开发修炼之旅--05Ecode入门讲解、接口调用源码示例及踩坑总结

文章链接&#xff1a;泛微开发修炼之旅--05Ecode入门讲解、接口调用源码示例及踩坑总结
阅读更多...
操作系统复习-linux的进程管理

操作系统复习-linux的进程管理

linux的进程管理 linux进程的相关概念 进程的类型 前台进程 前台进程就是具有终端&#xff0c;可以和用户交互的进程&#xff0c;会占用终端shell&#xff0c;不可以输入其他的命令。 后台进程 前台进程就是具有终端&#xff0c;可以和用户交互的进程。 不会占用终端shell&a…
阅读更多...
数据分析必备：一步步教你如何用Pandas做数据分析（17）

数据分析必备：一步步教你如何用Pandas做数据分析（17）

1、Pandas 连接 Pandas 连接的操作实例 Pandas具有与SQL等关系数据库非常相似的功能齐全的高性能内存中连接操作。 Pandas提供单个功能merge作为DataFrame对象之间所有标准数据库联接操作的入口点 pd.merge(left, right, howinner, onNone, left_onNone, right_onNone,left_i…
阅读更多...
实战|基于YOLOv10与MobileSAM实现目标检测与分割【附完整源码】

实战|基于YOLOv10与MobileSAM实现目标检测与分割【附完整源码】

《博主简介》 小伙伴们好&#xff0c;我是阿旭。专注于人工智能、AIGC、python、计算机视觉相关分享研究。 ✌更多学习资源&#xff0c;可关注公-仲-hao:【阿旭算法与机器学习】&#xff0c;共同学习交流~ &#x1f44d;感谢小伙伴们点赞、关注&#xff01; 《------往期经典推…
阅读更多...
[240605] FreeBSD 发布 v14.1 | ChatGPT 出现故障，部分用户无法使用

[240605] FreeBSD 发布 v14.1 | ChatGPT 出现故障，部分用户无法使用

目录 FreeBSD 发布 v14.1ChatGPT 出现故障&#xff0c;部分用户无法使用 FreeBSD 发布 v14.1 一、概述 FreeBSD 项目发布了 FreeBSD 14.1-RELEASE&#xff0c;这是 stable/14 分支的第二个稳定版本。 二、主要更新 C 库在 amd64 架构上实现了 SIMD 字符串和内存操作&#x…
阅读更多...
Navicat使用ssh隧道连接mysql数据库

Navicat使用ssh隧道连接mysql数据库

转载请标明出处&#xff1a;http://blog.csdn.net/donkor_/article/details/139352748 文章目录 前言新建连接MySql,填写ssh隧道信息方式1&#xff1a;使用密码方式连接方式二&#xff1a;使用密钥方式连接 填写常规信息总结 前言 使用ssh隧道连接数据库&#xff0c;方便本机…
阅读更多...
月入30000的软件测试人员，简历是什么样子的？

月入30000的软件测试人员，简历是什么样子的？

我们都知道&#xff0c;简历是一个人进入职场的敲门砖。从某种层面来说&#xff0c;简历也像一个人的具象身份证&#xff0c;或者专业资格证。所以&#xff0c;一份简历的好坏&#xff0c;不仅关乎个人的“脸面”&#xff0c;更关乎你是不是一个有“含金量”的技术人员。 所以…
阅读更多...
＜vs2022＞＜问题记录＞visual studio 2022使用console打印输出时，输出窗口不显示内容

＜vs2022＞＜问题记录＞visual studio 2022使用console打印输出时，输出窗口不显示内容

前言 本文为问题记录。 问题概述 在使用visual studio 2022编写代码时&#xff0c;如C#&#xff0c;在代码中使用console.writeline来打印某些内容&#xff0c;以便于观察&#xff0c;但发现输出窗口不显示&#xff0c;而代码是完全没有问题的。 解决办法 根据网上提供的办法…
阅读更多...
FastDFS分布式文件系统

FastDFS分布式文件系统

一、概述 FastDFS是一款由国人余庆开发的轻量级开源分布式文件系统&#xff0c;它对文件进行管理&#xff0c;功能包括&#xff1a;文件存储、文件同步、文件访问&#xff08;文件上传、文件下载&#xff09;等&#xff0c;主要解决大容量文件存储和高并发访问问题&#xff0c…
阅读更多...
ru域名如何申请ssl证书

ru域名如何申请ssl证书

SSL证书是一种数字证书&#xff0c;通过它可以在客户端和服务器之间建立加密通道&#xff0c;保证数据在传输过程中的安全性。对于.ru域名来说&#xff0c;申请SSL证书可以有效提升网站的安全性&#xff0c;增强用户对网站的信任度&#xff0c;提高网站的排名和权重。今天就随S…
阅读更多...
C#使用GDI对一个矩形进行任意角度旋转

C#使用GDI对一个矩形进行任意角度旋转

C#对一个矩形进行旋转GDI绘图&#xff0c;可以指定任意角度进行旋转 我们可以认为一张图片Image&#xff0c;本质就是一个矩形Rectangle,旋转矩形也就是旋转图片 在画图密封类 System.Drawing.Graphics中&#xff0c; 矩形旋转的两个关键方法 //设置旋转的中心点 public v…
阅读更多...
【遂愿赠书 - 2期】：618火热来袭，网络安全书单推荐

【遂愿赠书 - 2期】：618火热来袭，网络安全书单推荐

文章目录 一、网络安全书单背景二、网络安全与编程实践书单2.1 &#x1f3f0;《内网渗透实战攻略》2.2 &#x1f6e1;️《Kali Linux高级渗透测试&#xff08;原书第4版&#xff09;》2.3 &#x1f396;️《CTF那些事儿》2.4 &#x1f680;《权限提升技术&#xff1a;攻防实战与…
阅读更多...
最新文章
推荐文章

Copyright @ 2022~2023