Java语言----LinkedList 和 链表的实现

简介: Java语言----LinkedList 和 链表的实现

😽个人主页: tq02的博客_CSDN博客-C语言,Java,Java数据结构领域博主

🌈梦的目标:努力学习,向Java进发,拼搏一切,让自己的未来不会有遗憾。

🎁欢迎各位→点赞👍 + 收藏⭐ + 评论📝+关注✨

 本章讲解内容:链表 的讲解

48b44c8bb51a4c12b587a22f8f6c26d1.jpg

使用编译器:IDEA

一.链表概念


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

逻辑结构:

b0f702ca1109492e9a6ccc803fba66e5.png


注:1、如上图,相当于火车车厢,每一节都相连在一起。


      2、各个结点连接的方式:通过地址连接,在内存当中,相邻结点在内存中不一定相邻。


      3、所有结点都在  堆 中申请出来。


      4、 每个结点包括两个部分:一个是存储数据元素的数据域,另一个是存储下一个结点地址的指针域。


二.链表的分类


1.单向、双向链表

d0184c0358984cf095ebb4557fb01148.png


注:无论单向还是双向,都是一个结点存储着下(上)一个结点。

2.带头、不带头结点 链表


02580c9c547e44379042a749c90a3844.png


注:无头和带头结点的主要区别:有一个起始结点。

3.循环、非循环链表


c8cf0cd1421d431ca3c8d48edc6041ee.png



循环链表,就是指:头、尾结点有联系。


      在链表结构中,这是主要的链表,但是这些链表种类还可以结合,如:带头双向循环链表、双向循环链表等等。


链表的种类很多,但都大同小异,我们主要学习两种链表:


   1、无头单向非循环链表:结构简单,一般不会单独用来存数据。实际中更多是作为其他数据结构的子结构,如哈希桶、图的邻接表等等。另外这种结构在笔试面试中出现很多。              2、无头双向链表:在Java的集合框架库中LinkedList底层实现就是无头双向循环链表


三.无头单向非循环链表的实现


3.1创建简单链表


d7e0459971e940e68b7c99a7c7bf32e7.png


重点:每个结点存储着下一个结点的地址。

创建链表代码实现:

public class SingleLinkedList {
      static class List{
        int item;   //  存储数据
        List next;   // 指向下一个结点
        public List(int item) {
            this.item = item;
        }
        public List() {};
    }
//各种链表实现方法
//头插法
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){
}
    //得到单链表的长度
public int size(){
    return -1;
}
    //链表的清空
public void clear() {
}
    //展示链表
public void display() {}


3.2 链表基本方法实现

1.遍历链表元素

public void show() {
        //这里不是定义了一个节点 这里只是一个引用
        ListNode cur = head;
        while (cur != null) {
            System.out.print(cur.val+" ");
            cur = cur.next;
        }
        System.out.println();
    }


2.获取链表长度

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


3.查询数据

public boolean contains(int key){
        ListNode cur = head;
        while (cur != null) {
            //如果val值 是引用类型  那么这里得用equals来进行比较!!!
            if(cur.val == key) {
                return true;
            }
            cur = cur.next;
        }
        return false;
    }


4.链表的清空

public void clear() {
        //将所有结点都置空,更为安全
        while (head != null) {
            ListNode headNext = head.next;
            head.next = null;
            head = headNext;
        }
    }


3.3四大基本功能

     3.3.1 、增加元素结点

 1.头插法:将新增结点放在链表的头部。

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


2.尾插法:将新增结点直接连接在链表的尾部


 public 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 指向的节点就是尾巴节点
        cur.next = node;
    }


3.选择下标值,添加结点

 public void addIndex(int index,int data){
        int len = size();
        //0、判断index位置的合法性
        if(index < 0 || index > len) {
            throw new IndexOutOfBounds("任意位置插入数据的时候,index位置不合法: "+index);
        }
        if(index == 0) {
            addFirst(data);
            return;
        }
        if(index == len) {
            addLast(data);
            return;
        }
        //1、先找到index-1位置的节点
        ListNode cur = findIndex(index);
        //2、进行插入
        ListNode node = new ListNode(data);
        node.next = cur.next;
        cur.next = node;
}


3.3.2.查找元素结点

