数据结构——链表(短小精悍版)

使用链表结构可以克服数组链表需要预先知道数据大小的缺点

链表结构可以充分利用计算机内存空间,实现灵活的内存动态管理。

但是链表失去了数组随机读取的优点同时链表由于增加了结点的指针域,空间开销比较大。

单向链表:

一个单链表的节点分为两部分:数据域(data)和指针域(next)

数据域用来保存信息,指针域用来指向下一个节点的地址

单向链表查询较慢: 查找时需要从第一个节点开始一直访问到需要的位置

插入快

删除快:删除只需要将删除结点的上一个指针指向删除节点的下一个节点。

单向链表插入的三种方法:
1.头插法:
  • 将新节点的 next 指针指向当前的头节点。
  • 更新头节点指针为新节点。
public void insertAtHead(int data) {Node newNode = new Node(data);newNode.next = head;head = newNode;
}
2.尾插法
  • 如果链表为空(只有一个 head 指针并且值为null),直接将头节点指针指向新节点。
  • 链表不为空,遍历到链表的最后一个节点,将其 next 指针指向新节点。
public void insertAtTail(int data) {Node newNode = new Node(data);if (head == null) {//只有一个 head 指针并且值为nullhead = newNode;return;}Node current = head;while (current.next != null) {current = current.next;}current.next = newNode;
}
3.插入到链表的指定位置
  • 遍历到插入位置的前一个节点(位置从0开始计数)。
  • 将新节点的 next 指针指向当前节点的 next
  • 更新当前节点的 next 指针为新节点。
public void insertAtPosition(int data, int position) {if (position < 0) {throw new IndexOutOfBoundsException("Position cannot be negative");}if (position == 0) {insertAtHead(data);return;}Node newNode = new Node(data);Node current = head;for (int i = 0; i < position - 1 && current != null; i++) {current = current.next;}if (current == null) {throw new IndexOutOfBoundsException("Position out of bounds");}newNode.next = current.next;current.next = newNode;
}

双向链表:

双向链表的指针域有两个指针,分别指向直接后继和直接前驱。

双向链表可以从前向后遍历也可以从后向前遍历

typedef int LTDataType;
typedef struct ListNode
{struct ListNode* next;     //后继节点struct ListNode* prev;      //前驱节点LTDataType data;}LTNode;
当双向链表为空时:

双向链表头插法:

对于每个元素,创建一个新结点,并将其插入到头结点之后,使新结点成为新的头结点。

最后创建成功的双链表的顺序和输入的顺序相反,即为逆序的。

头插法的时间复杂度为O(1)。

//利用头插法创建双链表
DLinkList Init_DLinkList_head() {DLinkList head = (DLinkList) malloc(sizeof(DLinkList));head->prior = NULL;head->next = NULL;head->data = NULL;bool List_Insert (DLinkList pHead,int e){DNode* newNode = (DNode *)malloc(sizeof(DNode));newNode->data = e;newNode->next =  pHead->next;  //head的后继赋给新节点的后继pNode->prior = pHead;          //头节点指向新节点if(pHead->next !=NULL){pHead->next->prior = newNode;}pHead->next= newNode;return true;}
}
双向链表尾插法:

对于每个元素,创建一个新结点,并将其插入到头结点之后的尾部,更新尾结点的next指针和新结点的prior指针。遍历完成后,返回头结点的next指针,即为新链表的头结点。

尾插法的时间复杂度为O(n),因为需要遍历整个双链表找到尾节点。

//利用尾插法创建双链表
DLinkList Init_DLinkList_tail() {DLinkList head = (DLinkList) malloc(sizeof(DLinkList));head->prior = NULL;head->next = NULL;head->data = NULL;void addLast(DLinkList pHead,int e){DNode* newNode = (DNode *)malloc(sizeof(DNode));newNode->data = e;}DNode* last = pHead;//遍历链表找到最后一个节点while(last->next !=NULL){last = last->next;}//让最后一个结点的后继指向新节点,新节点的后继指针置空last->next = newNode;newNode->prior = last;newNode->next = NULL;
}

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

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

相关文章

【kafka】生产者

1. 主要参数&#xff1a; **bootstrap.servers&#xff1a;**该参数用来指定生产者客户端连接Kafka集群所需的broker地址清单&#xff0c;具体的内容格式为host1&#xff1a;port1&#xff0c;host2&#xff1a;port2&#xff0c;可以设置一个或多个地址&#xff0c;中间以逗号…

《Google软件测试之道》笔记

介绍 GTAC&#xff1a;Google Test Automation Conference&#xff0c;Google测试自动化大会。 本书出版之前还有一本《微软测试之道》&#xff0c;值得阅读。 质量不是被测试出来的&#xff0c;但未经测试也不可能开发出有质量的软件。质量是开发过程的问题&#xff0c;而不…

ROS第五梯:ROS+VSCode+C++单步调试

解决问题&#xff1a;在ROS项目中进行断点调试。 第一步&#xff1a;创建一个ROS项目或者打开一个现有的ROS项目。 第二步&#xff1a;修改c_cpp_properties.json 增加一段命令: "compileCommands": "${workspaceFolder}/build/compile_commands.json"第三…

线结构光测量系统标定--导轨

光平面标定原理可查看之前的博文《光平面标定》&#xff0c;光条中心提取可参考线结构光专栏光条中心提取系列的文章&#xff0c;相机标定参考相机标定专栏中的博文。&#xff08;欢迎进Q群交流&#xff1a;874653199&#xff09; 线结构光测量系统(指一个线结构光传感器与一个…

rocky9虚拟机配置双网卡的详细过程

编辑虚拟机配置->添加->选择网络适配器->确认->打开虚拟机 1.ip add查看第二个网卡的名称&#xff0c;我这里是ens36 2.cd到网卡的配置文件目录 cd /etc/NetworkManager/system-connections/ ls3.复制一份网卡的配置文件并改名为ens36.nmconnection(根据自己的第…

计算机网络(运输层)

物理层、数据链路层以及网络层共同解决了将主机通过异构网络互联起来所面临的问题&#xff0c;实现了主机与主机之间的通信。 实际上在计算机网络中进行通信的真正实体事位于通信两端主机中的进程。 运输层的任务就会是提供运行在不同主机上的应用进程提供直接的通信服务&…

pybind11 学习笔记

pybind11 学习笔记 0. 一个例子1. 官方文档1.1 Installing the Library1.1.1 Include as A Submodule1.1.2 Include with PyPI1.1.3 Include with Conda-forge 1.2 First Steps1.2.1 Separate Files1.2.2 PYBIND11_MODULE() 宏1.2.3 example.cpython-38-x86_64-linux-gnu.so 的…

常见 HTTP 状态码详解与Nginx 文件上传大小限制

在我们日常使用 Nginx 搭建网站或应用服务时&#xff0c;可能会遇到很多与文件上传和请求响应相关的问题。今天我们就来聊聊 如何限制文件上传的大小&#xff0c;并介绍一些常见的 HTTP 状态码 及其在 Nginx 中的处理方式。 一、文件上传大小限制 有时&#xff0c;我们需要限…

从入门到精通,玩转Python的print函数(探索Python print函数的隐藏功能)

文章目录 📖 介绍 📖🏡 演示环境 🏡📒 文章内容 📒📝 基础用法参数详解示例📝 高级用法自定义分隔符和结束符输出到文件追加模式📝 覆盖打印与进度条简单覆盖打印动态进度条示例代码⚓️ 相关链接 ⚓️📖 介绍 📖 刚开始学习编程时,我们接触到的第一个方…

【初阶数据结构】一文讲清楚 “堆” 和 “堆排序” -- 树和二叉树(二)(内含TOP-K问题)

文章目录 前言1. 堆1.1 堆的概念1.2 堆的分类 2. 堆的实现2.1 堆的结构体设置2.2 堆的初始化2.3 堆的销毁2.4 添加数据到堆2.4.1 "向上调整"算法 2.5 从堆中删除数据2.5.1 “向下调整”算法 2.6 堆的其它各种方法接口函数 3. 堆排序3.1 堆排序的代码实现 4. TOP-K问题…

微软Office全家桶再爆办公革命,o1模型加持重塑十亿人工作流!1句话生成PPT+自定义智能体

颠覆全球十亿打工人的Office办公全家桶&#xff0c;昨夜迎来重磅升级&#xff01; 在微软Copilot第二弹发布会上&#xff0c;CEO纳德拉官宣&#xff0c;「用AI构思&#xff0c;共同协作的全新工作流——WebWorkPages正式开启」。 全程半小时&#xff0c;每一幕都在透露着&…

GPT代码记录

#include <iostream>// 基类模板 template<typename T> class Base { public:void func() {std::cout << "Base function" << std::endl;} };// 特化的子类 template<typename T> class Derived : public Base<T> { public:void…

基于JDK1.8和Maven的GeoTools 28.X源码自主构建实践

目录 前言 一、GeoTools与Jdk的版本关系 1、GeoTools与Jdk版本 2、编译环境简介 二、使用Maven编译GeoTools28.X 1、GeoTools28.x 2、Maven的完整编译 3、构建时的问题 三、总结 前言 想要学习和掌握一个开源软件或者项目&#xff0c;源码是我们主要学习的内容。学习开…

JDBC笔记

文章目录 准备MySQL数据的建立和建表 idea 建工程和模块设置属性配置文件编写JDBC代码URL的设置JDBC 代码配置文件 准备MySQL 数据的建立和建表 idea 建工程和模块 设置属性配置文件 编写JDBC代码 URL的设置 JDBC 代码 package com.yanyu;import java.sql.*; import java.util…

vue2.0+ts注册全局函数和几个递归查找

vue2.0ts注册全局函数和几个递归查找 一、main.ts 一、main.ts // 定义你的全局函数,判断是否有按钮权限 interface Item {label: string;checked: number;[k: string]: any; } // 获取按钮时候权限 function globalLable(arr: Item[], label: string): boolean {for (const i…

硬件基础知识

驱动开发分为&#xff1a;裸机驱动、linux驱动 嵌入式&#xff1a;以计算机技术为基础&#xff0c;软硬结合的、可移植、可剪裁的专用计算机 单片机最小单元&#xff1a;vcc gnd reset 晶振 cpu --- soc :system on chip 片上外设 所有的程序都是在soc&#xff08;cpu&…

1.熟悉接口测试(Postman工具)

一、接口及其类型 API&#xff0c;应用编程接口&#xff0c;简称接口 通过接口&#xff0c;可以让程序和程序之间&#xff0c;能够互相交互。 接口分为两大类&#xff1a; 1&#xff09;基于TCP全双工&#xff08;适用于postman&#xff09; 2&#xff09;基于HTTP半双工 二、…

项目管理 | 一文读懂什么是敏捷开发管理

在快速变化的商业环境中&#xff0c;项目管理方式也在不断演进&#xff0c;其中敏捷开发管理因其高效、灵活和适应性强的特点&#xff0c;逐渐成为众多企业和团队的首选。本文将详细解析敏捷开发管理的定义、具体内容及其核心角色&#xff0c;帮助读者全面理解这一先进的项目管…

普罗米修斯监控

目录 概念 部署方法 1. 二进制&#xff08;源码包&#xff09; 2. 部署在k8s集群当中&#xff0c;用pod形式部署 概念 prometheus是开源的系统监控和告警。在k8s分布式的容器化管理系统当中&#xff0c;一般都是搭配prometheus来进行监控。它是服务监控系统&#xff0c;也…