数据结构基础（三）链表

news/2024/4/28 17:41:06/文章来源:https://blog.csdn.net/weixin_45700531/article/details/136962230

链表（Linked List）是一种常见的线性数据结构，由一系列称为节点（Node）的元素组成，每个节点包含两部分：数据（Data）和指向下一个节点的引用（Pointer 或者 Link）。通过这种节点之间的指针连接起来，形成了链式结构

我们为什么需要链表

链表常 用于存储和组织数据。它的设计目的主要有以下几个方面的考虑：

  1. 动态内存分配：链表能够动态地分配内存空间，这意味着它可以根据需要动态地增加或减少元素，而不需要像数组一样预先指定大小。

  2. 灵活性：链表的插入和删除操作非常高效，时间复杂度为 O(1)，这是因为它不需要像数组那样进行元素的移动。

  3. 适应动态数据：链表适用于需要频繁插入和删除操作的场景，比如实现队列、栈等数据结构。

  4. 内存紧张：当内存紧张时，链表可以节省内存空间，因为它只在需要时分配内存。

  5. 不连续内存：链表的节点不需要在内存中连续存储，这使得链表能够有效地利用零散的内存空间。

  6. 支持不同长度的元素：链表中的每个节点都包含一个指向下一个节点的指针，因此节点之间的大小不必相等，可以存储不同长度的元素。

  7. 简单实现：链表相对于其他数据结构（比如树）来说，实现起来比较简单，不需要复杂的数据结构和算法。

相对于数组而言，链表是一种非常灵活和高效的数据结构，特别适用于动态数据和需要频繁插入、删除操作的场景。在编程中，链表常用于实现各种数据结构，如队列、栈、图等，并且在很多算法中都有着广泛的应用。

手动实现链表

  • Java内置了 java.util.LinkedList 类，它是 Java 标准库中的一部分，用于表示双向链表（Doubly Linked List）。

我们可以参照该类进行设计

需求分析

