基础数据结构——链表（单向链表，双向链表，循环链表）

1.概述

在计算机科学中，链表是数据元素的线性集合，其每个元素都指向下一个元素，元素存储上并不连续

分类

  • 单向链表，每个元素只知道其下一个元素是谁
    在这里插入图片描述

  • 双向链表，每个元素知道其上一个元素和下一个元素
    在这里插入图片描述

  • 循环链表，通常的链表尾节点 tail 指向的都是 null，而循环链表的 tail 指向的是头节点 head
    在这里插入图片描述
    链表内还有一种特殊的节点称为哨兵（Sentinel）节点，也叫做哑元（ Dummy）节点，它不存储数据，通常用作头尾，用来简化边界判断，如下图所示
    在这里插入图片描述

随机访问性能

根据 index 查找，时间复杂度 O ( n ) O(n) O(n)

插入或删除性能

  • 起始位置： O ( 1 ) O(1) O(1)
  • 结束位置：如果已知 tail 尾节点是 O ( 1 ) O(1) O(1)，不知道 tail 尾节点是 O ( n ) O(n) O(n)
  • 中间位置：根据 index 查找时间 + O ( 1 ) O(1) O(1)

2.单向链表

public class SinglyLinkedList implements Iterable<Integer> {//定义头节点private Node head = null;/*** 在头部添加** @param value*/public void addFirst(int value) {head = new Node(head, value);}/*** 在尾部添加** @param value*/public void addLast(int value) {if (head == null) {addFirst(value);} else {Node last = findLast();last.next = new Node(null, value);}}/*** 根据索引插入** @param index* @param value*/public void insert(int index, int value) {if (index < 0) {throw new IndexOutOfBoundsException("index:" + index + " error");}if (index == 0) {addFirst(value);return;}Node prev = findNode(index - 1);if (prev == null) {throw new IndexOutOfBoundsException("index:" + index + " error");}prev.next = new Node(prev.next, value);}/*** 删除第一个节点*/public void removeFirst() {if (head == null) {throw new IndexOutOfBoundsException("数组为空，不能删除");}head = head.next;}/*** 根据索引删除节点** @param index*/public void remove(int index) {if (index < 0) {throw new IndexOutOfBoundsException("index:" + index + " error");}if (index == 0) {removeFirst();return;}Node prev = findNode(index - 1);if (prev == null) {throw new IndexOutOfBoundsException("index:" + index + " error");}Node removed = prev.next;if (removed == null) {throw new IndexOutOfBoundsException("index:" + index + " error");}prev.next = removed.next;}/*** 根据索引获取节点的值** @param index* @return*/public int get(int index) {Node node = findNode(index);if (node == null) {throw new IndexOutOfBoundsException("index:" + index + " error");}return node.value;}private Node findNode(int index) {/*int i = 0;for (Node pointer = head; pointer != null; pointer = pointer.next, i++) {if(i == index){return pointer;}}return null;*/int i = 0;Node pointer = head;while (pointer != null) {if (i == index) {return pointer;}pointer = pointer.next;i++;}return null;}/*** 查找最后一个节点** @return*/private Node findLast() {Node pointer = head;while (pointer != null && pointer.next != null) {pointer = pointer.next;}return pointer;}/*** 循环操作** @param consumer*/public void foreach(Consumer<Integer> consumer) {/*Node pointer = head;while (pointer != null) {consumer.accept(pointer.value);pointer = pointer.next;}*/for (Node pointer = head; pointer != null; pointer = pointer.next) {consumer.accept(pointer.value);}}/*** 递归循环*/public void recursion(Consumer<Integer> consumer) {recursion(head, consumer);}private void recursion(Node node, Consumer<Integer> consumer) {if (node != null) {consumer.accept(node.value);recursion(node.next, consumer);}}/*** 迭代器** @return*/@Overridepublic Iterator<Integer> iterator() {return new Iterator<Integer>() {Node pointer = head;@Overridepublic boolean hasNext() {return pointer != null;}@Overridepublic Integer next() {int value = pointer.value;pointer = pointer.next;return value;}};}/*** 定义节点信息*/private static class Node {private Node next;//下一个节点的指针private int value;//值public Node(Node next, int value) {this.next = next;this.value = value;}}
}

3.单向链表-带哨兵

