数据结构---链表（一）【不带头单向非循环】

文章目录

  • 链表概念
  • 链表的使用
  • LinkedList 的几种遍历方式
  • 单链表的模拟实现（不带头）
  • 链表面试题

  观察ArrayList 顺序表的源码发现，底层是使用数组实现的。由于其底层是一段连续空间，当在ArrayList任意位置插入或者删除元素时，就需要将后序元素整体往前或者往后搬移，时间复杂度为O(n)，效率比较低，因此ArrayList不适合做任意位置插入和删除比较多的场景。因此：java集合中又引入了LinkedList，即链表结构。

链表概念

链表是一种物理存储结构上非连续存储结构，数据元素的逻辑顺序是通过链表中的引用链接次序实现的 。
在这里插入图片描述

由上图可以看出链表在逻辑上是连续的，但是在逻辑上不一定连续

链表有很多不同的结构：
1.不带头单向非循环
2.不带头单向循环
3.不带头双向非循环
4.不带头双向循环
5.带头单向非循环
6.带头单向循环
7.带头双向非循环
8.带头双向循环
共八种不同的结构
本篇文章主要介绍 不带头单向非循环 的链表结构及其方法的实现。

链表的使用

LinkedList的构造
在这里插入图片描述
创建LinkedList的代码示例如下：

public static void main(String[] args) {
// 构造一个空的LinkedList
List<Integer> list1 = new LinkedList<>();
List<String> list2 = new java.util.ArrayList<>();
list2.add("JavaSE");
list2.add("JavaWeb");
list2.add("JavaEE");
// 使用ArrayList构造LinkedList
List<String> list3 = new LinkedList<>(list2);
}

LinkedList的常用方法
在这里插入图片描述

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);
System.out.println(list.size());
// foreach遍历
for (int e:list) {
System.out.print(e + " ");
} 
System.out.println();
// 使用迭代器遍历---正向遍历
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();
}

单链表的模拟实现（不带头）

LinkedList中常用的方法如下：

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

核心就是遍历链表，所有方法的具体实现如下：

public class MySingleList {//内部类   节点static class ListNode{public int val;public ListNode next;public ListNode(int val) {this.val = val;}}ListNode head;//创建单链表public void createList() {ListNode node1 = new ListNode(11);ListNode node2 = new ListNode(23);ListNode node3 = new ListNode(56);ListNode node4 = new ListNode(42);head = node1;node1.next = node2;node2.next = node3;node3.next = node4;}//打印单链表public void show() {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;}//头插法public void headAdd(int val) {ListNode headAdd = new ListNode(val);headAdd.next = head;head = headAdd;}//尾插法public void endAdd(int val) {ListNode endAdd = new ListNode(val);ListNode cur = head;while(cur.next != null) {cur = cur.next;}cur.next = endAdd;}//在index位置插入数据valpublic void addIndex(int index,int val) {if(index < 0 || index > size()-1) {throw new OutOfIndexException("index不合法");}else if(index == 0) {headAdd(val);}else if(index == size()-1) {endAdd(val);}else {ListNode cur = head;for (int i = 1; i < index; i++) {cur = cur.next;}ListNode addVal = new ListNode(val);addVal.next = cur.next;cur.next = addVal;}}//删除数据第一次出现的keypublic void remove(int key) {if(head == null) return;ListNode cur = head;while(cur != null) {//判断第一个节点的val值是否为keyif(head.val == key) {head = head.next;return;}ListNode lastKeyNode = findLastKey(key);if(lastKeyNode == null) {return;//没有找到要删除 val值为key 的节点}lastKeyNode.next = lastKeyNode.next.next;return;}}//找到第一个值为key的节点  的前一个节点public ListNode findLastKey(int key) {ListNode cur = head;while(cur.next != null) {if(cur.next.val == key) {return cur;}cur = cur.next;}return null;}//删除 所有 值为key 的节点public void removeAll(int key) {if(head == null) return;ListNode cur = head.next;ListNode pre = head;while(cur != null) {if(cur.val == key) {pre.next = cur.next;cur = cur.next;}else {pre = cur;cur = cur.next;}}if(head.val == key) {head = head.next;}}//清空所有的节点public void clear() {if(head == null) return;ListNode cur = head;while(cur.next != null) {ListNode tmp = cur.next;cur.next = null;cur = tmp;}head = null;}
}

