当前位置: 首页 > news >正文

数据结构(Java)——链表

1.概念及结构

  链表是一种 物理存储结构上非连续 存储结构,数据元素的 逻辑顺序 是通过链表中的 引用链接 次序实现的 。

2.分类

链表的结构非常多样,以下情况组合起来就有 8 种链表结构:
(1)单向或者双向
(2)带头或者不带头
(3)循环或者不循环
即单向带头循环链表、单向不带头循环链表、单向带头不循环链表、单向不带头不循环链表、双向带头循环链表、双向不带头循环链表、双向带头不循环链表和双向不带头不循环链表。
虽然有这么多的链表的结构,但是我们本篇主要讲两种 :
  • 无头单向非循环链表结构简单,一般不会单独用来存数据。实际中更多是作为其他数据结构的子结构,如哈希桶、图的邻接表等等。
  • 无头双向非循环链表:在Java的集合框架库中LinkedList底层实现就是无头双向非循环链表。

3. 代码实现

3.1 无头单向非循环链表

3.1.1 节点结

static class ListNode {public int val;public ListNode next;public ListNode(int val) {this.val = val;}}

3.1.2 方法接口

public interface ISingleLinkedList {
//头插法
public void addFirst(int data);
//尾插法
public void addLast(int data);
//任意位置插入,第一个数据节点为0号下标
public void addIndex(int index,int data);
//查找是否包含关键字key是否在单链表当中
public boolean contains(int key);
//删除第一次出现关键字为key的节点
public void remove(int key);
//删除所有值为key的节点
public void removeAllKey(int key)
//得到单链表的长度
public int size()
//清空链表
public void clear() 
//打印链表
public void display()
}

3.1.3 功能实现