public class SinglyLinkedListSentinel implements Iterable<Integer> {//定义哨兵节点private Node sentinel = new Node(null, -1);/*** 在头部添加** @param value*/public void addFirst(int value) {insert(0, value);}/*** 在尾部添加** @param value*/public void addLast(int value) {Node last = findLast();last.next = new Node(null, value);}/*** 根据索引插入** @param index* @param value*/public void insert(int index, int value) {if (index < 0) {throw new IndexOutOfBoundsException("index:" + index + " error");}Node prev = findNode(index - 1);if (prev == null) {throw new IndexOutOfBoundsException("index:" + index + " error");}prev.next = new Node(prev.next, value);}/*** 删除第一个节点*/public void removeFirst() {remove(0);}/*** 根据索引删除节点** @param index*/public void remove(int index) {if (index < 0) {throw new IndexOutOfBoundsException("index:" + index + " error");}Node prev = findNode(index - 1);if (prev == null) {throw new IndexOutOfBoundsException("index:" + index + " error");}Node removed = prev.next;if (removed == null) {throw new IndexOutOfBoundsException("index:" + index + " error");}prev.next = removed.next;}/*** 根据索引获取节点的值** @param index* @return*/public int get(int index) {Node node = findNode(index);if (node == null) {throw new IndexOutOfBoundsException("index:" + index + " error");}return node.value;}private Node findNode(int index) {/*int i = 0;for (Node pointer = head; pointer != null; pointer = pointer.next, i++) {if(i == index){return pointer;}}return null;*/int i = -1;Node pointer = sentinel;while (pointer != null) {if (i == index) {return pointer;}pointer = pointer.next;i++;}return null;}/*** 查找最后一个节点** @return*/private Node findLast() {Node pointer = sentinel;while (pointer.next != null) {pointer = pointer.next;}return pointer;}/*** 循环操作** @param consumer*/public void foreach(Consumer<Integer> consumer) {/*Node pointer = head;while (pointer != null) {consumer.accept(pointer.value);pointer = pointer.next;}*/for (Node pointer = sentinel.next; pointer != null; pointer = pointer.next) {consumer.accept(pointer.value);}}/*** 递归循环*/public void recursion(Consumer<Integer> consumer) {recursion(sentinel.next, consumer);}private void recursion(Node node, Consumer<Integer> consumer) {if (node != null) {consumer.accept(node.value);recursion(node.next, consumer);}}/*** 迭代器** @return*/@Overridepublic Iterator<Integer> iterator() {return new Iterator<Integer>() {Node pointer = sentinel.next;@Overridepublic boolean hasNext() {return pointer != null;}@Overridepublic Integer next() {int value = pointer.value;pointer = pointer.next;return value;}};}/*** 定义节点信息*/private static class Node {private Node next;//下一个节点的指针private int value;//值public Node(Node next, int value) {this.next = next;this.value = value;}}
}

4.双向链表-带哨兵

public class DoublyLinkedListSentinel implements Iterable<Integer> {private Node head = new Node(null, -1, null);//头哨兵节点private Node tail = new Node(null, -2, null);//尾哨兵节点public DoublyLinkedListSentinel() {this.head.next = tail;//头哨兵的下一个节点指向尾节点this.tail.prev = head;//尾哨兵的上一个节点指向头节点}/*** 查询节点** @param index* @return*/private Node findNode(int index) {if (index < -1) {throw new IndexOutOfBoundsException("index:" + index + " error");}int i = -1;Node pointer = head;while (pointer != tail) {if (index == i) {return pointer;}pointer = pointer.next;i++;}return null;}/*** 根据索引插入节点** @param index* @param value*/public void insert(int index, int value) {Node prev = findNode(index - 1);//上一个节点if (prev == null) {throw new IndexOutOfBoundsException("index:" + index + " error");}Node next = prev.next;Node add = new Node(prev, value, next);prev.next = add;next.prev = add;}/*** 根据索引删除** @param index*/public void remove(int index) {Node prev = findNode(index - 1);//上一个节点if (prev == null) {throw new IndexOutOfBoundsException("index:" + index + " error");}Node removed = prev.next;if (removed == tail) {throw new IndexOutOfBoundsException("index:" + index + " error");}Node next = removed.next;prev.next = next;next.prev = prev;}/*** 在头部添加** @param value*/public void addFirst(int value) {insert(0, value);}/*** 移除第一个节点*/public void removeFirst() {remove(0);}/*** 在尾部追加** @param value*/public void addLast(int value) {Node prev = tail.prev;Node add = new Node(prev, value, tail);prev.next = add;tail.prev = add;}/*** 移除最后一个节点*/public void removeLast() {Node removed = tail.prev;//要移除的节点if (tail.prev == head) {throw new IndexOutOfBoundsException("暂无最后一个节点");}Node prev = removed.prev;//上一个节点tail.prev = prev;prev.next = tail;}/*** 迭代** @return*/@Overridepublic Iterator<Integer> iterator() {return new Iterator<>() {Node pointer = head.next;@Overridepublic boolean hasNext() {return pointer != tail;}@Overridepublic Integer next() {int value = pointer.value;pointer = pointer.next;return value;}};}/*** 定义节点信息*/private static class Node {private Node prev;//上一个节点的指针private int value;//值private Node next;//下一个节点的指针public Node(Node prev, int value, Node next) {this.prev = prev;this.value = value;this.next = next;}}
}

