数据结构之LinkedList

系列文章目录

数据结构之ArrayList-CSDN博客


目录

系列文章目录

前言

一、模拟实现链表

1. 遍历链表

2. 插入节点

 3. 删除节点

4. 清空链表

二、链表的常见操作

1. 反转链表

2. 返回链表的中间节点

3. 链表倒数第 k 个节点

4. 合并两个有序链表

5. 分割链表

6. 判断链表是否回文

7. 找两个链表的第一个公共节点

8. 判断链表是否有环

9. 寻找链表入环的第一个节点

三、模拟实现双向链表

1. 遍历链表

2. 插入节点

3. 删除节点

4. 清空链表

四、ArrayList 和 LinkedList 的区别


前言

本文通过单链表的模拟实现,帮助了解单链表的底层原理,以及常见的链表的常用操作,比如反转链表,找链表的中间节点等。模拟实现双向链表,了解双向链表的底层原理,以及 ArrayList 和 LinkedList 的比较。


一、模拟实现链表

链表是物理存储结构上非连续,逻辑上连续的存储结构;每个节点都会保存下一个节点的哈希值,通过这个节点可以找到下一个节点;

链表的属性:用 head 表示链表的头节点;

public class MySingleList {static class ListNode{public int val;public ListNode next;public ListNode(int val){this.val = val;}}public ListNode head;// 链表的方法// ...
}

1. 遍历链表

以下方法都需要遍历一遍链表:

display(): void 打印节点信息;

size(): int 返回链表的长度;

contains(int key): boolean 判断链表中是否包含 key;

    // 打印所有节点信息public void display(){ListNode cur = head;while(cur != null){System.out.print(cur.val + " ");cur = cur.next;}}// 求链表的长度public int size(){ListNode cur = head;int count = 0;while(cur != null){count++;cur = cur.next;}return count;}// 查找关键字 key 是否在链表中public boolean contains(int key){ListNode cur = head;while(cur != null){if(cur.val == key){return true;}cur = cur.next;}return false;}

2. 插入节点

addFirst(int data): void 头插法,将节点插入到链表头节点的位置;

addLast(int data): void 尾插法,将节点插入到链表尾节点的位置,尾插的时候要注意,当链表没有节点,即 head == null,这时候要注意将要插入的节点设置为头节点;

findIndexPrev(int index): ListNode 找到 index 位置节点的前驱;

addIndex(int index, int data): void 在 index 位置插入节点;

插入之前需要先判断 index 位置是否合法;

如果合法再判断一下是否是头插,是否是尾插,因为这俩方法已经写好了,可以调用;

找到要插入节点的前驱,找到前驱之后进行插入;

    // 头插法public void addFirst(int data){ListNode node = new ListNode(data);node.next = head;head = node;}// 尾插法public void addLast(int data){ListNode node = new ListNode(data);ListNode cur = head;if(cur == null) {this.head = node;return;}while(cur.next != null){cur = cur.next;}cur.next = node;}// 在任意位置插入public void addIndex(int index, int data){if(index < 0 || index > size()){throw new PosOutOfBoundsException(index + "插入位置不合法");}if(index == 0){addFirst(data);return;}if(index == size()){addLast(data);return;}ListNode cur = findIndexPrev(index);ListNode node = new ListNode(data);node.next = cur.next;cur.next = node;}// 找到 index 下标的前一个节点private ListNode findIndexPrev(int index){ListNode cur = head;while(--index > 0){cur = cur.next;}return cur;}

 3. 删除节点

remove(int key): void 删除第一个值为 key  的节点;

如果链表为空则直接返回;

如果头节点为要删除的节点,直接删除;

如果要删除的节点不存在,抛异常;

如果要删除在后面,先找到要删除节点的前驱,再删除;

findPrev(int key): ListNode 找到值为 key 的节点的前驱,没有要删除的节点,返回 null;

removeAll(int key): void 删除所有值为 key 的节点;

如果链表为空,直接返回;

从头节点后面开始删除,找到要删除的节点和它的前驱,进行删除;

删除完成后,当前节点指针向后移动;

如果没有找到要删除的节点,前驱和当前节点指针都同步向后移动;