public class MySingleLinkedList implements IMySingleLinkedList {@Overridepublic void addFirst(int data) {ListNode node = new ListNode(data);node.next = head;head = node;}@Overridepublic void addLast(int data) {ListNode node = new ListNode(data);if(head == null) {head = node;return;}ListNode cur = head;while (cur.next != null) {cur = cur.next;}cur.next = node;}@Overridepublic void addIndex(int index,int data) {//1.判断index的合法性try {checkIndex(index);}catch (IndexNotLegalException e) {e.printStackTrace();}//2.index == 0  || index == size()if(index == 0) {addFirst(data);return;}if(index == size()) {addLast(data);return;}//3. 找到index的前一个位置ListNode cur = findIndexSubOne(index);//4. 进行连接ListNode node = new ListNode(val);node.next = cur.next;cur.next = node;}private ListNode findIndexSubOne(int index) {int count = 0;ListNode cur = head;while (count != index-1) {cur = cur.next;count++;}return cur;}private void checkIndex(int index) throws IndexNotLegalException{if(index < 0 || index > size()) {throw new IndexNotLegalException("index不合法");}}@Overridepublic boolean contains(int key) {ListNode cur = head;while (cur != null) {if(cur.val == key) {return true;}cur = cur.next;}return false;}@Overridepublic void remove(int key) {if(head == null) {return;}if(head.val == key) {head = head.next;return;}ListNode cur = head;while (cur.next != null) {if(cur.next.val == key) {ListNode del = cur.next;cur.next = del.next;return;}cur = cur.next;}}@Overridepublic void removeAllKey(int key) {//1. 判空if(this.head == null) {return;}//2. 定义prev 和 curListNode prev = head;ListNode cur = head.next;//3.开始判断并且删除while(cur != null) {if(cur.val == key) {prev.next = cur.next;}else {prev = cur;}cur = cur.next;}//4.处理头节点if(head.val == key) {head = head.next;}}@Overridepublic int size(){int count = 0;ListNode cur = head;while (cur != null) {count++;cur = cur.next;}return count;}@Overridepublic void clear() {//head = null;ListNode cur = head;while (cur != null) {ListNode curN = cur.next;//cur.val = null;cur.next = null;cur = curN;}head = null;}@Overridepublic void display() {ListNode cur = head;while (cur != null) {System.out.print(cur.val+" ");cur = cur.next;}System.out.println();}
}//自定义异常类
public class IndexNotLegalException extends RuntimeException{public IndexNotLegalException() {}public IndexNotLegalException(String msg) {super(msg);}
}

3.2 无头双向非循环链表

3.2.1 节点结构

class ListNode {public int val;public ListNode prev;//前驱public ListNode next;//后继public ListNode(int val) {this.val = val;}}

3.2.2 方法接口

public interface IMyLinkedList {
//头插法
public void addFirst(int data);
//尾插法
public void addLast(int data);
//任意位置插入,第一个数据节点为0号下标
public void addIndex(int index,int data);
//查找是否包含关键字key是否在单链表当中
public boolean contains(int key);
//删除第一次出现关键字为key的节点
public void remove(int key);
//删除所有值为key的节点
public void removeAllKey(int key);
//得到单链表的长度
public int size();
public void display();
public void clear();
}

3.2.3 功能实现

public class MyLinkedList implements IMyLinkedList {public ListNode head;//标志头节点public ListNode last;//标志尾结点//头插法@Overridepublic void addFirst(int data){ListNode node = new ListNode(data);if(head == null) {//是不是第一次插入节点head = last = node;}else {node.next = head;head.prev = node;head = node;}}//尾插法@Overridepublic void addLast(int data){ListNode node = new ListNode(data);if(head == null) {//是不是第一次插入节点head = last = node;}else {last.next = node;node.prev = last;last = last.next;}}//任意位置插入,第一个数据节点为0号下标@Overridepublic void addIndex(int index,int data){try {checkIndex(index);}catch (IndexNotLegalException e) {e.printStackTrace();}if(index == 0) {addFirst(data);return;}if(index == size()) {addLast(data);return;}//1. 找到index位置ListNode cur = findIndex(index);ListNode node = new ListNode(data);//2、开始绑定节点node.next = cur;cur.prev.next = node;node.prev = cur.prev;cur.prev = node;}private ListNode findIndex(int index) {ListNode cur = head;while (index != 0) {cur = cur.next;index--;}return cur;}private void checkIndex(int index) {if(index < 0 || index > size()) {throw new IndexNotLegalException("双向链表插入index位置不合法: "+index);}}//查找是否包含关键字key是否在单链表当中@Overridepublic boolean contains(int key){ListNode cur = head;while (cur != null) {if(cur.val == key) {return true;}cur = cur.next;}return false;}//删除第一次出现关键字为key的节点@Overridepublic void remove(int key){ListNode cur = head;while (cur != null) {if(cur.val == key) {//开始删除 处理头节点if(cur == head) {head = head.next;if(head != null) {head.prev = null;}else {last = null;}}else {cur.prev.next = cur.next;if(cur.next == null) {//处理尾巴节点last = last.prev;}else {cur.next.prev = cur.prev;}}return;//删完一个就走}cur = cur.next;}}//删除所有值为key的节点@Overridepublic void removeAllKey(int key){ListNode cur = head;while (cur != null) {if(cur.val == key) {//开始删除 处理头节点if(cur == head) {head = head.next;if(head != null) {head.prev = null;}else {//head == null 证明只有1个节点last = null;}}else {cur.prev.next = cur.next;if(cur.next == null) {//处理尾巴节点last = last.prev;}else {cur.next.prev = cur.prev;}}}cur = cur.next;}}//得到双向链表的长度@Overridepublic int size(){int count = 0;ListNode cur = head;while (cur != null) {count++;cur = cur.next;}return count;}@Overridepublic void display(){ListNode cur = head;while (cur != null) {System.out.print(cur.val+" ");cur = cur.next;}System.out.println();}@Overridepublic void clear(){ListNode cur = head;while (cur != null) {ListNode curN = cur.next;//cur.val = null;cur.prev = null;cur.next = null;cur = curN;}head = last = null;}
}
//自定义异常类
public class IndexNotLegalException extends RuntimeException{public IndexNotLegalException() {}public IndexNotLegalException(String msg) {super(msg);}
}

4.LinkedList

4.1 概念