5.双向环形链表-带哨兵

双向环形链表带哨兵，这时哨兵既作为头，也作为尾
在这里插入图片描述

public class DoublyCircularLinkedListSentinel implements Iterable<Integer> {private Node sentinel = new Node(null, -1, null);//定义哨兵节点public DoublyCircularLinkedListSentinel() {this.sentinel.prev = sentinel;this.sentinel.next = sentinel;}/*** 添加头部节点** @param value*/public void addFirst(int value) {Node prev = sentinel;Node next = sentinel.next;Node add = new Node(prev, value, next);prev.next = add;next.prev = add;}/*** 添加尾部节点** @param value*/public void addLast(int value) {Node next = sentinel;Node prev = sentinel.prev;Node add = new Node(prev, value, next);prev.next = add;next.prev = add;}/*** 移除头部节点*/public void removeFirst() {Node prev = sentinel;Node removed = sentinel.next;if (removed == sentinel) {throw new IndexOutOfBoundsException("暂无节点");}Node next = removed.next;prev.next = next;next.prev = prev;}/*** 移除头部节点*/public void removeLast() {Node next = sentinel;Node removed = sentinel.prev;if (removed == sentinel) {throw new IndexOutOfBoundsException("暂无节点");}Node prev = removed.prev;prev.next = next;next.prev = prev;}/*** 根据值删除节点** @param value*/public void removeByValue(int value) {Node removed = findByValue(value);if (removed == null) {return;}Node prev = removed.prev;Node next = removed.next;prev.next = next;next.prev = prev;}/*** 根据值查找节点** @param value* @return*/private Node findByValue(int value) {Node pointer = sentinel.next;while (pointer != sentinel) {if (pointer.value == value) {return pointer;}pointer = pointer.next;}return null;}/*** 递归遍历** @param consumer*/public void recursion(Consumer<Integer> consumer) {recursion(sentinel.next, consumer);}/*** 递归遍历** @param node* @param consumer*/private void recursion(Node node, Consumer<Integer> consumer) {if (node != sentinel) {consumer.accept(node.value);recursion(node.next, consumer);}}//节点类private static class Node {private Node prev;private int value;private Node next;public Node(Node prev, int value, Node next) {this.prev = prev;this.value = value;this.next = next;}}@Overridepublic Iterator<Integer> iterator() {return new Iterator<Integer>() {Node pointer = sentinel.next;@Overridepublic boolean hasNext() {return pointer != sentinel;}@Overridepublic Integer next() {int value = pointer.value;pointer = pointer.next;return value;}};}
}

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

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

相关文章

EasyExcel填充模板导出excel.xlsx

EasyExcel填充模板导出excel.xlsx

菜鸟的自我救赎&#xff0c;自从有了GPT&#xff0c;还是头一次一个bug写一天。 直接贴导出excel模板的完整案例 官网冲刺 EasyExcel EasyExcel填充模板导出excel.xlsx / 导出excel模板 一、bug(不需要请跳过) 1.1 使用apache poi操作excel报错 java.lang.NoSuchMethodError…
阅读更多...
与双指针的亲密接触：快与慢的浪漫交错

与双指针的亲密接触：快与慢的浪漫交错

公主请阅 1.合并两个有序数组1.1 题目说明示例 1示例 2示例 3 1.2 题目分析 1.3代码部分1.4 代码解析 2.移动零2.1题目说明示例 1示例 2 2.2题目分析2.3代码部分2.4代码解析 1.合并两个有序数组 题目传送门 1.1 题目说明 给你两个按 非递减顺序 排列的整数数组 nums1 和 nums…
阅读更多...
汽车免拆诊断案例 | 2022款大众捷达VS5车行驶中挡位偶尔会锁在D3挡