最后判断头节点,如果头节点也是要删除的节点,进行删除;

    // 删除节点public void remove(int key){if(head == null){return;}// 单独删除头节点if(head.val == key){head = head.next;return;}ListNode prev = findPrev(key);if(prev == null){throw new RuntimeException("要删除的节点不存在!");}ListNode del = prev.next;prev.next = del.next;}// 找到 data 节点的前驱private ListNode findPrev(int key){ListNode cur = head;while(cur.next != null){if(cur.next.val == key){return cur;}}return null;}// 删除所有值为 key 的节点public void removeAll(int key){if(head == null){return;}ListNode prev = head;ListNode cur = prev.next;while(cur != null){if(cur.val == key){prev.next = cur.next;cur = cur.next;}else{prev = cur;cur = cur.next;}}// 判断头结点if(head.val == key){head = head.next;}}

4. 清空链表

clear(): void 清空链表,只需要将头结点置空即可;

    // 清空链表public void clear(){this.head = null;}

二、链表的常见操作

1. 反转链表

reverseList(ListNode head): ListNode 反转链表;

如果链表为空,返回 null;

如果链表不为空,依次将 head 后面的元素进行头插;

    public ListNode reverseList(ListNode head) {if(head == null) return head;ListNode cur = head.next;head.next = null;while(cur != null){ListNode next = cur.next;cur.next = head;head = cur;cur = next;}return head;}

2. 返回链表的中间节点

middleNode(ListNode head): ListNode 返回链表的中间节点,如果链表是奇数个元素,返回中间节点,如果链表是偶数个元素,返回右中点节点;

定义快慢指针,快指针每次走两步,慢指针每次走一步,如果快指针走到最后一个位置或者空位置,返回慢指针指向的节点即可;

    public ListNode middleNode(ListNode head) {if(head == null){return head;}ListNode fast = head;ListNode slow = head;while(fast != null && fast.next != null){fast = fast.next;fast = fast.next;slow = slow.next;}return slow;}

3. 链表倒数第 k 个节点

findKthtoTail(ListNode head, int k): ListNode 找倒数第 k 个节点

先判断 head 是否为空,如果 head 为空,返回 null;

再判断 k 的值是否合法,如果不合法,返回 null;

定义快慢指针 fast 和 slow,先让 fast 走 k - 1步,再让 fast 和 slow 同时走, fast 走到尾巴节点的时候,slow 正好走到倒数第 k 个节点; 

    // 返回链表倒数第 k 个节点public ListNode findKthToTail(ListNode head, int k){if(head == null) return null;if(k <= 0 || k > size()) return null;ListNode fast = head;ListNode slow = head;while(--k > 0){fast = fast.next;}while(fast.next != null){fast = fast.next;slow = slow.next;}return slow;}

4. 合并两个有序链表

mergeTwoLists(ListNode list1, ListNode list2): ListNode 合并两个有序链表

两个链表的元素相互比较,小的加入新的队列,指针后移;

当有一个链表为空了,开始把剩下的链表的元素按顺序加入到新的链表中;

    public ListNode mergeTwoLists(ListNode list1, ListNode list2) {if(list1 == null) return list2;if(list2 == null) return list1;ListNode newHead = new ListNode();ListNode cur = newHead;while(list1 != null && list2 != null){if(list1.val <= list2.val){cur.next = list1;list1 = list1.next;}else{cur.next = list2;list2 = list2.next;}cur = cur.next;}while(list1 != null){cur.next = list1;list1 = list1.next;cur = cur.next;}while(list2 != null){cur.next = list2;list2 = list2.next;cur = cur.next;}return newHead.next;}

5. 分割链表

要求:将小于 x 的节点排在其余节点之前,不改变原来节点的顺序;

partition(ListNode pHead, int x): ListNode 分割链表;

小于 x 的节点放 head1 后面,大于等于 x 的节点放在 head2 后面;

合并 head1 和 head2,返回新的链表;

