Java中的链表

文章目录

  • 前言
  • 一、链表的概念及结构
  • 二、单向不带头非循坏链表的实现
    • 2.1打印链表
    • 2.2求链表的长度
    • 2.3头插法
    • 2.4尾插法
    • 2.5任意位置插入
    • 2.6查找是否包含某个元素的节点
    • 2.7删除第一次出现这个元素的节点
    • 2.8删除包含这个元素的所以节点
    • 2.9清空链表
    • 单向链表的测试
  • 三、双向不带头非循坏链表的实现
    • 3.1打印双向链表
    • 3.2求双向链表的长度
    • 3.3头插法
    • 3.4尾插法
    • 3.5任意位置插入
    • 3.6查找是否包含某个元素的节点
    • 3.7删除第一次出现这个元素的节点
    • 3.7删除包含这个元素的所有节点
    • 3.9清空双向链表
    • 双向链表的测试
    • LinkedList的遍历方式
    • 四、ArrayList和LinkedList的区别

前言

在前面我们已经学习了关于顺序表ArrayList的一些基本操作。通过源码知道，ArrayList底层使用数组来存储元素，由于其底层是一段连续空间，当在ArrayList任意位置插入或者删除元素时，就需要将后序元素整体往前或者往后搬移，时间复杂度为O(n)，效率比较低，因此ArrayList不适合做任意位置插入和删除比较多的场景。因此：java集合中又引入了LinkedList，即链表结构

一、链表的概念及结构

链表是一种物理存储结构上非连续存储结构，数据元素的逻辑顺序是通过链表中的引用链接次序实现的
注意：
1.链式结构在逻辑上是连续的，但是在物理上不一定连续
2.现实中的结点一般都是从堆上申请出来的
3.从堆上申请的空间，是按照一定的策略来分配的，两次申请的空间可能是连续，也可能不连续

链表的结构有8种样式：
单向带头循坏、单向带头非循坏、单向不带头循坏、单向不带头非循坏
双向带头循坏、双向带头非循坏、双向不带头循坏、双向不带头非循坏

这里我们主要学习以下两中结构：
单向不带头非循坏
在这里插入图片描述
LinkedList底层使用的就是双向不带头非循坏
在这里插入图片描述

二、单向不带头非循坏链表的实现

2.1打印链表

不带参数的打印

public void display() {
    ListNode cur = head;
    if(cur != null) {//遍历完所以节点
        System.out.print(cur.val+" ");
        cur = cur.next;
    }
    System.out.println();
}

带参数的打印

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

2.2求链表的长度

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

2.3头插法

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

2.4尾插法

public void addLast(int data){
    ListNode node = new ListNode(data);
    if(head == null) {
        head = node;
    }else {
        ListNode cur = head;
        while (cur.next != null) {//走到最后一个节点的位置
            cur = cur.next;
        }
        cur.next = node;
    }
}

2.5任意位置插入

在任意位置插入时我们要判断该位置是否合法，不合法的时候要抛一个异常

  public void addIndex(int index,int data){
      if(index < 0 || index > size()) {
          throw new IndexException("index位置不合法："+index);
      }
      ListNode node = new ListNode(data);
      if(head == null) {
          head = node;
          return;
      }
      if(index == 0) {
          addFirst(data);
          return;
      }
      if(index == size()) {
          addLast(data);
          return;
      }
      //中间插入
      ListNode cur = serchIndex(index);
      node.next = cur.next;
      cur.next = node;
}

找要添加节点位置的前一个节点

public ListNode serchIndex(int index) {
    ListNode cur = head;
    int count = 0;
    while (count != index-1) {
        cur = cur.next;
        count++;
    }
    return cur;
}

2.6查找是否包含某个元素的节点

遍历这个链表找是否与这个元素相同

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

2.7删除第一次出现这个元素的节点

public void remove(int key){
    if(head == null) {
        return;
    }
    if(head.val == key) {
        head = head.next;
        return;
    }
    ListNode cur = findKey(key);
    if(cur == null) {
        return;//没有要删除的元素
    }
    ListNode del = cur.next;
    cur.next = del.next;
}

要删除节点的前一个节点

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