链表面试题

  1. 删除链表中等于给定值 val 的所有节点
    上述方法已经实现，代码示例如下：
    //删除 所有 值为key 的节点public void removeAll(int key) {if(head == null) return;ListNode cur = head.next;ListNode pre = head;while(cur != null) {if(cur.val == key) {pre.next = cur.next;cur = cur.next;}else {pre = cur;cur = cur.next;}}if(head.val == key) {head = head.next;}}
  1. 反转一个单链表。 OJ链接
    在这里插入图片描述
    【解题思路】每个链表中的结点都有自己的地址，假设原链表的指向如下图所示：
    在这里插入图片描述
    实现翻转链表就可以把后一个结点的next域，指向前一个结点，遍历整个链表之后，这样每一个结点的next域就会指向前一个结点，此时head走到了最后一个节点，返回head。实现这些操作后的链表中结点的指向如下图：
    在这里插入图片描述
class Solution {public ListNode reverseList(ListNode head) {if(head == null) return null;ListNode cur = head.next;  ListNode tmp = null;head.next = null;while(cur != null) {tmp = cur.next; //使用tmp标记cur的下一个指向的结点cur.next = head; //后一个结点的next域指向前一个结点head = cur; //head 向后走一步cur = tmp; //cur 向后走一步}return head;}
}
  1. 给定一个带有头结点 head 的非空单链表，返回链表的中间结点。如果有两个中间结点，则返回第二个中间结点。OJ链接
      方法一：先求出链表的长度 len，不管长度len 是奇数还是偶数，中间结点就是 head 向前移动 len/2 次后所在的结点。
    I. 先求出链表的长度：遍历链表，代码示例如下：
public int size(ListNode head) {if(head == null) {return -1;}int count = 0;ListNode cur = head;while(cur != null) {count++;cur = cur.next;}return count;}

II.求出长度len后，让head结点向前移动 len/2 次，此时head结点指向的就是中间节点，完整代码示例如下：

class Solution {public ListNode middleNode(ListNode head) {if(head == null) {return null;}int len = size(head);int count = len / 2;ListNode cur = head;while(count != 0) {cur = cur.next;count--;}return cur;}public int size(ListNode head) {if(head == null) {return -1;}int count = 0;ListNode cur = head;while(cur != null) {count++;cur = cur.next;}return count;}
}

  方法二：使用快慢指针。定义快指针 fast，慢指针 slow ，初始 fast 和 slow 都指向head，fast 一次向前移动两步，slow 一次向前移动一步，当fast走到最后时，此时slow就指向 中间结点。那么fast走到最后的循环终止条件如何设置？ —> 当链表中结点个数为奇数时，fast走完 刚好指向最后一个结点，所以终止条件为 fast.next == null；当当链表中结点个数为偶数时，fast走完 刚好指向最后一个结点的下一个结点（也就是null），所以终止条件为 fast == null。所以只要满足这两个条件中的其中一个就会终止，转换到代码层面为： fast.next == null || fast == null因此while()中的条件应该为 fast.next != null && fast != null
【 注意 】这里while() 中的判断条件并不是fast.next != null || fast != null ！！！
代码示例如下：

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

4.输入一个链表，输出该链表中倒数第k个结点

这道题和上一道题一样的思路，也是有两种解决方法。
  方法一：求链表长度len ，让head 向后走 len - k 步，此时head 就指向了倒数第K个结点

        //输入一个链表，输出该链表中倒数第k个结点//方法一public int kthToLast(ListNode head, int k) {if(k <= 0 || k > size(head)) {return -1;}int len = size(head);int count = 0;ListNode cur = head;while(count < len -k) {cur = cur.next;count++;}return cur.val;}private int size(ListNode head) {int count = 0;while(head != null) {count++;head = head.next;}return count;}

