数据结构基础（三）链表

链表（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.rhkb.cn/news/286805.html

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

相关文章

放弃 Rust 选择 Zig，Xata 团队推出 pgzx —— 计划使用 Zig 开发基于 PG 的分布式数据库

放弃 Rust 选择 Zig，Xata 团队推出 pgzx —— 计划使用 Zig 开发基于 PG 的分布式数据库

Summary Xata 公司在基于 PostgresSQL 开发自己的分布式数据库&#xff0c;出于 Zig 和 C 语言以及 PostgreSQL 的 API 有更好的互操作性的考虑&#xff0c;他们选择了 Zig 而非当红炸子鸡语言 Rust。他们的博客文章中对 pgzx 进行了介绍。让我们来看下他们对 Zig 和 Rust 语言…
阅读更多...
【开发环境搭建篇】Git的安装和配置

【开发环境搭建篇】Git的安装和配置

作者介绍&#xff1a;本人笔名姑苏老陈&#xff0c;从事JAVA开发工作十多年了&#xff0c;带过大学刚毕业的实习生&#xff0c;也带过技术团队。最近有个朋友的表弟&#xff0c;马上要大学毕业了&#xff0c;想从事JAVA开发工作&#xff0c;但不知道从何处入手。于是&#xff0…
阅读更多...
利用Python和IP技术实现智能旅游情报系统

利用Python和IP技术实现智能旅游情报系统

文章目录 引言一、系统架构设计1. 数据采集模块2. 数据处理模块3. 用户界面模块 二、数据获取技术应用三、系统功能展示四、亮数据采集工具介绍五、总结六、号外 引言 随着旅游行业的不断发展&#xff0c;人们对旅游信息的需求也越来越大。为了帮助旅行者更好地规划行程&#…
阅读更多...
基于javaweb(springboot+mybatis)宠物医院预约管理系统设计和实现以及论文报告

基于javaweb(springboot+mybatis)宠物医院预约管理系统设计和实现以及论文报告

基于javaweb(springbootmybatis)宠物医院预约管理系统设计和实现以及论文报告 博主介绍&#xff1a;多年java开发经验&#xff0c;专注Java开发、定制、远程、文档编写指导等,csdn特邀作者、专注于Java技术领域 作者主页 央顺技术团队 Java毕设项目精品实战案例《1000套》 欢迎…
阅读更多...
【超全详解一文搞懂】Scala基础

【超全详解一文搞懂】Scala基础

目录 Scala 01 —— Scala基础一、搭建Scala开发环境安装Scala编译器在IDEA中进行scala编码 二、Scala简介与概述Scala简介Scala概述Scala代码规范 三、理解Scala变量与数据类型Scala的变量与常量Scala和Java变量的区别 Scala的数据类型 四、Scala的程序逻辑1.表达式2.运算符3.…
阅读更多...
紫鸾5.0：紫光云新一代敏捷应用开发平台全家桶

紫鸾5.0：紫光云新一代敏捷应用开发平台全家桶

曾几何时&#xff0c;“瀑布式”占据了二十世纪软件开发的主流&#xff0c;开发时间往往以年计&#xff0c;一款软件应用动辄几年才能交付。而随着社会生产力的跃升&#xff0c;“瀑布式”已严重跟不上时代的节奏&#xff0c;2001年&#xff0c;“敏捷宣言”的发布&#xff0c;…
阅读更多...
AtCoder Regular Contest 143 C - Piles of Pebbles 博弈 ， 每个人要拿的是固定的！不够也算不能拿

AtCoder Regular Contest 143 C - Piles of Pebbles 博弈 ， 每个人要拿的是固定的！不够也算不能拿

C - Piles of Pebbles 题意&#xff1a; n堆鹅卵石&#xff0c;第一个人可以拿任意堆x个&#xff0c;第二个人可以拿任意堆y个&#xff0c;第一个人先拿&#xff0c;谁不能拿谁败。 思路&#xff1a; 这个题我一直没读清楚&#xff0c;如文章标题&#xff0c;拿的是固定数目…
阅读更多...
MySQL查询约束

MySQL查询约束

1 DML DML 数据操作语句 插入 insert 更新 update 删除 delete 1.1 更新 语法 update 表名 set 字段 值 [, 字段2 值2, ... ] [where 字段 值]; -- [, 字段2 值2, ... ] 是指,可选的,可以同时修改多个列的值 -- [where 字段 值] 是指,可选的,加上是指过滤,只更新符合条…
阅读更多...
【C#】C#窗体应用修改窗体的标题和图标

【C#】C#窗体应用修改窗体的标题和图标

修改窗体顶部的标题和图表&#xff0c;如果不修改则会使用默认的图标&#xff0c;标题默认为Form1&#xff0c;如第一张图&#xff0c;这时候如果想换成和系统有关的内容&#xff0c;如第二张图&#xff0c;可以使用下面的方法进行修改&#xff0c;修改后打开该软件任务栏显示的…
阅读更多...
前台处理：CO主数据之成本中心标准层次更改-＜OKEON＞

前台处理：CO主数据之成本中心标准层次更改-＜OKEON＞