2.8删除包含这个元素的所以节点

public 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;
            cur = cur.next;
        }else {
            prev = cur;
            cur = cur.next;
        }
    }
    //除了头节点外，其余都删完了
    if(head.val == key) {
        head = head.next;
    }
}

2.9清空链表

清空链表只需要把头节点置为空

public void clear() {
    head = null;
}

单向链表的测试

public class Test {
    public static void main(String[] args) {
        MySingleList list = new MySingleList();
        list.addLast(30);//尾插
        list.addLast(20);
        list.addLast(30);
        list.addLast(40);
        list.addLast(50);
        list.addFirst(100);//头插
        list.addIndex(2,15);//任意位置插入
        list.display();
        System.out.println("*****");
        System.out.println(list.contains(20));//查看是否包含某个节点
        System.out.println("*****");
        System.out.println(list.size());//求链表长度
        System.out.println("*****");
        list.remove(30);//删除第一个出现的节点
        list.display();
        list.removeAllKey(30);//删除包含这个元素的所以节点
        System.out.println("*****");
        list.display();
        System.out.println("*****");
        list.clear();//清空链表
        list.display();
    }
}

在这里插入图片描述

三、双向不带头非循坏链表的实现

3.1打印双向链表

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

3.2求双向链表的长度

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

3.3头插法

public void addFist(int data) {
    ListNode node = new ListNode(data);
    if(head == null) {//一个节点都没有的情况
        head = node;
        last = node;
    }else {
        node.next = head;
        head.prev = node;
        head = node;
    }
}

3.4尾插法

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;
    }
}

3.5任意位置插入

这里的插入与单向链表一样也需要判断该位置的合法性，不合法时抛一个异常

public void addIndex(int index,int data) {
    if(index < 0 || index > size()) {
        throw new IndexException("双向链表中index的位置不合法："+index);
    }
    if(index == 0) {
        addFist(data);
    }
    if(index == size()) {
        addLast(data);
    }
    ListNode cur = findIndex(index);
    ListNode node = new ListNode(data);
    node.next = cur;
    cur.prev.next = node;
    node.prev = cur.prev;
    cur.prev = node;
}

要添加节点的位置

public ListNode findIndex(int index) {
    ListNode cur = head;
    if(index != 0) {
        cur = cur.next;
        index --;
    }
    return cur;
}

3.6查找是否包含某个元素的节点

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

3.7删除第一次出现这个元素的节点

因为数据结构是一门逻辑性非常严谨的学科，所以这里的删除需要考虑多种因素

public 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 {
                //删除中间节点
                if(cur.next != null) {
                    cur.next.prev = cur.prev;
                    cur.prev.next = cur.next;
                }else {
                    //删除尾巴节点
                    cur.prev.next = cur.next;
                    last = last.prev;
                }
            }
            return;
        }
        cur = cur.next;
    }
}

3.7删除包含这个元素的所有节点

public 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 {
                //删除中间节点
                if(cur.next != null) {
                    cur.next.prev = cur.prev;
                    cur.prev.next = cur.next;
                }else {
                    //删除尾巴节点
                    cur.prev.next = cur.next;
                    last = last.prev;
                }
            }
        }
        cur = cur.next;
    }
}

3.9清空双向链表

public void clear(){
    ListNode cur = head;
    while (cur != null) {
        ListNode curNext = cur.next;
        cur.prev = null;
        cur.next = null;
        cur = cur.next;
    }
    head = null;//头节点置空
    last = null;//尾巴节点置空
}

双向链表的测试

public class Test {
    public static void main(String[] args) {
        MyLinkedList myLinkedList = new MyLinkedList();
        myLinkedList.addLast(12);//尾插法
        myLinkedList.addLast(45);
        myLinkedList.addLast(34);
        myLinkedList.addLast(45);
        myLinkedList.addFist(56);//头插法
        myLinkedList.addIndex(2,15);//任意位置插入
        myLinkedList.display();
        System.out.println(myLinkedList.size());//求双向链表的长度
        System.out.println("******");
        System.out.println(myLinkedList.contains(23));//查找是否包含某个元素的节点
        System.out.println("******");
        myLinkedList.remove(45);//删除第一次出现这个元素的节点
        myLinkedList.display();
        System.out.println("******");
        myLinkedList.removeAllKey(45);//删除包含这个元素的所以节点
        myLinkedList.display();
        System.out.println("******");
        myLinkedList.clear();//清空链表
        myLinkedList.display();
    }
}

