JavaDS —— 单链表 与 LinkedList

顺序表和链表区别

ArrayList :
底层使用连续的空间,可以随机访问某下标的元素,时间复杂度为O(1)
但是在插入和删除操作的时候,需要将该位置的后序元素整体往前或者向后移动,时间复杂度为O(N)
增容需要申请新空间,有时候需要拷贝数据释放旧空间,这会有不小的消耗
顺序表的增容一般是2倍增加的,势必会有一定的kong’jian浪费,例如当前容量为100时,需要扩容的话,就是将容量增加到200,如果只是再插入几个数据,就一定会浪费九十几的空间。

既然如此,我们就会思考如何减少空间的浪费,这时候链表就登场了,下面是单链表的示意图:
在这里插入图片描述
链表由两个部分组成,一个是数据域,一个是指针域,数据域是用来存放数据的,指针域是用来存放下一个或者前一个的引用的,这样就把数据给串联起来了,大家也就不难发现,链表的优点就是用多少空间就申请多少空间,做到空间不浪费,并且在下面的内容,你还会感受到链表的插入删除操作效率很高。

链表的分类

链表有8大类,带头和不带头,单向还是双向,循环还是不循环,2^3 = 8种

带头和不带头是指链表有没有一个哨兵节点,就是只是充当头结点的作用,不存放任何有效的数据。
上面的图片就是不带头的,下面的是带头的:
在这里插入图片描述

单向和双向是指:链表的节点是只指向后一个节点的话就是单向的,如果链表的节点即指向前一个结点又指向后一个节点的话就是双向的。
在这里插入图片描述

循环和不循环是指链表是否头尾相连,如果头尾相连就是循环的,否则就是不循环的:
在这里插入图片描述
在这里插入图片描述

实现单链表

下面是自己写的IList接口,会被单链表拓展:

public interface IList {//头插法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();
}

单链表的节点需要一个数据域和一个指针域,我们先来写一个静态内部类来构造节点类:

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

除此之外,我们还需要一个头指针来指向第一个节点:

    public ListNode head;

打印

循环遍历链表,打印每一个节点的数据,这个方法有利于我们的测试:

    @Overridepublic void display() {ListNode cur = head;while(cur != null) {System.out.print(cur.val + " ");cur = cur.next;}System.out.println();}

头插

在单链表的头部插入一个数据,我们需要将新头节点的next指向原先头部的节点,然后改变head的指向。

    @Overridepublic void addFirst(int data) {ListNode node = new ListNode(data);node.next = head;head = node;}

尾插

循环遍历单链表找到尾节点,然后改变尾节点的指向即可。

这里要注意如果head为空的时候,直接赋值就可以了,不能直接使用null,会报空指针异常,所以在循环前面加多一个判断条件即可。

    @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 int size() {ListNode cur = head;int count = 0;while(cur != null) {cur = cur.next;count++;}return count;}

指定位置插入

先判断指定的位置有没有越界,和之前的顺序表是一样的,这里不赘述:

public class IndexException extends RuntimeException{public IndexException(String message) {super(message);}
}
    private void checkIndexInAdd(int index) throws IndexException {if(index < 0 || index > size()) {throw new IndexException("下标范围不合法!");}}