注意:后面的链表的尾巴节点的 next 一定要置空,避免成环;

    public ListNode partition(ListNode pHead, int x) {if(pHead == null) return null;ListNode head1 = new ListNode(0);ListNode head2 = new ListNode(0);ListNode cur1 = head1;ListNode cur2 = head2;ListNode cur = pHead;while(cur != null){if(cur.val < x){cur1.next = cur;cur1 = cur1.next;}else{cur2.next = cur;cur2 = cur2.next;}cur = cur.next;}// 这是需要注意的地方cur2.next = null;cur1.next = head2.next;return head1.next;}

6. 判断链表是否回文

chkPalindrom(ListNode A): boolean 检查链表是否回文;

reverse(ListNode head): ListNode 反转链表;

检查链表是否回文的关键首先是找到链表中点(奇数个节点找中点,偶数个节点找右中点),找到中点后从这个节点开始,逆置链表,形成两个链表;

分别从两个链表的头结点开始遍历链表,如果值不同,直接返回 false,如果值相同继续遍历,直到遍历完,返回 true;

    public boolean chkPalindrome(ListNode A) {if (A == null) return true;ListNode fast = A;ListNode slow = A;while (fast != null && fast.next != null) {fast = fast.next.next;slow = slow.next;}ListNode cur1 = A;ListNode cur2 = reverse(slow);boolean flag = true;while (cur1.next != null && cur2.next != null) {if (cur1.val != cur2.val) {flag = false;break;}cur1 = cur1.next;cur2 = cur2.next;}return flag;}public ListNode reverse(ListNode head) {ListNode newHead = new ListNode(0);ListNode cur = head;while (cur != null) {ListNode next = cur.next;cur.next = newHead.next;newHead.next = cur;cur = next;}return newHead.next;}

7. 找两个链表的第一个公共节点

getIntersectionNode(ListNode headA, ListNode headB): ListNode 找两个链表的第一个公共节点,没有公共节点返回 null;

定义两个指针遍历两个链表,同时让两个指针都往后走,如果相同返回节点即可;

如果不相同,当第一个指针遍历到最后,就让第一个指针指向第二个链表的头结点;同理,第二个指针边历到最后,让第二个指针也指向第一个链表;

这时候两个指针都同时向后移动,如果两个链表有公共节点,则一定会同时到达,因为两个指针速度相同,相同时间走的路程也一定相同;

如果两个链表没有公共节点,则最终会同时指向 null,返回 null 即可;

    public ListNode getIntersectionNode(ListNode headA, ListNode headB) {if(headA == null || headB == null) return null;ListNode cur1 = headA;ListNode cur2 = headB;while(cur1 != cur2){if(cur1 != null) cur1 = cur1.next;else cur1 = headB;if(cur2 != null) cur2 = cur2.next;else cur2 = headA;}return cur1;}

8. 判断链表是否有环

hasCycle(ListNode head): boolean 判断链表是否有环;

定义一个 fast,一个 slow 指针,每次 fast 走两步,slow 每次走一步,如果两个指针相遇了,就证明有环,否则就没有环;

    public boolean hasCycle(ListNode head) {ListNode fast = head;ListNode slow = head;while(fast != null && fast.next != null){fast = fast.next.next;slow = slow.next;if(fast == slow){return true;}}return false;}

9. 寻找链表入环的第一个节点

detectCycle(ListNode head): ListNode 寻找链表入环的第一个节点;

先找到 fast 和 slow 的相遇点,一个从起点出发,另一个从相遇点出发,最终两个指针会在环的入口点相遇;

    public ListNode detectCycle(ListNode head) {ListNode fast = head;ListNode slow = head;while(fast != null && fast.next != null){fast = fast.next.next;slow = slow.next;if(fast == slow){break;}}if(fast == null || fast.next == null) return null;slow = head;while(fast != slow){fast = fast.next;slow = slow.next;}return fast;}

三、模拟实现双向链表

双向链表的属性:用 head 表示链表的头节点,last 表示链表的尾巴节点;

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

1. 遍历链表

display(): void 打印链表;

size(): int 返回链表长度;

contains(int key): boolean 判断链表中是否包含 key;

    // 打印链表public void display(){ListNode cur = head;while(cur != null){System.out.print(cur.val + " ");cur = cur.next;}System.out.println();}// 返回链表长度public int size(){ListNode cur = head;int count = 0;while(cur != null){count++;cur = cur.next;}return count;}// 判断链表中是否包含 keypublic boolean contains(int key) {ListNode cur = head;while (cur != null) {if (cur.val == key) {return true;}cur = cur.next;}return false;}

2. 插入节点

addFirst(int data): void 头插法,将节点插入到链表头节点的位置;

注意:如果链表没有节点,插入的时候要把头指针和尾指针都指向插入的节点;

addLast(int data): void 尾插法,将节点插入到链表尾节点的位置,尾插的时候要

注意:如果链表没有节点,插入的时候要把头指针和尾指针都指向插入的节点;

findIndexPrev(int index): ListNode 找到 index 位置节点的前驱;

addIndex(int index, int data): void 在 index 位置插入节点;

插入之前需要先判断 index 位置是否合法;

如果合法再判断一下是否是头插,是否是尾插,因为这俩方法已经写好了,可以调用;

找到要插入节点的前驱和后继,进行插入;

    // 头插法public void addFirst(int data){ListNode node = new ListNode(data);if(head == null) {head = node;last = node;}else {node.next = head;head.prev = node;head = node;}}// 尾插法public void addLast(int data){ListNode node = new ListNode(data);if(head == null){head = node;last = node;}else{last.next = node;node.prev = last;last = node;}}// 在 index 位置插入public void addIndex(int index, int data){if(index < 0 || index > size()){throw new RuntimeException(index + "位置不合法!");}if(index == 0){addFirst(data);return;}else if(index == size()){addLast(data);return;}ListNode node = new ListNode(data);ListNode prevNode = findPrev(index);ListNode nextNode = prevNode.next;prevNode.next = node;node.prev = prevNode;node.next = nextNode;nextNode.prev = node;}private ListNode findPrev(int index){ListNode cur = head;while(--index > 0){cur = cur.next;}return cur;}

3. 删除节点

remove(int key): void 删除第一个值为 key  的节点;

找到要删除节点的前驱和后继;

如果前驱为空,就删除头节点,删除头结点要特殊处理只有一个节点的情况;

如果后继为空,就删除尾节点,删除尾节点要特殊处理只有一个节点的情况;

如果删除中间节点,删除后返回;

removeAll(int key): void 删除所有值为 key 的节点;

注意:原理同上,不同点是删除一个节点后,继续向后遍历;

    // 删除第一次出现关键字 key 的节点public void remove(int key){ListNode cur = head;while(cur != null){if(cur.val == key){ListNode prevNode = cur.prev;ListNode nextNode = cur.next;if(prevNode != null) {prevNode.next = nextNode;}else{head = head.next;if(head != null){head.prev = null;}}if(nextNode != null) {nextNode.prev = prevNode;}else{last = last.prev;if(last != null){last.next = null;}}break;}cur = cur.next;}}// 删除所有值为 key 的节点public void removeAll(int key){ListNode cur = head;while(cur != null) {if (cur.val == key) {ListNode prevNode = cur.prev;ListNode nextNode = cur.next;if (prevNode != null) {prevNode.next = nextNode;} else {head = head.next;if(head != null){head.prev = null;}}if (nextNode != null) {nextNode.prev = prevNode;} else {last = last.prev;if(last != null){last.next = null;}}cur = nextNode;}else{cur = cur.next;}}}

4. 清空链表

clear(): void 清空链表;

注意:要把 headlast 置空;

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

四、ArrayList 和 LinkedList 的区别

存储上:

ArrayList 在存储空间上是连续的,LinkedList 逻辑上是,连续的,在存储空间上是不一定连续的;

操作上:

从查询元素上来说,ArrayList 的时间复杂度是 O(1),而 LinkedList 不支持随机访问;

从插入上来说:

LinkedList 的时间复杂度是 O(1),ArrayList 头插时间复杂度是 O(n),因为需要把把元素统一往后移一个位置;

ArrayList 在插入时,空间不够时,需要扩容,而 LInkedList 没有容量的概念;

应用场景:

ArrayList 适合频繁查询,LinkedList 适合频繁插入删除;

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

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

相关文章

DC3靶机渗透

1. 靶机介绍 主要的内容有 sql 注入漏洞、joomla 框架漏洞、ssh 攻击、shell 反弹、提权 信息收集(ip、端口、目录、指纹信息)--->利用漏洞--->反弹---->提权 2. 信息收集 2.1. 扫描存活 ip 192.168.220.134 2.2. 端口扫描 nmap -T4 -A -p- 192.168.220.134 …

C# 线程交互

一、为什么要进行线程交互 在C#中&#xff0c;线程交互通常涉及到多个线程之间的数据共享和同步。‌. 一、全局变量 在C#中&#xff0c;全局变量是指在程序的任何地方都可以访问的变量。通常&#xff0c;全局变量是在类的外部定义的&#xff0c;或者在所有方法之外定义的。全…

Cursor 编辑器中的 Notepad 功能使用指南

Cursor 编辑器中的 Notepad 功能使用指南 摘要 本指南全面介绍了 Cursor 编辑器中的 Notepad 功能&#xff0c;涵盖其用途、多种访问方式、适用场景以及与其它功能的整合技巧等内容&#xff0c;助力用户高效利用该功能提升工作流程效率。 不同访问方式介绍 功能概述 Curso…

用于评估大语言模型(LLMs)能力的重要基准任务(Benchmark)

基准任务涵盖了 多领域&#xff08;如语言理解、数学、推理、编程、医学等&#xff09;和 多能力维度&#xff08;如事实检索、计算、代码生成、链式推理、多语言处理&#xff09;。常用于模型发布时的对比评测&#xff0c;例如 GPT-4、Claude、Gemini、Mistral 等模型的论文或…

力扣HOT100之技巧:169. 多数元素

这道题如果不考虑空间复杂度和时间复杂度的限制的话很好做&#xff0c;一种思路是通过一次遍历将所有元素的数量记录在一个哈希表中&#xff0c;然后我们直接返回出现次数最多的键即可。另一种思路是直接对数组进行排序&#xff0c;数组中间的值一定是多数元素&#xff0c;因为…

wordpress首页调用指定ID页面内的相册

要在WordPress首页调用ID为2的页面中的相册&#xff0c;你可以使用以下几种方法&#xff1a; 方法一&#xff1a;使用短代码和自定义查询 首先&#xff0c;在你的主题的functions.php文件中添加以下代码&#xff1a; function display_page_gallery($atts) {$atts shortcod…

基于深度学习的异常检测系统:原理、实现与应用

前言 在现代数据驱动的业务环境中&#xff0c;异常检测&#xff08;Anomaly Detection&#xff09;是一个关键任务&#xff0c;它能够帮助企业和组织及时发现数据中的异常行为或事件&#xff0c;从而采取相应的措施。异常检测广泛应用于金融欺诈检测、网络安全、工业设备故障监…

Java基于BS架构的OA流程可视化实战:从工作流引擎到前端交互(附完整源代码+论文框架)

一、引言&#xff1a;BS架构OA系统的流程可视化需求 在企业信息化建设中&#xff0c;基于浏览器/服务器&#xff08;BS&#xff09;架构的OA系统通过流程自动化提升办公效率&#xff0c;而流程可视化是实现流程监控、优化的核心模块。本文基于Java技术栈&#xff0c;结合Activ…

JavaWeb-数据库连接池

目录 1.springboot默认Hikari(追光者)连接池 2.切换为Druid(德鲁伊)连接池 1.springboot默认Hikari(追光者)连接池 2.切换为Druid(德鲁伊)连接池 一般几乎用不到&#xff0c;不需要切换 <!--Druid连接池--> <dependency><groupId>com.alibaba</groupId&…

c# 完成恩尼格玛加密扩展

c# 完成恩尼格玛加密扩展 恩尼格玛扩展为可见字符恩尼格玛的设备原始字符顺序转子的设置反射器的设置连接板的设置 初始数据的设置第一版 C# 代码第二版 C# 代码 总结 恩尼格玛 在之前&#xff0c;我们使用 python 实现了一版恩尼格玛的加密算法&#xff0c;但是这一版&#x…

【Redisson】锁可重入原理

目录 一、基本原理 二、源码解析&#xff1a; &#xff08;2&#xff09;获取锁 &#xff08;1&#xff09;释放锁&#xff1a; 之前给大家介绍过redisson的分布式锁&#xff0c;用redisson来实现比自己手搓简单的分布式锁有很多好处&#xff0c;因为这些可重入、可重试的逻…

BERT 模型微调与传统机器学习的对比

BERT 微调与传统机器学习的区别和联系&#xff1a; 传统机器学习流程 传统机器学习处理文本分类通常包含以下步骤&#xff1a; 特征工程&#xff1a;手动设计特征&#xff08;如 TF-IDF、词袋模型&#xff09;模型训练&#xff1a;使用分类器&#xff08;如 SVM、随机森林、逻…

(12)-Fiddler抓包-Fiddler设置IOS手机抓包

1.简介 Fiddler不但能截获各种浏览器发出的 HTTP 请求&#xff0c;也可以截获各种智能手机发出的HTTP/ HTTPS 请求。 Fiddler 能捕获Android 和 Windows Phone 等设备发出的 HTTP/HTTPS 请求。同理也可以截获iOS设备发出的请求&#xff0c;比如 iPhone、iPad 和 MacBook 等苹…

芯科科技Tech Talks技术培训重磅回归:赋能物联网创新,共筑智能互联未来

聚焦于Matter、蓝牙、Wi-Fi、LPWAN、AI/ML五大热门无线协议与技术 为年度盛会Works With大会赋能先行 随着物联网&#xff08;IoT&#xff09;和人工智能&#xff08;AI&#xff09;技术的飞速发展&#xff0c;越来越多的企业和个人开发者都非常关注最新的无线连接技术和应用…

docker-compose容器单机编排

docker-compose容器单机编排 开篇前言 随着网站架构的升级&#xff0c;容器的使用也越来越频繁&#xff0c;应用服务和容器之间的关系也越发的复杂。 这个就要求研发人员能更好的方法去管理数量较多的服务器&#xff0c;而不能手动挨个管理。 例如一个LNMP 架构&#xff0c;就…

LeetCode--29.两数相除

解题思路&#xff1a; 1.获取信息&#xff1a; 给定两个整数&#xff0c;一个除数&#xff0c;一个被除数&#xff0c;要求返回商&#xff08;商取整数&#xff09; 限制条件&#xff1a;&#xff08;1&#xff09;不能使用乘法&#xff0c;除法和取余运算 &#xff08;2&#…

中山大学GaussianFusion:首个将高斯表示引入端到端自动驾驶多传感器融合的新框架

摘要 近年来由于端到端自动驾驶极大简化了原有传统自动驾驶模块化的流程&#xff0c;吸引了来自工业界和学术界的广泛关注。然而&#xff0c;现有的端到端智驾算法通常采用单一传感器&#xff0c;使其在处理复杂多样和具有挑战性的驾驶场景中受到了限制。而多传感器融合可以很…

《哈希算法》题集

1、模板题集 满足差值的数字对 2、课内题集 字符统计 字符串统计 优质数对 3、课后题集 2006 Equations k倍区间 可结合的元素对 满足差值的数字对 异常频率 神秘数对 费里的语言 连连看 本题集为作者&#xff08;英雄哪里出来&#xff09;在抖音的独家课程《英雄C入门到精…

Cordova移动应用对云端服务器数据库的跨域访问

Cordova移动应用对云端服务器数据库的跨域访问 当基于类似 Cordova这样的跨平台开发框架进行移动应用的跨平台开发时&#xff0c;往往需要访问部署在公网云端服务器上的数据库&#xff0c;这时就涉及到了跨域数据访问的问题。 文章目录 Cordova移动应用对云端服务器数据库的跨…

mysql知识点3--创建和使用数据库

mysql知识点3–创建数据库 创建数据库 在MySQL中创建数据库使用CREATE DATABASE语句。语法如下&#xff1a; CREATE DATABASE database_name;其中database_name为自定义的数据库名称。例如创建名为test_db的数据库&#xff1a; CREATE DATABASE test_db;可以添加字符集和排…