在这里插入图片描述

LinkedList的遍历方式

关于LinkedList的遍历方式有四种：

public class Test {
    public static void main(String[] args) {
        LinkedList<Integer> list = new LinkedList<>();
        list.add(1);
        list.add(2);
        list.add(3);
        list.add(4);
        System.out.println(list);
        //for循坏遍历
        for (int i = 0; i < list.size(); i++) {
            System.out.print(list.get(i)+" ");
        }
        System.out.println();
        System.out.println("*******");
        //foreach遍历
        for (int m : list) {
            System.out.print(m +" ");
        }
        System.out.println();
        System.out.println("*******");
        //使用迭代器——正向遍历
        ListIterator<Integer> it = list.listIterator();
        while (it.hasNext()) {
            System.out.print(it.next()+" ");
        }
        System.out.println();
        System.out.println("*******");
        //使用迭代器——反向遍历
        ListIterator<Integer> it2 = list.listIterator(list.size());
        while (it2.hasPrevious()) {
            System.out.print(it2.previous()+" ");
        }
        System.out.println();
    }
}

在这里插入图片描述

四、ArrayList和LinkedList的区别

1.ArrayList在物理上是连续的，LinkedList在逻辑上连续，但在物理上不一定连续
2.ArrayList和LinkedList是两种不同的数据结构。ArrayList是基于动态数组的，而LinkedList则是基于链表的
3.当需要随机访问元素（如get和set操作）时，ArrayList效率更高，因为LinkedList需要逐个查找。但当进行数据的增加和删除操作（如add和remove操作）时，LinkedList效率更高，因为ArrayList在进行这些操作时需要移动大量数据
4.ArrayList需要手动设置固定大小的容量，使用方便但自由性低；而LinkedList能够随数据量变化而动态调整，自由性较高但使用较为复杂

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

如若内容造成侵权/违法违规/事实不符，请联系我们进行投诉反馈qq邮箱809451989@qq.com，一经查实，立即删除！

相关文章

spring 笔记三 Spring与Web环境集成

spring 笔记三 Spring与Web环境集成

文章目录 Spring与Web环境集成ApplicationContext应用上下文获取方式导入Spring集成web的坐标置ContextLoaderListener监听器通过工具获得应用上下文对象SpringMVC概述SpringMVC快速入门 Spring与Web环境集成 ApplicationContext应用上下文获取方式 应用上下文对象是通过new …
阅读更多...
leetcode面试经典150题——36 旋转图像

leetcode面试经典150题——36 旋转图像

题目&#xff1a; 旋转图像 描述&#xff1a; 给定一个 n n 的二维矩阵 matrix 表示一个图像。请你将图像顺时针旋转 90 度。 你必须在 原地 旋转图像&#xff0c;这意味着你需要直接修改输入的二维矩阵。请不要 使用另一个矩阵来旋转图像。 示例 1&#xff1a; 输入&#x…
阅读更多...
中国经济增长：全球复苏的引擎

中国经济增长：全球复苏的引擎

近年来&#xff0c;中国经济以其强劲的增长势头成为全球经济的重要引擎。中国的经济崛起不仅对自身国家发展具有重要意义&#xff0c;而且也对全球经济复苏和稳定有着积极影响。本文将从多个角度探讨中国经济增长对全球经济的影响及其作为全球复苏的引擎。 首先&#xff0c;中国…
阅读更多...
《使用ThinkPHP6开发项目》 - ThinkPHP6使用JWT生成Token

《使用ThinkPHP6开发项目》 - ThinkPHP6使用JWT生成Token