  方法二：还是使用快慢指针，快指针 fast ，慢指针 slow，初始 fast 和 slow 都指向head ，此时需要先让fast 向前走 k-1 步，然后 fast 和 slow 绑着一块向前走，一次走一步，当 fast 走到最后时，slow 就指向了倒数第K个结点.代码示例如下:

        //方法二public int kthToLast2(ListNode head, int k) {if(k <= 0) {return -1;}ListNode fast = head;ListNode slow = head;int count = k - 1;while(count != 0) {fast = fast.next;if(fast == null) {return -1;}count--;}while(fast.next != null) {fast = fast.next;slow = slow.next;}return slow.val;}
  1. 将两个有序链表合并为一个新的有序链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。OJ
    链接
    两个有序链表的合并，一定是要遍历两个链表，最后返回拼接后的链表的头结点，
      我们可以定义一个伪结点 newH（用来表示合并后新链表的带头结点），newH.next 中存的是新链表的第一个结点，也是data域最小的结点，所以最终返回的结点为 newH.next 。
      定义 tmpH 结点，使 tmpH 指向 newH 所指向的对象，只操作tmpH 的next 域 按照升序来拼接结点，最终返回的是newH.next,此时tmpH已经完成了结点的拼接

  遍历两个链表，循环条件为 headA 和 headB 都不为null 。每次比较 headA.val 和 headB.val 的大小，哪个小 就把哪个结点 赋值给 tmpH.next。遍历完成之后，如果其中一个结点不为空，就把 这一个结点 赋给 tmpH.next（原本都是升序链表,连接后 后面也一定是升序）

本人注意：【newH 和 tmpH 的关系理解为 head 和 cur 的关系】

在这里插入图片描述代码示例如下：
  