我们要先找到index前一个结点,因为这个插入操作是对三个节点进行操作的,首先先把index的引用放入新结节点的next中,然后再把index前一个结点的next改成新结点的引用,这是一般情况,如果index == 0的话就是头插操作,为什么要做一个判断,因为我们得出的一般规律最后是cur.next = node,这是建立在新结点前面一定有结点的情况下,但是如果是头插的话就不符合了,所以头插需要单独说明。

    @Overridepublic void addIndex(int index, int data) {try{checkIndexInAdd(index);if(index == 0) {addFirst(data);return;}//找到index前一个的节点ListNode cur = head;for (int i = 0; i < index - 1; i++) {cur = cur.next;}ListNode node = new ListNode(data);node.next = cur.next;cur.next = node;} catch (IndexException e) {System.out.println("index 不合法!");e.printStackTrace();}}

对于插入操作,我们要先处理后面的结点,避免后面的结点丢失。

contains

是否包含某个元素,直接遍历循环即可:

    @Overridepublic boolean contains(int key) {ListNode cur = head;while(cur != null) {if(cur.val == key) {return true;}cur = cur.next;}return false;}

删除第一次出现的key

删除某个结点的时候,由于这是单链表,所以我们最好事先拿到删除节点的前一个结点,然后我们要考虑一些特殊的情况,如果这个链表为空就不需要删除,如果要删除的结点就是头结点,那么我们就需要改变头指针的指向,最后就是一般情况下,我们直接修改删除结点的前一个结点的 next 域 就可以了。

    private ListNode findFrontNodeOfKey(int key) {ListNode cur = head;while(cur != null) {if(cur.next.val == key) {return cur;}cur = cur.next;}return null;}@Overridepublic void remove(int key) {//空链表if(head == null) {return;}//头删if(head.val == key) {head = head.next;return;}ListNode prev = findFrontNodeOfKey(key);if(prev == null) {return;//不存在key}ListNode del = prev.next;prev.next = del.next;}

删除所有出现的key

我们使用两个指针,一个从头结点开始,另一个从头结点的下一个结点开始遍历链表,当第二个指针遇到要删除的结点时,配合第一个指针完成此工作,然后prev不变,cur继续移动,如果没有遇到删除的结点,两个指针是一起继续向后运动。

要注意如果链表为空的话就直接return ,避免发生空指针异常

这时候大家一定知道还差一个结点没有判断,就是第一个结点,所以我们最后还有判断一下头结点。

    @Overridepublic void removeAllKey(int key) {if(head == null) {return;}ListNode prev = head;ListNode cur = head.next;while(cur != null) {if(cur.val == key) {prev.next = cur.next;} else {prev = cur;}cur = cur.next;}if(head.val == key) {head = head.next;}}

clear

清空链表,你可以直接把头指针赋值为null,由于链表没有被引用,会被JVM自动回收,

    @Overridepublic void clear() {ListNode cur = head;while(cur != null) {ListNode tmp = cur.next;cur.next = null;cur = tmp;}head = null;}

模拟实现LinkedList

LinkedList 是不带头,双向的,循环的链表

构建节点

双向的意味着有两个节点,一个指向前一个结点,一个指向后一个结点,还有一个头指针指向头节点,一个尾指针指向尾节点。

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

打印

    public void display() {ListNode cur = head;while(cur != null) {System.out.print(cur.val + " ");cur = cur.next;}System.out.println();}

头插

要注意如果头指针为null,意味着链表为空,尾指针自然也是null,链表为空的话,插入新数据要改变头尾指针的指向。
正常情况下是链表至少有一个结点,改变原先头节点的prev指向,新结点的next也要改变。

    public void addFirst(int data) {ListNode node = new ListNode(data);if(head == null) {head = last = node;return;}head.prev = node;node.next = head;head = node;}

尾插

注意如果尾指针为null时,说明链表为空。和上面的头插一样,要单独讨论说明。

    public void addLast(int data) {ListNode node = new ListNode(data);if(last == null) {head = last = node;}last.next = node;node.prev = last;last = node;}

求结点个数

    public int size() {ListNode cur = head;int count = 0;while(cur != null) {count++;cur = cur.next;}return count;}

指定位置插入

先判断index是否合法,不合法还是和之前一样抛异常。

public class IndexOutOfBoundException extends RuntimeException {public IndexOutOfBoundException() {super();}public IndexOutOfBoundException(String message) {super(message);}
}
    private void checkIndexInAdd(int index) throws IndexOutOfBoundException{if(index < 0 || index > size()) {throw new IndexOutOfBoundException("下标越界!!!");}}

我们先讨论一般情况,如果待插入的结点正好前后都是由结点的,那么我们需要修改三个结点的指针:
cur.prev.next = node;
node.prev = cur.prev;
node.next = cur;
cur.prev = node;
在这里插入图片描述
现在来注意特殊情况,如果index == 0时,就是头插,不管怎么样,头插就一定要改变头指针,所以要单独讨论。换一种思路,如果是头插的话,cur.prev = null ,所以 cur.prev.next 一定会报空指针异常。所以头插还是要单独讨论。
那如果是尾插呢?尾插意味着 cur == null ,还是和头插思考方式一样,尾节点一定要改变所以要单独讨论,还有cur.prev 一定会报空指针异常。

    public void addIndex(int index,int data) {try {checkIndexInAdd(index);if(index == 0) {addFirst(data);return;}ListNode node = new ListNode(data);ListNode cur = head;for (int i = 0; i < index; i++) {cur = cur.next;}if(cur == null) {addLast(data);return;}cur.prev.next = node;node.prev = cur.prev;node.next = cur;cur.prev = node;} catch (IndexOutOfBoundException e) {e.printStackTrace();}}

remove

删除第一次出现关键字为key的节点

如果链表为空不能继续删除操作
如果删除头节点,就必须改变头指针,所以要单独说明
一般情况下,需要变动cur前后结点,自然会想到:cur.prev.next = cur.next; cur.next.prev = cur.prev;
那如果是尾删呢?上面两行代码只有前面一行还能继续用,由于是尾删,尾节点就要发生改变,所以last = cur.prev;

public void remove(int key) {if(head == null) {return;}if(head.val == key) {head = head.next;if(head != null) {head.prev = null;}return;}ListNode cur = head.next;while(cur != null) {if(cur.val == key) {cur.prev.next = cur.next;if(cur.next == null) {last = cur.prev;} else {cur.next.prev = cur.prev;}return;}cur = cur.next;}}

removeAllKey

删除所有值为key的节点

删除所有的key,上面我们写了删除第一次出现key的结点,这里把代码直接帮过来,删掉return就可以继续用,但是一定是对的吗?
前面的链表判空直接返回没有问题,但是头删的话就有问题了,假设头节点是你要删除的结点就意味着头指针要发生改变,那如果新的头节点又要发生改变呢?这里我们选择尽量不改变我们的祖传代码,把头删放在最后面去做即可。

    public void removeAllKey(int key) {if(head == null) {return;}ListNode cur = head.next;while(cur != null) {if(cur.val == key) {cur.prev.next = cur.next;if(cur.next == null) {last = cur.prev;} else {cur.next.prev = cur.prev;}}cur = cur.next;}if(head.val == key) {head = head.next;if(head != null) {head.prev = null;}}}

contains

是否包含key这个元素

    public boolean contains(int key) {ListNode cur = head;while(cur != null) {if(cur.val == key) {return true;}cur = cur.next;}return false;}

clear

你可以直接将head 和last都置为null,这样链表就会被JVM自动回收。
这里模仿源码的写法,源码是一个一个结点都置为null,最后头尾指针再置为null

    public void clear() {ListNode cur = head;while(cur != null) {ListNode tmp = cur.next;cur.prev = null;cur.next = null;cur = tmp;}head = last = null;}

LinkedList 使用

Java集合类中给我们提供了LinkedList,这是一个无头双向循环链表,我们来看一下它里面的方法,方法名字和上面我们模拟实现的差不多。
在这里插入图片描述

LinkedList 的构造方法

在这里插入图片描述
第二个构造方法是可以传入一个对象,和之前ArrayList表示二维数组是一个意思。

LinkedList 的方法

在这里插入图片描述

要注意LinkedList和ArrayList 的subList是一样的原理,截取的list还是原来的对象list,只是范围不同,并没有创建新的对象。

add(默认尾插)

注意LinkedList的add方默认是尾插

    public static void main(String[] args) {LinkedList<Integer> list = new LinkedList<>();list.add(1);list.add(2);list.add(3);System.out.println(list);}

在这里插入图片描述

addAll

尾插一个对象

    public static void main(String[] args) {LinkedList<Integer> list = new LinkedList<>();list.add(1);list.add(2);list.add(3);System.out.println(list);ArrayList<Integer> list1 = new ArrayList<>();list1.add(10);list1.add(20);list.addAll(list1);System.out.println(list);}

在这里插入图片描述

遍历链表

直接打印

LinkedList也是重写了toString 方法

    public static void main(String[] args) {LinkedList<Integer> list = new LinkedList<>();list.add(1);list.add(2);list.add(3);System.out.println(list);}

在这里插入图片描述

for 循环

    public static void main(String[] args) {LinkedList<Integer> list = new LinkedList<>();list.add(1);list.add(2);list.add(3);int size = list.size();for (int i = 0; i < size; i++) {System.out.print(list.get(i) + " ");}System.out.println();}

在这里插入图片描述

for each

    public static void main(String[] args) {LinkedList<Integer> list = new LinkedList<>();list.add(1);list.add(2);list.add(3);for(int x : list) {System.out.print(x + " ");}System.out.println();}

在这里插入图片描述

迭代器

在这里插入图片描述
ListIterator 是继承 Iterator 的,这两个都可以来遍历链表打印数据。

迭代器的使用可以类似下面的图:
在这里插入图片描述

while(it.hasNext())hasNext表示是否由下一个数据,通过next()方法打印下一个数据,之后 it 一直向后移动。

Iterator
    public static void main(String[] args) {LinkedList<Integer> list = new LinkedList<>();list.add(1);list.add(2);list.add(3);System.out.println("===== Iterator ====");Iterator<Integer> it = list.iterator();while (it.hasNext()) {System.out.print(it.next()+" ");}System.out.println();}

在这里插入图片描述

ListIterator
    public static void main(String[] args) {LinkedList<Integer> list = new LinkedList<>();list.add(1);list.add(2);list.add(3);ListIterator<Integer> lit =  list.listIterator();while (lit.hasNext()) {System.out.print(lit.next()+" ");}System.out.println();}

在这里插入图片描述

ListIterator(逆向遍历)
    public static void main(String[] args) {LinkedList<Integer> list = new LinkedList<>();list.add(1);list.add(2);list.add(3);System.out.println("===== ListIterator ====");ListIterator<Integer> lit2 =  list.listIterator(list.size());while (lit2.hasPrevious()) {System.out.print(lit2.previous()+" ");}System.out.println();}

在这里插入图片描述

listIterator(int n) ,可以指定从哪个下标开始遍历链表

ArrrayList 和 LinkedLisrt 的总结

在这里插入图片描述

配套练习:
http://t.csdnimg.cn/nmObG

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

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

相关文章

【银河麒麟服务器操作系统】系统夯死分析及处理建议

了解银河麒麟操作系统更多全新产品&#xff0c;请点击访问麒麟软件产品专区&#xff1a;https://product.kylinos.cn 服务器环境以及配置 【机型】物理机 处理器&#xff1a; Intel 内存&#xff1a; 512G 整机类型/架构&#xff1a; X86_64 【内核版本】 4.19.90-25…

【学习笔记】无人机(UAV)在3GPP系统中的增强支持(五)-同时支持无人机和eMBB用户数据传输的用例

引言 本文是3GPP TR 22.829 V17.1.0技术报告&#xff0c;专注于无人机&#xff08;UAV&#xff09;在3GPP系统中的增强支持。文章提出了多个无人机应用场景&#xff0c;分析了相应的能力要求&#xff0c;并建议了新的服务级别要求和关键性能指标&#xff08;KPIs&#xff09;。…

集成excel工具:自定义导入回调监听器、自定义类型转换器、web中的读

文章目录 I 封装导入导出1.1 定义工具类1.2 自定义读回调监听器: 回调业务层处理导入数据1.3 定义文件导入上下文1.4 定义回调协议II 自定义转换器2.1 自定义枚举转换器2.2 日期转换器2.3 时间、日期、月份之间的互转2.4 LongConverterIII web中的读3.1 使用默认回调监听器3.2…

防御第二次作业完成接口配置实验

一、实验括扑图 二、实验要求 1.防火墙向下使用子接口分别对应生产区和办公区 2.所有分区设备可以ping通网关 三、实验思路 1、配置各设备的IP地址 2、划分VLAN及VLAN的相关配置 3、配置路由及安全策略 四、实验步骤 1、配置PC跟Client还有server配置&#xff0…

【Js】导出 HTML 为 Word 文档

在 Web 开发中&#xff0c;有时我们希望用户能够将网页上的 HTML 内容保存为 Word 文档&#xff0c;以便更方便地分享和打印。 html样式 word文档 工具准备 1、 html-docx-js - npm html-docx-js是一个 JavaScript 库&#xff0c;用于将 HTML 内容转换为 Word 文档的格式。它…

五、 计算机网络(考点篇)

1 网络概述和模型 计算机网络是计算机技术与通信技术相结合的产物&#xff0c;它实现了远程通信、远程信息处理和资源共享。计算机网络的功能&#xff1a;数据通信、资源共享、管理集中化、实现分布式处理、负载均衡。 网络性能指标&#xff1a;速率、带宽(频带宽度或传送线路…

快速读出linux 内核中全局变量

查问题时发现全局变量能读出来会提高效率&#xff0c;于是考虑从怎么读出内核态的全局变量&#xff0c;脚本如下 f open("/proc/kcore", rb) f.seek(4) # skip magic assert f.read(1) b\x02 # 64 位def read_number(bytes):return int.from_bytes(bytes, little,…

debian 12 PXE Server 批量部署系统

pxe server 前言 PXE&#xff08;Preboot eXecution Environment&#xff0c;预启动执行环境&#xff09;是一种网络启动协议&#xff0c;允许计算机通过网络启动而不是使用本地硬盘。PXE服务器是实现这一功能的服务器&#xff0c;它提供了启动镜像和引导加载程序&#xff0c;…

QML 鼠标和键盘事件

学习目标&#xff1a;Qml 鼠标和键盘事件 学习内容 1、QML 鼠标事件处理QML 直接提供 MouseArea 来捕获鼠标事件&#xff0c;该操作必须配合Rectangle 获取指定区域内的鼠标事件, 2、QML 键盘事件处理&#xff0c;并且获取对OML直接通过键盘事件 Keys 监控键盘任意按键应的消…

Lottery 分布式抽奖(个人向记录总结)

1.搭建&#xff08;DDDRPC&#xff09;架构 DDD——微服务架构&#xff08;微服务是对系统拆分的方式&#xff09; &#xff08;Domain-Driven Design 领域驱动设计&#xff09; DDD与MVC同属微服务架构 是由Eric Evans最先提出&#xff0c;目的是对软件所涉及到的领域进行建…

智慧城市3d数据可视化系统提升信息汇报的时效和精准度

在信息大爆炸的时代&#xff0c;数据的力量无可估量。而如何将这些数据以直观、高效的方式呈现出来&#xff0c;成为了一个亟待解决的问题。为此&#xff0c;我们推出了全新的3D可视化数据大屏系统&#xff0c;让数据“跃然屏上”&#xff0c;助力您洞察先机&#xff0c;决胜千…

Python excel知识库批量模糊匹配的3种方法实例(fuzzywuzzy\Gensim)

前言 当然&#xff0c;基于排序的模糊匹配&#xff08;类似于Excel的VLOOKUP函数的模糊匹配模式&#xff09;也属于模糊匹配的范畴&#xff0c;但那种过于简单&#xff0c;不是本文讨论的范畴。 本文主要讨论的是以公司名称或地址为主的字符串的模糊匹配。 使用编辑距离算法进…

Python3.6.6 OpenCV 将视频中人物标记或者打马赛克或加图片并保存为不同格式

1、轻松识别视频人物并做出标记 需安装face_recongnition与dlib&#xff0c;过程有点困难&#xff0c;还请网上查找方法 import face_recognition import cv2 #镜像源 -i https://pypi.mirrors.ustc.edu.cn/simple # 加载视频 video_file E:\\videos\\1.mp4 video_capture …

浏览器开发者视角及CSS表达式选择元素

点击想要查看的接口&#xff0c;然后点击检查&#xff0c;便可以切换到该接口对应的html代码 如果F12不起作用的话&#xff0c;点击更多工具&#xff0c;然后选择开发者工具即可 ctrlF可以去查阅相关的CSS表达式选择元素 如果没有加#t1&#xff0c;那么表示的是选择所有的p 使用…

JS进阶-异常处理

学习目标&#xff1a; 掌握异常处理 学习内容&#xff1a; throw抛异常try/catch捕获异常debugger throw抛异常&#xff1a; 异常处理是预估代码执行过程中可能发生的错误&#xff0c;然后最大程度的避免错误的发生导致整个程序无法继续运行。 <title>throw抛异常</…

Go-知识测试-子测试

Go-知识测试-子测试 1. 介绍2. 例子3. 子测试命名规则4. 选择性执行5. 子测试并发6. testing.T.Run7. testing.T.Parallel8. 子测试适用于单元测试9. 子测试适用于性能测试10. 总结10.1 启动子测试 Run10.2 启动并发测试 Parallel 建议先看&#xff1a;https://blog.csdn.net/a…

基于大语言模型(LLM)的合成数据生成、策展和评估的综述

节前&#xff0c;我们星球组织了一场算法岗技术&面试讨论会&#xff0c;邀请了一些互联网大厂朋友、参加社招和校招面试的同学。 针对算法岗技术趋势、大模型落地项目经验分享、新手如何入门算法岗、该如何准备、面试常考点分享等热门话题进行了深入的讨论。 合集&#x…

JavaScript中的面向对象编程

OPP在JavaScript的表现方式&#xff1a;原型 传统的OPP&#xff1a;类 ● 对象&#xff08;实例&#xff09;由类实例化&#xff0c;类的功能类似于蓝图&#xff0c;通过蓝图来实现建筑&#xff08;实例&#xff09; ● 行为&#xff08;方法&#xff09;从类复制到所有实例 …

阿里ChatSDK使用,开箱即用聊天框

介绍&#xff1a; 效果&#xff1a;智能助理 ChatSDK&#xff0c;是在ChatUI的基础上&#xff0c;结合阿里云智能客服的最佳实践&#xff0c;沉淀和总结出来的一个开箱即用的&#xff0c;可快速搭建智能对话机器人的框架。它简单易上手&#xff0c;通过简单的配置就能搭建出对…

交换机和路由器的工作流程

1、交换机工作流程&#xff1a; 将接口中的电流识别为二进制&#xff0c;并转换成数据帧&#xff0c;交换机会记录学习该数据帧的源MAC地址&#xff0c;并将其端口关联起来记录在MAC地址表中。然后查看MAC地址表来查找目标MAC地址&#xff0c;会有一下一些情况&#xff1a; MA…