链表是由一个个数据节点构成，换句话说，我们将每条数据储存在链表中的每一个数据节点中。同时每个节点要负责帮助我们找到下一个节点在哪里。所以我们需要一个内置Node类，它的内部有一个数据，一个节点指针。

     private class Node {E data;Node next;//下一个节点的地址Node(E data) {this.data = data;this.next = null;}}

回到链表本身，我们需要记录整个链表的大小，size， 不仅如此，我也要一个头指针帮我定位整个链表的起始点。

public class MyLinkedList<E> {private class Node {E data;Node next;Node(E data) {this.data = data;this.next = null;}}private Node head;private int size;public MyLinkedList() {head = null;size = 0;}
}

功能实现

  • 1.添加元素

这个功能很容易理解，不过呢，我们肯定不能满足仅仅append元素。应该允许我们指定位置插入

        // 在链表末尾添加元素public void add(E data) {add(size, data);}/*** 在指定位置插入一个元素。* @param index 插入位置的索引，从0开始。* @param data 要插入的元素。* @throws IndexOutOfBoundsException 如果索引小于0或大于当前列表大小，则抛出异常。*/public void add(int index, E data) {// 检查索引是否超出范围if (index < 0 || index > size) {throw new IndexOutOfBoundsException("Index out of bounds");}Node newNode = new Node(data); // 创建新节点// 当索引为0时，将新节点插入到链表头部if (index == 0) {newNode.next = head;head = newNode;} else {// 遍历链表，找到插入位置的前一个节点Node current = head;for (int i = 0; i < index - 1; i++) {current = current.next;}newNode.next = current.next;current.next = newNode;}size++; // 更新列表大小}
  • 2.删除元素

有增加就需要有删除

        /*** 删除链表中指定位置的元素。* @param index 要删除的元素的位置索引。* @throws IndexOutOfBoundsException 如果索引超出链表范围，则抛出异常。*/public void remove(int index) {// 检查索引是否超出链表范围if (index < 0 || index >= size) {throw new IndexOutOfBoundsException("Index out of bounds");}// 如果删除的是头节点if (index == 0) {head = head.next;} else {// 遍历找到要删除节点的前一个节点Node current = head;for (int i = 0; i < index - 1; i++) {current = current.next;}// 跳过要删除的节点，重新连接链表current.next = current.next.next;}size--; // 更新链表大小}/*** 删除链表中指定数据的元素。* @param data 要删除的元素数据。*/public void remove(E data) {// 如果链表为空，则直接返回if (head == null) {return;}// 如果头节点数据与要删除的数据相等，则将头节点指向下一个节点，并更新大小if (head.data.equals(data)) {head = head.next;size--;return;}// 从第二个节点开始遍历链表，寻找要删除的数据Node current = head;while (current.next != null) {// 如果找到要删除的数据，则跳过该节点，并更新大小if (current.next.data.equals(data)) {current.next = current.next.next;size--;return;}current = current.next;}}
  • 3.查询元素
    /*** 获取链表中指定位置的元素。** @param index 要获取元素的位置，从0开始计数。* @return 链表中指定位置的元素。* @throws IndexOutOfBoundsException 如果指定位置超出链表范围（小于0或大于等于链表长度）。*/public E get(int index) {// 检查索引是否超出链表范围if (index < 0 || index >= size) {throw new IndexOutOfBoundsException("Index out of bounds");}Node current = head;// 遍历链表，直到达到指定位置for (int i = 0; i < index; i++) {current = current.next;}return current.data; // 返回指定位置的元素}
  • 4.其他方法
    // 返回链表的大小public int size() {return size;}// 清空链表public void clear() {head = null; //垃圾回收器会自动清理内存size = 0;}

全部代码

public class MyLinkedList<E> {private class Node {E data;Node next;Node(E data) {this.data = data;this.next = null;}}private Node head;private int size;public MyLinkedList() {head = null;size = 0;}// 在链表末尾添加元素public void add(E data) {add(size, data);}/*** 在指定位置插入一个元素。* @param index 插入位置的索引，从0开始。* @param data 要插入的元素。* @throws IndexOutOfBoundsException 如果索引小于0或大于当前列表大小，则抛出异常。*/public void add(int index, E data) {// 检查索引是否超出范围if (index < 0 || index > size) {throw new IndexOutOfBoundsException("Index out of bounds");}Node newNode = new Node(data); // 创建新节点// 当索引为0时，将新节点插入到链表头部if (index == 0) {newNode.next = head;head = newNode;} else {// 遍历链表，找到插入位置的前一个节点Node current = head;for (int i = 0; i < index - 1; i++) {current = current.next;}newNode.next = current.next;current.next = newNode;}size++; // 更新列表大小}// 返回链表的大小public int size() {return size;}// 清空链表public void clear() {head = null;size = 0;}/*** 获取链表中指定位置的元素。** @param index 要获取元素的位置，从0开始计数。* @return 链表中指定位置的元素。* @throws IndexOutOfBoundsException 如果指定位置超出链表范围（小于0或大于等于链表长度）。*/public E get(int index) {// 检查索引是否超出链表范围if (index < 0 || index >= size) {throw new IndexOutOfBoundsException("Index out of bounds");}Node current = head;// 遍历链表，直到达到指定位置for (int i = 0; i < index; i++) {current = current.next;}return current.data; // 返回指定位置的元素}/*** 删除链表中指定位置的元素。* @param index 要删除的元素的位置索引。* @throws IndexOutOfBoundsException 如果索引超出链表范围，则抛出异常。*/public void remove(int index) {// 检查索引是否超出链表范围if (index < 0 || index >= size) {throw new IndexOutOfBoundsException("Index out of bounds");}// 如果删除的是头节点if (index == 0) {head = head.next;} else {// 遍历找到要删除节点的前一个节点Node current = head;for (int i = 0; i < index - 1; i++) {current = current.next;}// 跳过要删除的节点，重新连接链表current.next = current.next.next;}size--; // 更新链表大小}/*** 删除链表中指定数据的元素。* @param data 要删除的元素数据。*/public void remove(E data) {// 如果链表为空，则直接返回if (head == null) {return;}// 如果头节点数据与要删除的数据相等，则将头节点指向下一个节点，并更新大小if (head.data.equals(data)) {head = head.next;size--;return;}// 从第二个节点开始遍历链表，寻找要删除的数据Node current = head;while (current.next != null) {// 如果找到要删除的数据，则跳过该节点，并更新大小if (current.next.data.equals(data)) {current.next = current.next.next;size--;return;}current = current.next;}}public static void main(String[] args) {MyLinkedList<Integer> list = new MyLinkedList<>();list.add(1);list.add(2);list.add(3);list.add(1, 4); // 在索引1处插入元素4System.out.println("Size of LinkedList after insertion: " + list.size());System.out.println("Element at index 1: " + list.get(1));}
}

双向链表

双向链表是一种链表数据结构，其中每个节点都有两个指针，一个指向前一个节点，一个指向后一个节点。与单向链表相比更方便双向遍历和删除插入节点

其实实现上和上面一本一样，只是需要考虑一个prev指针


/*** MyLinkedList类，实现一个双向链表。* @param <E> 链表元素的类型。*/
public class MyLinkedList<E> {/*** 链表节点内部类。* 包含数据、前向指针和后向指针。*/private class Node {E data;Node prev;Node next;/*** 节点构造函数。* @param data 节点存储的数据。*/Node(E data) {this.data = data;this.prev = null;this.next = null;}}private Node head; // 链表头节点private Node tail; // 链表尾节点private int size; // 链表大小/*** 链表构造函数，初始化链表。*/public MyLinkedList() {head = null;tail = null;size = 0;}/*** 在链表末尾添加元素。* @param data 要添加的数据。*/public void add(E data) {add(size, data);}/*** 在指定位置插入元素。* @param index 插入的位置。* @param data 要插入的数据。* @throws IndexOutOfBoundsException 如果索引超出范围，则抛出异常。*/public void add(int index, E data) {// 检查索引是否有效if (index < 0 || index > size) {throw new IndexOutOfBoundsException("Index out of bounds");}Node newNode = new Node(data);// 处理头节点插入和尾节点插入的情况if (index == 0) {// 处理在头部插入的情况if (head == null) {head = newNode;tail = newNode;} else {newNode.next = head;head.prev = newNode;head = newNode;}} else if (index == size) {// 处理在尾部插入的情况newNode.prev = tail;tail.next = newNode;tail = newNode;} else {// 在中间位置插入Node current = head;for (int i = 0; i < index - 1; i++) {current = current.next;}newNode.next = current.next;newNode.prev = current;current.next.prev = newNode;current.next = newNode;}size++;}/*** 返回链表的大小。* @return 链表中元素的数量。*/public int size() {return size;}/*** 清空链表。* 将头尾指针置空，大小设为0。*/public void clear() {head = null;tail = null;size = 0;}/*** 获取指定位置的元素。* @param index 要获取元素的位置。* @return 位置处的元素。* @throws IndexOutOfBoundsException 如果索引超出范围，则抛出异常。*/public E get(int index) {// 检查索引是否有效if (index < 0 || index >= size) {throw new IndexOutOfBoundsException("Index out of bounds");}Node current = head;// 遍历链表，直到找到指定位置的元素for (int i = 0; i < index; i++) {current = current.next;}return current.data;}/*** 删除指定位置的元素。* @param index 要删除的元素的位置。* @throws IndexOutOfBoundsException 如果提供的索引超出链表范围，则抛出异常。*/public void remove(int index) {// 检查索引是否有效if (index < 0 || index >= size) {throw new IndexOutOfBoundsException("Index out of bounds");}// 根据索引位置的不同，分别处理删除头节点、尾节点和中间节点的情况if (size == 1) { // 当链表只有一个元素时，删除后同时将头尾指针置为nullhead = null;tail = null;} else if (index == 0) { // 删除头节点head = head.next;head.prev = null;} else if (index == size - 1) { // 删除尾节点tail = tail.prev;tail.next = null;} else { // 删除中间的节点Node current = head;for (int i = 0; i < index; i++) {current = current.next;}// 断开选定节点的前后连接current.prev.next = current.next;current.next.prev = current.prev;}size--; // 链表大小减1}/*** 删除链表中第一个匹配给定数据的节点。* @param data 要删除的数据。* 该方法首先检查链表是否为空，若为空则直接返回。* 接着区分三种情况：删除头节点、删除尾节点、删除中间节点。* 对于删除头节点和尾节点，需要更新头尾指针。* 对于删除中间节点，需要更新前后节点的指针。* 删除操作完成后，链表长度减一。*/public void remove(E data) {if (head == null) { // 链表为空，直接返回return;}// 处理删除头节点和尾节点的情况，以及中间节点的情况if (head.data.equals(data)) { // 删除头节点head = head.next;if (head != null) { // 更新头节点的前指针head.prev = null;}size--;return;}if (tail.data.equals(data)) { // 删除尾节点tail = tail.prev;tail.next = null; // 更新尾节点的后指针size--;return;}Node current = head; // 从头开始查找要删除的节点while (current != null) {if (current.data.equals(data)) { // 找到要删除的节点current.prev.next = current.next; // 更新前节点的后指针current.next.prev = current.prev; // 更新后节点的前指针size--;return;}current = current.next; // 继续查找下一个节点}}// 主函数，示例使用public static void main(String[] args) {MyLinkedList<Integer> list = new MyLinkedList<>();list.add(1);list.add(2);list.add(3);list.add(1, 4); // 在索引1处插入元素4System.out.println("Size of LinkedList after insertion: " + list.size());System.out.println("Element at index 1: " + list.get(1));}
}

总结

我们自己写的链表是一个简单的实现，用于演示链表的基本操作和原理，并作为学习链表数据结构的起点。通过自己动手实现链表，可以加深对链表的理解，并提升编程能力。作为学习链表数据结构的起点，它相比于标准库中的链表实现可能存在一些局限性，但非常适用于学习和理解链表的基本概念。

在这里插入图片描述

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

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

相关文章

STM32CubeMX学习笔记27---FreeRTOS事件

STM32CubeMX学习笔记27---FreeRTOS事件

一、简介 1、 基本概念 事件是一种实现任务间通信的机制&#xff0c;主要用于实现多任务间的同步&#xff0c;但事件通信只能是事件类型的通信&#xff0c;无数据传输。 与信号量不同的是&#xff0c;它可以实现一对多&#xff0c;多对多的同步。即一个任务可以等待多个事件的…
阅读更多...
CentOS使用Docker部署Halo并结合内网穿透实现公网访问本地博客

CentOS使用Docker部署Halo并结合内网穿透实现公网访问本地博客

文章目录 1. Docker部署Halo1.1 检查Docker版本如果未安装Docker可参考已安装Docker步骤&#xff1a;1.2 在Docker中部署Halo 2. Linux安装Cpolar2.1 打开服务器防火墙2.2 安装cpolar内网穿透 3. 配置Halo个人博客公网地址4. 固定Halo公网地址 本文主要介绍如何在CentOS 7系统使…
阅读更多...
C语言例4-33：求调和级数中第多少项的值大于10

C语言例4-33：求调和级数中第多少项的值大于10

代码如下&#xff1a; //求调和级数中第多少项的值大于10 //调和级数的第n项为11/21/3...1/n #include<stdio.h> #define LIMIT 10 int main(void) {int n1;float sum0.0;for(;;) //死循环&#xff0c;或者while&#xff08;1&#xff09;{sumsum1.0/n;if(sum&g…
阅读更多...
GitLab更新失败（Ubuntu）

GitLab更新失败（Ubuntu）

在Ubuntu下使用apt更新gitlab报错如下&#xff1a; An error occurred during the signature verification.The repository is not updated and the previous index files will be used.GPG error: ... Failed to fetch https://packages.gitlab.com/gitlab/gitlab-ee/ubuntu/d…
阅读更多...
Solidity Uniswap V2 Router swapTokensForExactTokens

Solidity Uniswap V2 Router swapTokensForExactTokens

最初的router合约实现了许多不同的交换方式。我们不会实现所有的方式&#xff0c;但我想向大家展示如何实现倒置交换&#xff1a;用未知量的输入Token交换精确量的输出代币。这是一个有趣的用例&#xff0c;可能并不常用&#xff0c;但仍有可能实现。 GitHub - XuHugo/solidit…
阅读更多...
elasticsearch 8.12+kibana 8.12

elasticsearch 8.12+kibana 8.12

准备工作&#xff1a;1.下载相关的安装包放到/usr/local/ES下面 elasticsearch下载地址:Download Elasticsearch | Elastic elasticsearch-head-master下载地址:https://github.com/mobz/elasticsearch-head/archive/master.zip node下载地址:Index of /dist/ kibana地址:Downl…
阅读更多...
设计模式之桥接模式解析

设计模式之桥接模式解析

桥接模式 1&#xff09;概述 1.定义 桥接模式(Bridge Pattern) 将抽象部分与它的实现部分分离&#xff0c;使它们都可以独立地变化。 2.作用 如果系统中某个类存在两个独立变化的维度&#xff0c;通过该模式可以将这两个维度分离出来&#xff0c;使两者可以独立扩展。 3.…
阅读更多...
(一)基于IDEA的JAVA基础5

(一)基于IDEA的JAVA基础5

Scanner的使用 使用scanner可以接收键盘上输入的数据&#xff0c; Scanner inputnew Scanner(System.in)&#xff1b; 导包的方式: 什么是导包&#xff0c;导入的是jdk提供的java开发工具包&#xff0c;我们建一个java文件&#xff0c;psvm快捷输入后&#xff0c;打上new S…
阅读更多...
静态住宅IP优缺点，究竟要怎么选？

静态住宅IP优缺点，究竟要怎么选？

在进行海外 IP 代理时&#xff0c;了解动态住宅 IP 和静态住宅 IP 的区别以及如何选择合适的类型非常重要。本文将介绍精态住宅 IP 特点和&#xff0c;并提供选择建议&#xff0c;帮助您根据需求做出明智的决策。 静态住宅 IP 的特点 静态住宅 IP 是指 IP 地址在一段时间内保…
阅读更多...
论文研读：Transformers Make Strong Encoders for Medical Image Segmentation

论文研读：Transformers Make Strong Encoders for Medical Image Segmentation

论文&#xff1a;TransUNet&#xff1a;Transformers Make Strong Encoders for Medical Image Segmentation 目录 Abstract Introduction Related Works 各种研究试图将自注意机制集成到CNN中。 Transformer Method Transformer as Encoder 图像序列化 Patch Embed…
阅读更多...
47 vue 常见的几种模型视图不同步的问题

47 vue 常见的几种模型视图不同步的问题

前言 这里主要是来看一下 关于 vue 中的一些场景下面 可能会出现 模型和视图 不同步更新的情况 然后 这种情况主要是 vue 中的对象 属性没有响应式的 setter, getter 然后 我们这里就来看一下 大多数的情况下的一个场景, 和一些处理方式 当然 处理方式主要是基于 Vue.set, …
阅读更多...
书生浦语训练营2期-第一节课笔记

书生浦语训练营2期-第一节课笔记

笔记总结: 了解大模型的发展方向、本质、以及新一代数据清洗过滤技术、从模型到应用的典型流程、获取数据集的网站、不同微调方式的使用场景和训练数据是什么&#xff0c;以及预训练和微调在训练优势、通信/计算调度、显存管理上的区别。 收获&#xff1a; 理清了预训练和微调…
阅读更多...
【优选算法】专题1 -- 双指针 -- 复写0

【优选算法】专题1 -- 双指针 -- 复写0

前言&#xff1a; 补充一下前文没有写到的双指针入门知识&#xff1a;专题1 -- 双指针 -- 移动零 目录 基础入门知识&#xff1a; 1. 复写零&#xff08;easy&#xff09; 1. 题⽬链接&#xff1a;1089.复习0 - 力扣&#xff08;LeetCode&#xff09; 2. 题⽬描述&#xff…
阅读更多...
windwos权限维持

windwos权限维持

1.php 不死马权限维持 <?php ignore_user_abort(); //关掉浏览器&#xff0c;PHP脚本也可以继续执行. set_time_limit(0);//通过set_time_limit(0)可以让程序无限制的执行下去 $interval 5; // 每隔*秒运行 do { $filename test.php; if(file_exists($filename)) { echo…
阅读更多...
iOS网络抓包工具全解析

iOS网络抓包工具全解析

摘要 本文将深入探讨iOS平台上常用的网络抓包工具&#xff0c;包括Charles、克魔助手、Thor和Http Catcher&#xff0c;以及通过SSH连接进行抓包的方法。此外&#xff0c;还介绍了克魔开发助手作为iOS应用开发的辅助工具&#xff0c;提供的全方面性能监控和调试功能。 在iOS应…
阅读更多...
一小时学习redis！

一小时学习redis！

redis 基于内存的数据存储系统 三种使用方式 redis优势 安装redis 最后一种方式只能得到5.0的redis版本 比较老&#xff01; 启动redis redis-server.exe 命令 停止ctrlc或关闭 启动客户端 redis-cli redisinsight安装 字符串 redis区分大小写 默认使用字符串存储 二进制…
阅读更多...
2024年，如何实现高效的自动化渗透测试？

2024年，如何实现高效的自动化渗透测试？

随着当前网络安全威胁的不断扩展与升级&#xff0c;开展渗透测试工作已经成为广大企业组织主动识别安全漏洞与潜在风险的关键过程。然而&#xff0c;传统的人工渗透测试模式对测试人员的专业能力和经验水平有很高的要求&#xff0c;企业需要投入较大的时间和资源才能完成。在此…
阅读更多...
如何快速搭建一个ELK环境？

如何快速搭建一个ELK环境？

前言 ELK是Elasticsearch、Logstash和Kibana三个开源软件的统称&#xff0c;通常配合使用&#xff0c;并且都先后归于Elastic.co企业名下&#xff0c;故被简称为ELK协议栈。 Elasticsearch是一个实时的分布式搜索和分析引擎&#xff0c;它可以用于全文搜索、结构化搜索以及分…
阅读更多...
网络稳定性（蓝桥省赛）

网络稳定性（蓝桥省赛）

0网络稳定性 - 蓝桥云课 (lanqiao.cn) 知识点&#xff1a;克鲁斯卡尔生成树&#xff0c;lca&#xff0c;倍增 最小生成树的模板&#xff1a;最小生成树【模板】-CSDN博客 题解代码如下&#xff1a; #include<bits/stdc.h> using namespace std; const int N3e5100; co…
阅读更多...
Gemma开源AI指南

Gemma开源AI指南

近几个月来&#xff0c;谷歌推出了 Gemini 模型&#xff0c;在人工智能领域掀起了波澜。 现在&#xff0c;谷歌推出了 Gemma&#xff0c;再次引领创新潮流&#xff0c;这是向开源人工智能世界的一次变革性飞跃。 与前代产品不同&#xff0c;Gemma 是一款轻量级、小型模型&…
阅读更多...
推荐文章
最新文章

Copyright @ 2022~2023

友情链接： 我的编程经验分享 一条长河网 尧图网站开发 尧图建网站 广利置业