    public ListNode mergeTwoLists(ListNode headA, ListNode headB) {if(headA == null && headB == null) return null;ListNode newH = new ListNode();ListNode tmpH = newH;while(headA != null && headB != null) {if(headA.val < headB.val) {tmpH.next = headA;tmpH = headA;headA = headA.next;}else {tmpH.next = headB;tmpH = headB;headB = headB.next;}}if(headA == null) {tmpH.next = headB;}else {tmpH.next = headA;}return newH.next;
}

在这里插入图片描述

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

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

相关文章

Pytorch（一）

Pytorch（一）

一.PyTorch环境配置及安装 1.1 工具安装 1.1.1 Anaconda下载 清华大学镜像站下载&#xff0c;版本为Anaconda3-5.2.0-Windows-x86_64&#xff08;对应python3.6.5&#xff09; Index of /anaconda/archive/ | 清华大学开源软件镜像站 | Tsinghua Open Source Mirror 1.1.2…
阅读更多...
关于我的数据结构与算法——初阶第二篇（排序）

关于我的数据结构与算法——初阶第二篇（排序）

&#xff08;叠甲&#xff1a;如有侵权请联系&#xff0c;内容都是自己学习的总结&#xff0c;一定不全面&#xff0c;仅当互相交流&#xff08;轻点骂&#xff09;我也只是站在巨人肩膀上的一个小卡拉米&#xff0c;已老实&#xff0c;求放过&#xff09;。 排序的概念及其运…
阅读更多...
AI驱动的低代码未来：加速应用开发的智能解决方案

AI驱动的低代码未来：加速应用开发的智能解决方案

引言 随着数字化转型的浪潮席卷全球&#xff0c;企业对快速构建应用程序的需求愈发强烈。然而&#xff0c;传统的软件开发周期冗长、成本高昂&#xff0c;往往无法满足快速变化的市场需求。在此背景下&#xff0c;低代码平台逐渐成为开发者和企业的优选方案&#xff0c;以其“低…
阅读更多...
三周精通FastAPI：21 子依赖项和路径操作装饰器依赖项

三周精通FastAPI：21 子依赖项和路径操作装饰器依赖项

官方文档&#xff1a;https://fastapi.tiangolo.com/zh/tutorial/dependencies/sub-dependencies/#_6 子依赖项 FastAPI 支持创建含子依赖项的依赖项。 并且&#xff0c;可以按需声明任意深度的子依赖项嵌套层级。 FastAPI 负责处理解析不同深度的子依赖项。 第一层依赖项 …
阅读更多...
模具生产管理系统软件：提升制造业效率的新利器

模具生产管理系统软件：提升制造业效率的新利器

引言 我们都知道&#xff0c;企业面临着提高生产效率、降低成本和提升产品质量的压力。模具生产作为制造过程中至关重要的一环&#xff0c;如何有效管理和优化模具生产过程&#xff0c;成为企业关注的重点。模具生产管理系统应运而生&#xff0c;能够为企业提供实时监控、流程…
阅读更多...
MySQL中，如何定位慢查询？定位到的慢SQL如何分析？

MySQL中，如何定位慢查询？定位到的慢SQL如何分析？

目录 1. 慢查询发生的场景&#xff1f; 2. MySQL中&#xff0c;如何定位慢查询&#xff1f; 2.1 详细解释 3. 定位到的慢SQL如何分析&#xff1f; 3.1 详细说明 1. 慢查询发生的场景&#xff1f; 2. MySQL中&#xff0c;如何定位慢查询&#xff1f; 介绍一下当时产生问题…
阅读更多...
「C/C++」C++ 设计模式 之 单例模式（Singleton）

「C/C++」C++ 设计模式 之 单例模式（Singleton）

✨博客主页何曾参静谧的博客&#x1f4cc;文章专栏「C/C」C/C程序设计&#x1f4da;全部专栏「VS」Visual Studio「C/C」C/C程序设计「UG/NX」BlockUI集合「Win」Windows程序设计「DSA」数据结构与算法「UG/NX」NX二次开发「QT」QT5程序设计「File」数据文件格式「PK」Parasoli…
阅读更多...
华为云开源项目Sermant正式成为CNCF官方项目

华为云开源项目Sermant正式成为CNCF官方项目

近日&#xff0c;云原生计算基金会&#xff08;CNCF&#xff09;正式接纳由华为云发起的云原生无代理服务网格项目Sermant。Sermant的加入&#xff0c;极大地丰富了云原生微服务治理技术的探索、创新和发展&#xff0c;为CNCF社区注入了新的活力。 Sermant是华为云在微服务治理…
阅读更多...
用sdcc给51单片机编译C程序

用sdcc给51单片机编译C程序

学习单片机大部分人用的是Keil uVision&#xff0c;虽然好用&#xff0c;可大部分人用的是盗版&#xff0c;其实单片机程序小的话&#xff0c;完全可以用文本编辑器&#xff08;推荐notepad)编写&#xff0c;然后用免费的sdcc来编译&#xff0c;下面介绍一下大致的过程。 sdcc…
阅读更多...
Ajax：表单 模板引擎

Ajax：表单 模板引擎

Ajax&#xff1a;表单 & 模板引擎 form 表单form 属性 Ajax操控表单事件监听阻止默认行为收集表单数据 模板引擎art-template{{}}语法原文输出条件输出循环输出过滤器 原理 form 表单 在HTML中&#xff0c;可以通过<form>创建一个表单&#xff0c;收集用户信息。而采…
阅读更多...
【水下生物数据集】 水下生物识别 深度学习 目标检测 机器视觉 yolo（含数据集）

【水下生物数据集】 水下生物识别 深度学习 目标检测 机器视觉 yolo（含数据集）

一、背景意义 随着全球海洋生态环境的日益变化&#xff0c;水下生物的监测和保护变得愈发重要。水下生物种类繁多&#xff0c;包括螃蟹、鱼类、水母、虾、小鱼和海星等&#xff0c;它们在海洋生态系统中扮演着关键角色。传统的水下生物监测方法通常依赖于人工观察&#xff0c;效…
阅读更多...
[vulnhub]Kioptrix: Level 1.2 (#3)

[vulnhub]Kioptrix: Level 1.2 (#3)

https://www.vulnhub.com/entry/kioptrix-level-12-3,24/ 主机发现端口扫描 使用nmap扫描网段类存活主机 因为靶机是我最后添加的&#xff0c;所以靶机IP是169 nmap -sP 192.168.75.0/24 Starting Nmap 7.94SVN ( https://nmap.org ) at 2024-10-29 13:16 CST …
阅读更多...
TVM前端研究--Relay

TVM前端研究--Relay

文章目录 深度学习IR梳理1. IR属性2. DL前端发展3. DL编译器4. DL编程语言Relay的主要内容一、Expression in Relay1. Dataflow and Control Fragments2. 变量3. 函数3.1 闭包3.2 多态和类型关系3.3. Call4. 算子5. ADT Constructors6. Moudle和Global Function7. 常量和元组8.…
阅读更多...
Ubuntu UFW防火墙规则与命令示例大全

Ubuntu UFW防火墙规则与命令示例大全

在服务器安全领域&#xff0c;防火墙是守护网络安全的坚实盾牌。UFW&#xff08;Uncomplicated Firewall&#xff09;&#xff0c;即“不复杂的防火墙”&#xff0c;是一个运行在iptables之上的防火墙配置工具&#xff0c;它为Ubuntu系统默认提供了一个简洁的命令行界面&#x…
阅读更多...
Linux高阶——1026—验证内存映射mmap函数使用

Linux高阶——1026—验证内存映射mmap函数使用

1、验证共享映射后修改文件内容&#xff0c;是否能够同步 先创建一个映射文件&#xff0c;写入数据 分为四个步骤 1、打开映射文件 设文件描述符&#xff0c;使用open函数 int fd; if((fdopen("mapfile",O_RDWR))-1) { perror("open failed");exit…
阅读更多...
从零开始的 vue项目部署到服务器详细步骤（vue项目build打包+nginx部署+配置ssl证书）

从零开始的 vue项目部署到服务器详细步骤（vue项目build打包+nginx部署+配置ssl证书）

从零开始的 vue项目部署到服务器详细步骤&#xff08;vue项目build打包nginx部署配置ssl证书&#xff09; 文章目录 从零开始的 vue项目部署到服务器详细步骤&#xff08;vue项目build打包nginx部署配置ssl证书&#xff09;一、前言二、vue项目部署前配置1、vite.config.js 增加…
阅读更多...
快速遍历包含合并单元格的Word表格

快速遍历包含合并单元格的Word表格

Word中的合并表格如下&#xff0c;现在需要根据子类&#xff08;例如&#xff1a;果汁&#xff09;查找对应的品类&#xff0c;如果这是Excel表格&#xff0c;那么即使包含合并单元格&#xff0c;也很容易处理&#xff0c;但是使用Word VBA进行查找&#xff0c;就需要一些技巧。…
阅读更多...
智慧园区 | 数智引领，让智慧触手可及

智慧园区 | 数智引领，让智慧触手可及

随着科技的飞速发展&#xff0c;智慧园区正成为现代城市发展的重要方向之一。在智慧园区中&#xff0c;各种高科技手段被应用于园区的管理和服务&#xff0c;为园区的运营和居民的生活带来无限可能。 智慧园区管理平台是智慧园区建设的核心。它集聚了大数据、物联网、云计算等技…
阅读更多...
基于uniapp微信小程序的旅游系统

基于uniapp微信小程序的旅游系统

作者&#xff1a;计算机学姐 开发技术&#xff1a;SpringBoot、SSM、Vue、MySQL、JSP、ElementUI、Python、小程序等&#xff0c;“文末源码”。 专栏推荐&#xff1a;前后端分离项目源码、SpringBoot项目源码、Vue项目源码、SSM项目源码、微信小程序源码 精品专栏&#xff1a;…
阅读更多...
【分布式知识】分布式对象存储组件-Minio

【分布式知识】分布式对象存储组件-Minio

文章目录 什么是minio核心特点&#xff1a;使用场景&#xff1a;开发者工具&#xff1a;社区和支持&#xff1a; 核心概念什么是对象存储&#xff1f;MinIO 如何确定对对象的访问权限&#xff1f;我可以在存储桶内按文件夹结构组织对象吗&#xff1f;如何备份和恢复 MinIO 上的…
阅读更多...
最新文章
推荐文章

Copyright @ 2022~2023