查找一个元素,返回对应的下标值。

 public ListNode findIndex(int index) {
        ListNode cur = head;
        while (index - 1 != 0) {
            cur = cur.next;
            index--;
        }
        return cur;//index-1位置的节点
    }



3.3.3.删除元素结点


先找到对应的下标值,然后进行删除。删除方法,前一个结点连接到删除结点的后一个结点。

3d1d387d2ef048bdacc8e78bbf969130.png


如图,先断开d2与d3的连接,然后d2直接连接d4

代码实现:

//删除第一次出现关键字为key的节点
    public void remove(int key){
        if(head == null) {
            return;
        }
        //当删除结点为头结点
        if(head.val == key) {
            head = head.next;
            return;
        }
        ListNode prev = searchPrev(key); //返回待删除结点的前一个结点
        if(prev == null) {
            System.out.println("没有这个数据!");
            return;
        }
        ListNode del = prev.next;
        prev.next = del.next;
    }
    private ListNode searchPrev(int key) {
        ListNode prev = head;
        while (prev.next != null) {
            if(prev.next.val == key) {
                return prev;
            }else {
                prev = prev.next;
            }
        }
        return null;
    }


3.3.4.结点信息修改

修改指定下标值的结点元素

public void searchPrev(int num,int date) {
        ListNode prev = head;
       for(int i=0;i<num-1;i++) {
                prev = prev.next;  
        }
        prev.val=date;
    }


四.LinkedList是什么?


       LinkedList的底层是双向链表结构,由于链表没有将元素存储在连续的空间中,元素存储在单独的节点中,然后通过引用将节点连接起来了,因此在在任意位置插入或者删除元素时,不需要搬移元素,效率比较高。


5687bd7a23394845935fe037bfc56b59.png



如图所示:1. LinkedList实现了List接口

                  2. LinkedList的底层使用了双向链表

                  3. LinkedList没有实现RandomAccess接口,因此LinkedList不支持随机访问。                                 4. LinkedList的任意位置插入和删除元素时效率比较高,时间复杂度为O(1)

                  5. LinkedList比较适合任意位置插入的场景


五.LinkedList使用方法



方法
解释
   构造方法 LinkedList()    无参构造
public LinkedList(Collection<? extends E> c) 使用其他集合容器中元素构造List
常用方法 boolean add(E e) 尾插e
void add(int index,E element) 将e插入到index位置
boolean addAII(Collection<? extends E> c) 尾插c中的元素

E remove(int index)


删除index位置元素

boolean remove(Object o)

删除遇到的第一个o
E get( int index) 获取下标index位置元素
void clear() 清空


总结


        链表入门很简单,但是却有很多很难的题目,而我们只有将这些题目全部掌握了,对之后的栈、堆等题有更加深刻的知识。


题目推荐:1、移除链表元素        2、反转单链表       3、返回链表中间节点                                


                4、 合并两个有序链表       5、 合并两个有序链表       6. 相交链表       7、回文链表