   LinkedList 的底层是双向链表结构 ( 链表后面介绍 ) ,由于链表没有将元素存储在连续的空间中,元素存储在单独的节点中,然后通过引用将节点连接起来了,因此在在任意位置插入或者删除元素时,不需要搬移元素,效率比较高。
注意:
1. LinkedList 实现了 List 接口
2. LinkedList 的底层使用了双向链表
3. LinkedList 没有实现 RandomAccess 接口,因此 LinkedList 不支持随机访问
4. LinkedList 的任意位置插入和删除元素时效率比较高,时间复杂度为 O(1)
5. LinkedList 比较适合任意位置插入的场景

4.2 使用

4.2.1 构造方法

方法说明
LinkedList()
无参构造
public LinkedList(Collection<? extends E> c)使用其他集合容器中元素构造List

代码示例:

public static void main(String[] args) {// 构造一个空的LinkedListList<String> list1 = new LinkedList<>();list1.add("sas");list1.add("asd");list1.add("Jsd");System.out.print("list1: ");for(int i = 0; i < list1.size();i++){System.out.print(list1.get(i)+" ");}System.out.println();System.out.print("list2: ");List<String> list2 = new LinkedList<>(list1);for(int i = 0; i < list2.size();i++){System.out.print(list2.get(i)+" ");}}

运行结果如下:

4.2.2 其他常用方法

方法解释
boolean add( E e)
尾插 e
void add(int index, E element)
e 插入到 index 位置
boolean addAll(Collection<? extends E> c)
尾插 c 中的元素
E remove(int index)
删除 index 位置元素
boolean remove(Object o)
删除遇到的第一个 o
E get(int index)
获取下标 index 位置元素
E set(int index, E element)
将下标 index 位置元素设置为 element
void clear()
清空
boolean contains(Object o)
判断 o 是否在线性表中
int indexOf(Object o)
返回第一个 o 所在下标
int lastIndexOf(Object o)
返回最后一个 o 的下标
List<E> subList(int fromIndex, int toIndex)截取部分list

代码示例:

public static void main(String[] args) {LinkedList<Integer> list = new LinkedList<>();list.add(1); // add(elem): 表示尾插list.add(2);list.add(3);list.add(4);list.add(5);list.add(6);list.add(7);System.out.println(list.size());System.out.println(list);// 在起始位置插入0list.add(0, 0); // add(index, elem): 在index位置插入元素elemSystem.out.println(list);list.remove(); // remove(): 删除第一个元素,内部调用的是removeFirst()list.removeFirst(); // removeFirst(): 删除第一个元素list.removeLast(); // removeLast(): 删除最后元素list.remove(1); // remove(index): 删除index位置的元素System.out.println(list);// contains(elem): 检测elem元素是否存在,如果存在返回true,否则返回falseif(!list.contains(1)){list.add(0, 1);}list.add(1);System.out.println(list);System.out.println(list.indexOf(1)); // indexOf(elem): 从前往后找到第一个elem的位置System.out.println(list.lastIndexOf(1)); // lastIndexOf(elem): 从后往前找第一个1的位置int elem = list.get(0); // get(index): 获取指定位置元素list.set(0, 100); // set(index, elem): 将index位置的元素设置为elemSystem.out.println(list);// subList(from, to): 用list中[from, to)之间的元素构造一个新的LinkedList返回List<Integer> copy = list.subList(0, 3);System.out.println(list);System.out.println(copy);list.clear(); // 将list中元素清空System.out.println(list.size());
}

运行结果如下:

4.3 遍历

我们之前常用的遍历方式有for循环、foreach循环和while循环等来进行遍历,LinkedList除了使用这些外, 还可以使用迭代器进行遍历。

代码示例:

public static void main(String[] args) {LinkedList<Integer> list = new LinkedList<>();list.add(1); // add(elem): 表示尾插list.add(2);list.add(3);list.add(4);list.add(5);list.add(6);list.add(7);// 使用迭代器遍历---正向遍历ListIterator<Integer> it = list.listIterator();while(it.hasNext()){System.out.print(it.next()+ " ");}System.out.println();
// 使用反向迭代器---反向遍历ListIterator<Integer> rit = list.listIterator(list.size());while (rit.hasPrevious()){System.out.print(rit.previous() +" ");}System.out.println();
}

运行结果如下:

5.ArrayListLinkedList的区别

不同点
ArrayListLinkedList
存储空间上物理上一定连续逻辑上连续,但物理上不一定连续
随机访问
支持O(1)不支持:O(N)
头插
需要搬移元素,效率低 O(N)
只需修改引用的指向,时间复杂度为O(1)
插入
空间不够时需要扩容没有容量的概念
应用场景
元素高效存储+频繁访问任意位置插入和删除频繁

本文是作者学习后的总结,如果有什么不恰当的地方,欢迎大佬指正!!!

相关文章:

数据结构(Java)——链表

1.概念及结构 链表是一种 物理存储结构上非连续 存储结构&#xff0c;数据元素的 逻辑顺序 是通过链表中的 引用链接 次序实现的 。 2.分类 链表的结构非常多样&#xff0c;以下情况组合起来就有 8 种链表结构&#xff1a; &#xff08;1&#xff09;单向或者双向 &#xff08;…...

变量与数据类型 - 整型、浮点型、字符型等

引言 在编程中&#xff0c;变量和数据类型是基础中的基础。理解它们如何工作以及如何正确使用它们对于编写高效且无误的代码至关重要。本文将详细介绍 C 中的几种基本数据类型&#xff1a;整型、浮点型、字符型等&#xff0c;并通过实例帮助读者更好地理解和掌握这些概念。 一…...

MacOS安装Xcode(非App Store)

文章目录 访问官网资源页面 访问官网资源页面 直接访问官网的历史版本下载资源页面地址&#xff1a;https://developer.apple.com/download/more/完成APP ID的登陆&#xff0c;直接找到需要的软件下载即可 解压后&#xff0c;安装将xcode.app移动到应用程序文件夹。...

运行Zr.Admin项目(后端)

1.下载Zr.Admin代码压缩包 https://codeload.github.com/izhaorui/Zr.Admin.NET/zip/refs/heads/main 2.打开项目 我这里装的是VS2022社区版 进入根目录&#xff0c;双击ZRAdmin.sln打开项目 3.安装.net7运行时 我当时下载的代码版本是.net7的 点击安装 点击安装&#xff0…...

Ubuntu24.04最新版本安装详细教程

Ubuntu 24.04 LTS发布说明 推荐的系统配置要求&#xff1a; 双核2 GHz处理器或更高 4 GB系统内存 25 GB磁盘存储空间 可访问的互联网 光驱或USB安装介质 Ubuntu 24.04官方下载网址&#xff1a;https://cn.ubuntu.com/download/desktop 04. Ubuntu 22.04(创建虚拟机方式一) 4…...

js版本之ES6特性简述【Proxy、Reflect、Iterator、Generator】(五)

目录 Proxy Reflect 静态方法 部分实例 Iterator 实际开发迭代器的使用实例 迭代器&#xff08;Iterator&#xff09;应用 Generator Proxy Proxy 是 ES6 中新增的对象 Proxy 是JavaScript中的内置对象&#xff0c;它提供了一种机制&#xff0c;可以拦截并自定义各种…...

CSS实现一个自定义的滚动条

要使用CSS创建一个自定义的滚动条&#xff0c;你可以使用伪元素和CSS的伪类来控制滚动条的外观和行为。以下是一个简单的例子&#xff0c;展示如何为任何HTML元素添加一个自定义的滚动条样式&#xff1a; <!DOCTYPE html> <html lang"en"> <head> …...

CKA认证 | Day8 K8s安全

第八章 Kubernetes安全 1、Kubernetes RBAC授权 Kubernetes 基于角色的访问控制&#xff08;Role-Based Access Control, RBAC&#xff09; 是一种强大的权限管理机制&#xff0c;用于控制用户、用户组、服务账户对 Kubernetes 集群资源的访问。通过 RBAC&#xff0c;可以细…...

深度分析java 使用 proguard 如何解析混淆后的堆栈

经过proguard混淆过后&#xff0c;发生异常时堆栈也进行了混淆&#xff0c;那么如果获取的原始的堆栈呢&#xff1f;我们下面来看下 使用proguard 根据mapping文件直接解析 import proguard.obfuscate.MappingReader; import proguard.retrace.FrameInfo; import proguard.re…...

bash 中 ${-#*i} 是什么意思?

-------------------------------------------------- author: hjjdebug date: 2024年 12月 25日 星期三 17:43:45 CST description: bash 中 ${-#*i} 是什么意思? -------------------------------------------------- 在centos 的 /etc/profile 中有这样的语句 for i in /…...

什么是Top-p采样与Top-k采样?大模型推理时如何同时设置?解析Transformers库源代码

什么是Top-p采样与Top-k采样&#xff1f;大模型推理时如何同时设置&#xff1f; 在自然语言生成&#xff08;NLG&#xff09;和大规模语言模型推理中&#xff0c;Top-k采样 和 Top-p采样 是两种常用的解码策略&#xff0c;用于控制生成文本的多样性和质量。它们在生成过程中对…...

java队列--数据结构

文章目录 前言本文源代码网址&#xff1a;https://gitee.com/zfranklin/java/tree/master/dataStructure/src/com/njupt/queue队列的性质数组队列成员变量方法 链表栈成员变量方法 总结 前言 顺序表和链表两种存储方式实现数据结构–队列。 本文源代码网址&#xff1a;https:/…...

【WebSocket】tomcat内部处理websocket的过程

websocket请求格式 浏览器请求 GET /webfin/websocket/ HTTP/1.1。 Host: localhost。 Upgrade: websocket。 Connection: Upgrade。 Sec-WebSocket-Key: xqBt3ImNzJbYqRINxEFlkg。 Origin: http://服务器地址。 Sec-WebSocket-Version: 13。 服务器响应 HTTP/1.1 101 Swi…...

【踩坑/Linux】Vmware中的Ubuntu虚拟机无法访问互联网

Vmware中的Ubuntu虚拟机无法访问互联网 首先前提是我的系统是Ubuntu 16.04系统&#xff0c;vmware workstation选择的是NAT模式&#xff0c;虚拟机内连不上网络 ping www.baidu.com ping: unknown host www.baidu.com首先检查 DNS 解析服务&#xff1a;在虚拟机中打开命令提示…...

overleaf中的includegraphics设置图片缩放,居中显示

overleaf中的includegraphics设置图片缩放,居中显示 \includegraphics[width=0.5\textwidth]{example.jpg} \centering 在使用 \includegraphics 命令插入图片时,可以通过设置其参数来缩小图片的显示尺寸,以下是几种常见的方法: 设置宽度或高度 按比例缩小宽度:可以使用…...

IPv6的地址类型

IPv6地址总长度为128bit&#xff0c;被分为8组&#xff0c;每组为4个十六进制数&#xff0c;用冒号分隔&#xff1a; 例如&#xff1a;FC00:0123:4567:8901:ABFD:0987:0000:0023 可缩写为&#xff1a;FC00:0123:4567:8901:ABFD:0987::23 IPv6中取消了v4中的广播&#xff0c;新…...

Elasticsearch:analyzer(分析器)

一、概述 可用于将字符串字段转换为单独的术语&#xff1a; 添加到倒排索引中&#xff0c;以便文档可搜索。级查询&#xff08;如 生成搜索词的 match查询&#xff09;使用。 分析器分为内置分析器和自定义的分析器&#xff0c;它们都是由若干个字符过滤器&#xff08;chara…...

【工作感悟】

1、不返工 - 复述任务 避免返工的前提是先把事情弄清楚&#xff0c;怎么弄清楚&#xff0c;要问到每个细节&#xff0c;怎么确保每个细节都问到了&#xff0c;把要做的事情复述一遍&#xff0c;有必要的话再讲述一下自己打算怎么做&#xff1b;及时对齐工作进度可以避免出错 …...

事件(event) SystemVerilog

1.定义 在数字逻辑仿真中&#xff0c;事件&#xff08;event&#xff09; 是一种机制&#xff0c;用于触发模型中的更新或计算。这种机制是仿真器用来追踪信号的变化以及调度进程执行的核心。 2.分类 事件可以分为以下两种类型&#xff1a; 更新事件&#xff08;Update Even…...

【MySQL学习笔记】关于索引

文章目录 【MySQL学习笔记】关于索引1.索引数据结构2.索引存储3.联合索引3.1 联合索引的b树结构3.2 索引覆盖&#xff1f;回表&#xff1f;3.3 联合索引最左匹配原则3.5 索引下推 4.索引失效 【MySQL学习笔记】关于索引 1.索引数据结构 索引是一种能提高查询速度的数据结构。…...

SkyWalking 10.2.0 SWCK 配置过程

SkyWalking 10.2.0 & SWCK 配置过程 skywalking oap-server & ui 使用Docker安装在K8S集群以外&#xff0c;K8S集群中的微服务使用initContainer按命名空间将skywalking-java-agent注入到业务容器中。 SWCK有整套的解决方案&#xff0c;全安装在K8S群集中。 具体可参…...

RocketMQ延迟消息机制

两种延迟消息 RocketMQ中提供了两种延迟消息机制 指定固定的延迟级别 通过在Message中设定一个MessageDelayLevel参数&#xff0c;对应18个预设的延迟级别指定时间点的延迟级别 通过在Message中设定一个DeliverTimeMS指定一个Long类型表示的具体时间点。到了时间点后&#xf…...

Golang 面试经典题:map 的 key 可以是什么类型?哪些不可以?

Golang 面试经典题&#xff1a;map 的 key 可以是什么类型&#xff1f;哪些不可以&#xff1f; 在 Golang 的面试中&#xff0c;map 类型的使用是一个常见的考点&#xff0c;其中对 key 类型的合法性 是一道常被提及的基础却很容易被忽视的问题。本文将带你深入理解 Golang 中…...

【WiFi帧结构】

文章目录 帧结构MAC头部管理帧 帧结构 Wi-Fi的帧分为三部分组成&#xff1a;MAC头部frame bodyFCS&#xff0c;其中MAC是固定格式的&#xff0c;frame body是可变长度。 MAC头部有frame control&#xff0c;duration&#xff0c;address1&#xff0c;address2&#xff0c;addre…...

在HarmonyOS ArkTS ArkUI-X 5.0及以上版本中,手势开发全攻略:

在 HarmonyOS 应用开发中&#xff0c;手势交互是连接用户与设备的核心纽带。ArkTS 框架提供了丰富的手势处理能力&#xff0c;既支持点击、长按、拖拽等基础单一手势的精细控制&#xff0c;也能通过多种绑定策略解决父子组件的手势竞争问题。本文将结合官方开发文档&#xff0c…...

Swagger和OpenApi的前世今生

Swagger与OpenAPI的关系演进是API标准化进程中的重要篇章&#xff0c;二者共同塑造了现代RESTful API的开发范式。 本期就扒一扒其技术演进的关键节点与核心逻辑&#xff1a; &#x1f504; 一、起源与初创期&#xff1a;Swagger的诞生&#xff08;2010-2014&#xff09; 核心…...

如何在网页里填写 PDF 表格?

有时候&#xff0c;你可能希望用户能在你的网站上填写 PDF 表单。然而&#xff0c;这件事并不简单&#xff0c;因为 PDF 并不是一种原生的网页格式。虽然浏览器可以显示 PDF 文件&#xff0c;但原生并不支持编辑或填写它们。更糟的是&#xff0c;如果你想收集表单数据&#xff…...

以光量子为例,详解量子获取方式

光量子技术获取量子比特可在室温下进行。该方式有望通过与名为硅光子学&#xff08;silicon photonics&#xff09;的光波导&#xff08;optical waveguide&#xff09;芯片制造技术和光纤等光通信技术相结合来实现量子计算机。量子力学中&#xff0c;光既是波又是粒子。光子本…...

七、数据库的完整性

七、数据库的完整性 主要内容 7.1 数据库的完整性概述 7.2 实体完整性 7.3 参照完整性 7.4 用户定义的完整性 7.5 触发器 7.6 SQL Server中数据库完整性的实现 7.7 小结 7.1 数据库的完整性概述 数据库完整性的含义 正确性 指数据的合法性 有效性 指数据是否属于所定…...

纯 Java 项目(非 SpringBoot)集成 Mybatis-Plus 和 Mybatis-Plus-Join

纯 Java 项目&#xff08;非 SpringBoot&#xff09;集成 Mybatis-Plus 和 Mybatis-Plus-Join 1、依赖1.1、依赖版本1.2、pom.xml 2、代码2.1、SqlSession 构造器2.2、MybatisPlus代码生成器2.3、获取 config.yml 配置2.3.1、config.yml2.3.2、项目配置类 2.4、ftl 模板2.4.1、…...