汽车免拆诊断案例 | 2022款大众捷达VS5车行驶中挡位偶尔会锁在D3挡

故障现象　 一辆2022款大众捷达VS5汽车&#xff0c;搭载EA211发动机和手自一体变速器&#xff0c;累计行驶里程约为4.5万km。该车行驶中挡位偶尔会锁在D3挡&#xff0c;车速最高约50 km/h&#xff0c;且组合仪表上的发动机故障灯和EPC灯异常点亮。 故障诊断　 用故障检测仪检…
阅读更多...
linux一二三章那些是重点呢

linux一二三章那些是重点呢

第一章 静态库动态库的区别 什么是库 库文件是计算机上的一类文件&#xff0c;可以简单的把库文件看成一种代码仓库&#xff0c;它提供给使用者一些可以直接 拿来用的变量、函数或类。 如何制作 静态动态库 静态库&#xff1a; GCC 进行链接时&#xff0c;会把静态库中代码打…
阅读更多...
MySQL-15.DQL-分页查询

MySQL-15.DQL-分页查询

一.DQL-分页查询 -- 分页查询 -- 1. 从 起始索引0 开始查询员工数据&#xff0c;每页展示5条记录 select * from tb_emp limit 0,5; -- 2.查询 第1页 员工数据&#xff0c;每页展示5条记录 select * from tb_emp limit 0,5; -- 3.查询 第2页 员工数据&#xff0c;每页展示5条记…
阅读更多...
Golang | Leetcode Golang题解之第491题非递减子序列

Golang | Leetcode Golang题解之第491题非递减子序列

题目&#xff1a; 题解&#xff1a; var (temp []intans [][]int )func findSubsequences(nums []int) [][]int {ans [][]int{}dfs(0, math.MinInt32, nums)return ans }func dfs(cur, last int, nums []int) {if cur len(nums) {if len(temp) > 2 {t : make([]int, len(…
阅读更多...
4.计算机网络_TCP

4.计算机网络_TCP

可靠与效率 TCP的主要特点&#xff1a; TCP是面向连接的运输层协议&#xff0c;每一条TCP连接只能有两个端点&#xff0c;即&#xff1a;点对点、一对一形式。每一个端口都是一个socket。TCP提供可靠交付的服务TCP提供全双工通信&#xff0c;因为TCP的收发缓冲区是分开的。TC…
阅读更多...
java导出带图形的word

java导出带图形的word

先看效果图&#xff1a;方法都是一样的&#xff0c;所以数据只做了前两组 第一步需要准备模版&#xff1a; 新建一个word插入图表&#xff0c;选择想要的图表。 编辑图表&#xff1a;营业额表示数字&#xff0c;季度表示文字。其他的样式编辑可根据自己的需求更改&#xff0c;…
阅读更多...
（42）MATLAB中使用fftshift绘制以零为中心的功率谱

（42）MATLAB中使用fftshift绘制以零为中心的功率谱

文章目录 前言一、MATLAB代码二、仿真结果画图 前言 在分析信号的频率分量时&#xff0c;将零频分量平移到频谱中心会很有帮助。本例给出绘制以零为中心的功率谱的方法。 一、MATLAB代码 代码如下&#xff1a; f 1; % 余弦波的振荡频率&#xf…
阅读更多...
400行程序写一个实时操作系统（十）：用面向对象思想构建抢占式内核

400行程序写一个实时操作系统（十）：用面向对象思想构建抢占式内核

前言 通过前几章的学习&#xff0c;我们学会了如何为RTOS设计一个合理的内存管理算法。现在&#xff0c;是时候学习设计RTOS内核了。 关于RTOS内核的文章也有很多&#xff0c;但都有一点先射箭再化靶子的意味。要么是代码连篇解释却寥寥无几&#xff0c;要么是要先怎么样再怎么…
阅读更多...
大数据linux操作系统

大数据linux操作系统

第一关&#xff1a;Linux的初体验 答案&#xff1a; cd / ls -a / &#xff08;里面有空格要注意&#xff09; 第二关&#xff1a;Linux的常用命令 答案&#xff1a; touch newfile mkdir newdir cp newfile newdir/newfileCpy 第三关&#xff1a;Linux查询命令帮助语句…
阅读更多...
飞机大战告尾

飞机大战告尾