一、背景&#xff1a; 前面讲解了成本要素和成本要素组&#xff0c;我们继续介绍成本控制与核算的主数据之成本中心&#xff0c;成本控制分主数据篇和业务篇&#xff1a; 主数据篇主要内容&#xff1a;成本要素、成本中心、订单、作业类型、工作中心&#xff1b; 业务篇主要…
阅读更多...
ServletConfig和ServletContext

ServletConfig和ServletContext

ServletConfig接口 在Servlet运行期间&#xff0c;需要一些配置信息&#xff0c;这些信息都可以在WebServlet注解的属性中配置。当Tomcat初始化一个Servlet时&#xff0c;会将该Servlet的配置信息封装到一个ServletConfig对象中&#xff0c;通过调用init(ServletConfig config…
阅读更多...
【go从入门到精通】for循环控制

【go从入门到精通】for循环控制

作者简介&#xff1a; 高科&#xff0c;先后在 IBM PlatformComputing从事网格计算&#xff0c;淘米网&#xff0c;网易从事游戏服务器开发&#xff0c;拥有丰富的C&#xff0c;go等语言开发经验&#xff0c;mysql&#xff0c;mongo&#xff0c;redis等数据库&#xff0c;设计模…
阅读更多...
32.768K晶振X1A000141000300适用于无人驾驶汽车电子设备

32.768K晶振X1A000141000300适用于无人驾驶汽车电子设备

科技的发展带动电子元器件的发展电子元器件-“晶振”为现代的科技带来了巨大的贡献&#xff0c;用小小的身体发挥着大大的能量。 近两年无人驾驶汽车热度很高&#xff0c;不少汽车巨头都已入局。但这项技术的难度不小&#xff0c;相信在未来几年里&#xff0c;无人驾驶汽车这项…
阅读更多...
Python网络爬虫实战进阶：代理IP池免费送

Python网络爬虫实战进阶：代理IP池免费送

在Python网络爬虫实战中&#xff0c;代理IP池是一个非常重要的技术环节。代理IP池可以帮助爬虫隐藏真实的IP地址&#xff0c;防止被目标网站封禁&#xff0c;同时可以提高爬虫的爬取效率。本文将详细介绍代理IP池在Python网络爬虫实战中的应用。 文章目录 一、代理IP池的概念二…
阅读更多...
蓝桥杯2023真题-幸运数字

蓝桥杯2023真题-幸运数字

目录 进制转换&#xff1a; 思路 代码 题目链接&#xff1a; 0幸运数字 - 蓝桥云课 (lanqiao.cn) 本题就考的进制转换问题&#xff0c;要将十进制5转换成二进制&#xff0c;通过%2,和/2的交替使用即可完成&#xff0c;所得余数就是转换成的二进制各位的值&#xff0c;转换…
阅读更多...
[Qt学习笔记]Qt实现自定义控件SwitchButton开关按钮

[Qt学习笔记]Qt实现自定义控件SwitchButton开关按钮

1、功能介绍 在项目UI中使用较多的打开/关闭的开关按钮&#xff0c;一般都是找图片去做效果&#xff0c;比如说如下的图像来表征打开或关闭。 如果想要控件有打开/关闭的动画效果或比较好的视觉效果&#xff0c;这里就可以使用自定义控件&#xff0c;使用Painter来绘制控件。软…
阅读更多...
数据库运行状况和性能监控工具

数据库运行状况和性能监控工具

数据库监控是跟踪组织中数据库的可用性、安全性和性能的过程&#xff0c;它涉及通过跟踪各种关键指标来分析数据库的性能&#xff0c;确保数据库的正常运行并具有深入的可见性&#xff0c;并在出现潜在问题时触发即时警报&#xff0c;以采取主动措施来确保数据库的高可用性。 …
阅读更多...
美团2024届秋招笔试第二场编程真题

美团2024届秋招笔试第二场编程真题

要么是以0开头 要么以1开头 选择最小的答案累加 import java.util.Scanner; import java.util.*; // 注意类名必须为 Main, 不要有任何 package xxx 信息 public class Main {public static void main(String[] args) {Scanner in new Scanner(System.in);// 注意 hasNext 和…
阅读更多...
OpenLayers基础教程——WebGLPoints图层样式的设置方法

OpenLayers基础教程——WebGLPoints图层样式的设置方法

1、前言 前一篇博客介绍了如何在OpenLayers中使用WebGLPoints加载海量数据点的方法&#xff0c;这篇博客就来介绍一下WebGLPoints图层的样式设置问题。 2、样式运算符 在VectorLayer图层中&#xff0c;我们只需要创建一个ol.style.Style对象即可&#xff0c;WebGLPoints则不…
阅读更多...
【C++】基础：STL容器库

【C++】基础：STL容器库

&#x1f60f;★,:.☆(&#xffe3;▽&#xffe3;)/$:.★ &#x1f60f; 这篇文章主要介绍STL容器库。 学其所用&#xff0c;用其所学。——梁启超 欢迎来到我的博客&#xff0c;一起学习&#xff0c;共同进步。 喜欢的朋友可以关注一下&#xff0c;下次更新不迷路&#x1f95…
阅读更多...
最新文章
推荐文章

Copyright @ 2022~2023