《使用ThinkPHP6开发项目》 - 登录接口一-CSDN博客 《使用ThinkPHP6开发项目》 - 登录接口二-CSDN博客 《使用ThinkPHP6开发项目》 - 登录接口三【表单验证】-CSDN博客 登录接口成功后返回Token&#xff0c;便于其他需要验证用户登录的接口携带Token进行请求校验 这里Think…
阅读更多...
基于ssm网络安全宣传网站设计论文

基于ssm网络安全宣传网站设计论文

摘 要 现代经济快节奏发展以及不断完善升级的信息化技术&#xff0c;让传统数据信息的管理升级为软件存储&#xff0c;归纳&#xff0c;集中处理数据信息的管理方式。本网络安全宣传网站就是在这样的大环境下诞生&#xff0c;其可以帮助管理者在短时间内处理完毕庞大的数据信息…
阅读更多...
SI24R03国产自主可控RISC-V架构MCU低功耗2.4GHz收发芯片SoC

SI24R03国产自主可控RISC-V架构MCU低功耗2.4GHz收发芯片SoC

目录 RISC-V架构的优势SI24R03/04特性射频收发器模块特征MCU 模块特征 其他特征 RISC-V架构的优势 相对于目前主流的英特尔X86架构及ARM等架构来说&#xff0c;RISC-V架构具有指令精简、模块化、可扩展、开源、免费等优点。RISC-V的基础指令集只有40多条&#xff0c;加上其他基…
阅读更多...
爬虫的分类

爬虫的分类

爬虫的分类 网络爬虫按照系统结构和实现技术&#xff0c;大致可分为4类&#xff0c;即通用网络爬虫、聚焦网络爬虫、增量网络爬虫和深层次网络爬虫。 1.通用网络爬虫&#xff1a;搜索引擎的爬虫 比如用户在百度搜索引擎上检索对应关键词时&#xff0c;百度将对关键词进行分析…
阅读更多...
比特币价格创新高：加密货币的崛起与未来

比特币价格创新高：加密货币的崛起与未来

一、引言 近年来&#xff0c;比特币的价格一路上涨&#xff0c;引起了全球投资者和市场的广泛关注。作为最早一批区块链技术应用案例之一&#xff0c;比特币的成功带动了整个加密货币市场的兴起。本文将探讨比特币价格创新高的原因、加密货币的崛起以及未来发展趋势。 二、比特…
阅读更多...
ChatGPT热门项目

ChatGPT热门项目

1.智能GPT 项目地址&#xff1a;智能GPT&#xff1a;你只要提供OpenAI的API Key&#xff0c;那么它就可以根据你设定的目标&#xff0c;采用Google搜索、浏览网站、执行脚本等方式 主要语言&#xff1a;Python 推荐理由&#xff1a;这是由开发者Significant Gravitas推出的项目…
阅读更多...
【C++练级之路】【Lv.4】类和对象（下）（初始化列表，友元，static成员，编译器的优化）

【C++练级之路】【Lv.4】类和对象（下）（初始化列表，友元，static成员，编译器的优化）

目录 一、再谈构造函数1.1 构造函数体赋值1.2 初始化列表1.3 explicit关键字 二、static成员2.1 概念2.2 特性 三、友元3.1 引入3.2 友元函数3.2.1 概念3.2.2 特性 3.3 友元类3.3.1 概念3.3.2 特性 四、内部类4.1 概念4.2 特性 五、匿名对象六、编译器的优化6.1 传参优化6.1.1 …
阅读更多...
Java EE 网络之网络初识

Java EE 网络之网络初识

文章目录 1. 网络发展史1.1 独立模式1.2 网络互连1.3 局域网 LAN1.4 广域网 WAN 2. 网络通信基础2.1 IP 地址2.2 端口号2.3 认识协议2.4 五元组2.5 协议分层2.5.1 什么是协议分层2.5.2 分层的作用2.5.3 OSI七层协议2.5.4 TCP/IP五层协议2.5.5 网络设备所在分层 2.6 分装和分用 …
阅读更多...
简单的教务系统

简单的教务系统

#include <stdio.h> #include <string.h> #define N 20 int i,j,n,m,lll0,renshu6; double zcj[N]{0};struct stu{ char num[10]; //学号char name[10]; //姓名char sex; //姓别double score[3]; //3 门课的成绩double sum; //3 门课的总分double aver; //3 门课的…
阅读更多...
【深度学习目标检测】五、基于深度学习的安全帽识别（python，目标检测）