参考 PPO算法逐行代码详解 链接 通过网盘分享的文件&#xff1a;PlaneWar 链接: https://pan.baidu.com/s/1cbLKTcBxL6Aem3WkyDtPzg?pwd1234 提取码: 1234 10.17关于博客发了又改这件事 悲催的事 今天训练了一早上ppo模型&#xff0c;满怀期待的检测成果时发现一点长进都…
阅读更多...
根据语音生成视频33搜帧

根据语音生成视频33搜帧

33搜帧&#xff0c;是一个能根据语音生成视频的网站&#xff0c;33搜帧 - 视频帧画面搜索引擎 33搜帧是一个使用AI技术构建的视频帧画面搜索引擎&#xff0c;和一般素材平台通过视频标签来搜索视频不同&#xff0c;33搜帧能搜索到视频素材中的每一帧画面&#xff0c;这个功能可…
阅读更多...
基于SpringBoot+Vue+uniapp的海产品加工销售一体化管理系统的详细设计和实现(源码+lw+部署文档+讲解等)

基于SpringBoot+Vue+uniapp的海产品加工销售一体化管理系统的详细设计和实现(源码+lw+部署文档+讲解等)

详细视频演示 请联系我获取更详细的视频演示 项目运行截图 技术框架 后端采用SpringBoot框架 Spring Boot 是一个用于快速开发基于 Spring 框架的应用程序的开源框架。它采用约定大于配置的理念&#xff0c;提供了一套默认的配置&#xff0c;让开发者可以更专注于业务逻辑而不…
阅读更多...
软考（网工）——网络操作系统与应用服务器

软考（网工）——网络操作系统与应用服务器

文章目录 网络操作系统与应用服务器&#x1f550;本地用户与组1️⃣Windows server 2008R2 本地用户与组2️⃣常见用户组与权限 &#x1f551;活动目录1️⃣活动目录2️⃣活动目录&#xff08;Active Directory&#xff0c;AD)3️⃣活动目录工作组分类 &#x1f552;远程桌面与…
阅读更多...
uniapp学习（005-1 详解Part.1）

uniapp学习（005-1 详解Part.1）

零基础入门uniapp Vue3组合式API版本到咸虾米壁纸项目实战&#xff0c;开发打包微信小程序、抖音小程序、H5、安卓APP客户端等 总时长 23:40:00 共116P 此文章包含第36p-第p40的内容 文章目录 响应式尺寸单位 rpx各种工具修改ui给的图片的宽度ps操作步骤即时设计操作步骤&…
阅读更多...
高级算法设计与分析 学习笔记13 线性规划

高级算法设计与分析 学习笔记13 线性规划

注意是线性规划不是动态规划哦 好家伙&#xff0c;这不是凸优化吗&#xff1f; 凸优化标准形式&#xff1a; 先改成统一最大化&#xff08;凸优化那边怎么是统一最小化&#xff1f;&#xff09; 原来的x2正负无所谓&#xff0c;但我希望每个x都是有限制的&#xff0c;所以把它改…
阅读更多...
高德开放平台API调用实战指南

高德开放平台API调用实战指南

本文 一、地图展示1.1 地图初始化与展示1.2 自定义标记 二、路线规划2.1 驾车路线规划2.2 步行路线规划 三、定位服务3.1 使用JavaScript API进行定位3.2 IP定位 四、实时交通信息查询4.1 获取实时交通路况 五、智能调度引擎总结 一、地图展示 地图展示是开发基于地理信息系统…
阅读更多...
【MySQL】设置二进制日志文件自动过期，从根源上解决占满磁盘的问题：通过修改 binlog_expire_logs_seconds 配置项

【MySQL】设置二进制日志文件自动过期，从根源上解决占满磁盘的问题：通过修改 binlog_expire_logs_seconds 配置项

引言 MySQL的二进制日志&#xff08;binlog&#xff09;文件记录了数据库中所有更改的详细信息&#xff0c;包括但不限于对数据的插入、删除、更新&#xff0c;对表和数据库的创建、更改、删除等操作。每一次这样的操作都会在二进制日志中生成一个新的日志事件&#xff0c;并被…
阅读更多...
【Linux】命令行下的增删查改之“查看”

【Linux】命令行下的增删查改之“查看”

致谢:Linux常用命令大全(手册) – 真正好用的Linux命令在线查询网站 提供的命令查询 头部内容获取(head) head命令的功能是显示文件开头的内容&#xff0c;默认值为前10行。 指令参数&#xff1a; -n 定义显示行数 -c 指定显示头部内容的字符数 -v 总是显示文件名的头信…
阅读更多...
最新文章
推荐文章

Copyright @ 2022~2023