目录
相关文章
|
6月前
|
人工智能 安全 Java
智慧工地源码,Java语言开发,微服务架构,支持分布式和集群部署,多端覆盖
智慧工地是“互联网+建筑工地”的创新模式,基于物联网、移动互联网、BIM、大数据、人工智能等技术,实现对施工现场人员、设备、材料、安全等环节的智能化管理。其解决方案涵盖数据大屏、移动APP和PC管理端,采用高性能Java微服务架构,支持分布式与集群部署,结合Redis、消息队列等技术确保系统稳定高效。通过大数据驱动决策、物联网实时监测预警及AI智能视频监控,消除数据孤岛,提升项目可控性与安全性。智慧工地提供专家级远程管理服务,助力施工质量和安全管理升级,同时依托可扩展平台、多端应用和丰富设备接口,满足多样化需求,推动建筑行业数字化转型。
212 5
|
3月前
|
监控 Java API
Java语言按文件创建日期排序及获取最新文件的技术
这段代码实现了文件创建时间的读取、文件列表的获取与排序以及获取最新文件的需求。它具备良好的效率和可读性,对于绝大多数处理文件属性相关的需求来说足够健壮。在实际应用中,根据具体情况,可能还需要进一步处理如访问权限不足、文件系统不支持某些属性等边界情况。
209 14
|
4月前
|
Java 编译器 应用服务中间件
为什么说 Java 语言编译与解释并存的原因
在编程语言的世界里,Java以其独特的“编译与解释并存”特性独树一帜。这一特性不仅赋予了Java强大的跨平台能力,还使其在性能和灵活性上达到了很好的平衡。接下来,我们将深入探讨Java语言这一特性的本质、原理以及在实际应用中的体现。
97 6
|
3月前
|
JSON JavaScript 前端开发
Python+JAVA+PHP语言,苏宁商品详情API
调用苏宁商品详情API,可通过HTTP/HTTPS发送请求并解析响应数据,支持多种编程语言,如JavaScript、Java、PHP、C#、Ruby等。核心步骤包括构造请求URL、发送GET/POST请求及解析JSON/XML响应。不同语言示例展示了如何获取商品名称与价格等信息,实际使用时请参考苏宁开放平台最新文档以确保兼容性。
|
4月前
|
分布式计算 Java 大数据
Java 语言基础概念与常识之主要特点解析
Java是一种广泛应用于企业级开发、移动应用(如Android)、大数据处理及云计算等领域的编程语言。其核心特点包括跨平台性(一次编写,到处运行)、面向对象设计、自动垃圾回收、多线程支持和高性能表现。Java通过JVM实现跨平台,具备强大的健壮性和安全性,同时拥有丰富的标准库与活跃的开发者社区。本文深入解析Java的技术优势及其在电商系统、大数据处理和云计算中的实际应用,并提供相关面试资料供学习参考。
128 0
|
4月前
|
网络协议 安全 Java
实现Java语言的文件断点续传功能的技术方案。
像这样,我们就完成了一项看似高科技、实则亲民的小工程。这样的技术实现不仅具备实用性,也能在面对网络不稳定的挑战时,稳稳地、不失乐趣地完成工作。
253 0
|
6月前
|
Java
Java LinkedList集合的深度剖析
总的来说,我希望像说故事一样讲解Java LinkedList集合的使用和实现原理,让有些许枯燥的编程知识变得趣味盎然。在这个“公交车”故事中,你不仅熟悉了LinkedList集合的实现和使用,而且还更深入地理解了数据结构中的链表。链表可能会因为插入和删除的便利性而被选用,虽然它的查找效率并不高,但是在很多场景中仍然十分有效。这就像公交车,虽然它速度不快,但却是城市出行的重要工具。
86 8
|
8月前
|
存储 缓存 Java
java语言后台管理ruoyi后台管理框架-登录提示“无效的会话,或者会话已过期,请重新登录。”-扩展知识数据库中密码加密的方法-问题如何解决-以及如何重置若依后台管理框架admin密码-优雅草卓伊凡
java语言后台管理ruoyi后台管理框架-登录提示“无效的会话,或者会话已过期,请重新登录。”-扩展知识数据库中密码加密的方法-问题如何解决-以及如何重置若依后台管理框架admin密码-优雅草卓伊凡
823 3
java语言后台管理ruoyi后台管理框架-登录提示“无效的会话,或者会话已过期,请重新登录。”-扩展知识数据库中密码加密的方法-问题如何解决-以及如何重置若依后台管理框架admin密码-优雅草卓伊凡
|
7月前
|
存储 Java 数据安全/隐私保护
Java语言位运算符详解
Java语言提供了7种位运算符:按位与(&)、按位或(|)、按位异或(^)、取反(~)、左移(&lt;&lt;)、带符号右移(&gt;&gt;)和无符号右移(&gt;&gt;&gt;)。这些运算符主要用于对long、int、short、byte和char类型的数据进行二进制位级别的操作,不能用于double、float和boolean类型。文中详细讲解了每种运算符的规则和应用场景,并指出位运算在实际开发中有重要应用价值,不仅限于面试。
299 2
|
8月前
|
缓存 Java 应用服务中间件
java语言后台管理若依框架-登录提示404-接口异常-系统接口404异常如何处理-登录验证码不显示prod-api/captchaImage 404 (Not Found) 如何处理-解决方案优雅草卓伊凡
java语言后台管理若依框架-登录提示404-接口异常-系统接口404异常如何处理-登录验证码不显示prod-api/captchaImage 404 (Not Found) 如何处理-解决方案优雅草卓伊凡
1345 5

热门文章

最新文章