【深度学习目标检测】五、基于深度学习的安全帽识别（python，目标检测）

深度学习目标检测方法则是利用深度神经网络模型进行目标检测&#xff0c;主要有以下几种&#xff1a; R-CNN系列&#xff1a;包括R-CNN、Fast R-CNN、Faster R-CNN等&#xff0c;通过候选区域法生成候选目标区域&#xff0c;然后使用卷积神经网络提取特征&#xff0c;并通过分类…
阅读更多...
超聚变服务器（原华为服务器）网站模拟器

超聚变服务器（原华为服务器）网站模拟器

一、超聚变服务器&#xff08;原华为服务器&#xff09;网站模拟器&#xff1a; 原来了解服务器可以从他的网站上进行了解&#xff0c;模拟器做的很好了。 https://support.xfusion.com/server-simulators/ 有很多的模拟器&#xff0c;今天主要看下BMC的设置 有很多的在线工具…
阅读更多...
vue中element-ui日期选择组件el-date-picker 清空所选时间，会将model绑定的值设置为null 问题 及 限制起止日期范围

vue中element-ui日期选择组件el-date-picker 清空所选时间，会将model绑定的值设置为null 问题 及 限制起止日期范围

一、问题 在Vue中使用Element UI的日期选择组件 <el-date-picker>&#xff0c;当你清空所选时间时&#xff0c;组件会将绑定的 v-model 值设置为 null。这是日期选择器的预设行为&#xff0c;它将清空所选日期后将其视为 null。但有时后端不允许日期传空。 因此&#xff…
阅读更多...
生产实践：基于K8S的私有化部署解决方案

生产实践：基于K8S的私有化部署解决方案

随着国内数字化转型的加速和国产化进程推动&#xff0c;软件系统的私有化部署已经成为非常热门的话题&#xff0c;因为私有化部署赋予了企业更大的灵活和控制权&#xff0c;使其可以根据自身需求和安全要求定制和管理软件系统。下面分享下我们的基于k8S私有化部署经验。 私有化…
阅读更多...
AR眼镜光学方案_AR眼镜整机硬件定制

AR眼镜光学方案_AR眼镜整机硬件定制

增强现实(Augmented Reality&#xff0c;AR)技术通过将计算机生成的虚拟物体或其他信息叠加到真实世界中&#xff0c;实现对现实的增强。AR眼镜作为实现AR技术的重要设备&#xff0c;具备虚实结合、实时交互的特点。为了实现透视效果&#xff0c;AR眼镜需要同时显示真实的外部世…
阅读更多...
【WebRTC】用WebRTC做即时视频聊天应用

【WebRTC】用WebRTC做即时视频聊天应用

【配套项目源码】 打开即用，设置一个免费的Agora账户就可以实现视频电话。非常好的WebRTC学习和应用项目。 用VSCode打开即可。 https://download.csdn.net/download/weixin_41697242/88630069 【什么是WebRTC？】 WebRTC是一套基于JS的API，能够建立端对端的直接通信，实…
阅读更多...
服务器上配置jupyter，提示Invalid credentials如何解决

服务器上配置jupyter，提示Invalid credentials如何解决

我是按照网上教程在服务器上安装的jupyter以及进行的密码配置&#xff0c;我利用 passwd()这个口令生成的转译密码是"argon...."。按照教程配置jupyter notebook配置文件里面的内容&#xff0c;登陆网页提示"Invalid credentials"。我谷歌得到的解答是&…
阅读更多...
如何学习Kubernetes，学习K8S入门教程

如何学习Kubernetes，学习K8S入门教程

学习 Kubernetes&#xff08;K8s&#xff09;确实不容易 你的硬件资源有限时&#xff0c;不过别担心&#xff0c;我帮你理清思路&#xff0c;让你在学习 K8s 的路上更加从容。 1、资源限制下的学习方法 当硬件资源有限时&#xff0c;一个好的选择是使用云服务提供的免费层或者…
阅读更多...
最新文章

Copyright @ 2022~2023