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

这篇具有很好参考价值的文章主要介绍了Java语言----LinkedList 和 链表的实现。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

目录

一.链表概念

二.链表的分类 

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

3.1创建简单链表

3.2 链表基本方法实现

3.3四大基本功能

             3.3.1.增加元素结点

             3.3.2.查找元素结点

             3.3.3.删除元素结点

             3.3.4.结点信息修改

 

四.LinkedList是什么?

五.LinkedList使用方法

总结


😽个人主页: tq02的博客_CSDN博客-C语言,Java,Java数据结构领域博主
 🌈梦的目标:努力学习,向Java进发,拼搏一切,让自己的未来不会有遗憾。
 🎁欢迎各位→点赞👍 + 收藏⭐ + 评论📝+关注✨
  本章讲解内容:链表 的讲解

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

 

使用编译器:IDEA 

一.链表概念

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

逻辑结构:

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

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

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

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

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


二.链表的分类 

 1.单向、双向链表

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

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

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

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

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

3.循环、非循环链表 

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

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

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

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

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


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

3.1创建简单链表

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

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

创建链表代码实现:

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.删除元素结点

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

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

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

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

 如图所示: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、回文链表文章来源地址https://www.toymoban.com/news/detail-433527.html

到了这里,关于Java语言----LinkedList 和 链表的实现的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

  • C语言之单链表的实现以及链表的介绍

    因为我们常用的顺序表会存在以下的一些问题: 1. 中间/头部的插入删除,时间复杂度为O(N) 2. 增容需要申请新空间,拷贝数据,释放旧空间。会有不小的消耗。 3. 增容一般是呈2倍的增长,势必会有一定的空间浪费。例如当前容量为100,满了以后增容到 200,我们再继续插入了

    2024年02月01日
    浏览(45)
  • C语言/C++实现链表的详细教程

    1. 什么是链表 链表是一种常用的数据结构,它由一系列节点组成,每个节点包含两部分内容:数据和指向下一个节点的指针,最后一个节点指向空。链表的节点可以动态添加和删除,因此可以方便地进行插入、删除等操作。链表有多种类型,包括单向链表、双向链表和循环链

    2024年02月17日
    浏览(30)
  • 基于双向链表的通讯录C语言实现

    关于双向链表的详细了解请见博主的另一篇博客,本文旨在对单链表进行应用,采用C语言编写。

    2024年04月17日
    浏览(140)
  • [C语言][数据结构][链表] 双链表的从零实现!

    目录 零.必备知识 0.1 一级指针 二级指针 0.2 双链表节点的成员列表         a. 数据         b. 后驱指针         c. 前驱指针 0.3 动态内存空间的开辟 一. 双链表的实现与销毁         1.1 节点的定义         1.2 双向链表的初始化 创建新节点         1.3 尾插       

    2024年04月17日
    浏览(245)
  • [C语言][数据结构][链表] 单链表的从零实现!

    目录 零.必备知识 1.一级指针 二级指针 2. 节点的成员列表     a.数据     b.指向下一个节点的指针. 3. 动态内存空间的开辟 (malloc-calloc-realloc) 一.单链表的实现与销毁          1.1 节点的定义         1.2 单链表的尾插         1.3 单链表的头插         1.4 单链表的尾删  

    2024年04月11日
    浏览(76)
  • c语言数据结构——链表的实现及其基本操作

    顺序表的问题及思考 问题: 中间/头部的插入删除,时间复杂度为O(N) 增容需要申请新空间,拷贝数据,释放旧空间。会有不小的消耗。 增容一般是呈2倍的增长,势必会有一定的空间浪费。例如当前容量为100,满了以后增容到 200,我们再继续插入了5个数据,后面没有数据插

    2023年04月09日
    浏览(85)
  • Java中链表的实现(超详细)

            在Java中,链表可以通过 创建节点 和 链接节点 来实现。以下是一个简单的 链表实现 示例: 输出:         在这个示例中,我们创建了一个  LinkedList 类 ,它 包含一个 Node 类 和 一些方法 来操作链表。我们可以使用  push() 方法在链表的头部插入节点 ,使

    2024年02月14日
    浏览(42)
  • 数据结构——链表的实现(Java版)

    目录 一、链表 二、代码实现 1.创建结点 2.构造函数 3.链表的相关属性 4.添加虚拟节点 5.判断链表是否为空 6.添加方法 (1)在头部添加 (2)在尾部添加 (3)在索引位置添加 (4)对头插法和尾插法代码进行简化(调用任意位置添加的方法) 7.打印链表(遍历,重写toString方

    2024年01月23日
    浏览(50)
  • 链表——LinkedList类的概述和实现

    LinkedList类底层是基于双向链表结构实现的,不同于ArrayList类和Vector类是基于数组实现的; LinkedList类是非线程安全的; LinkedList类元素允许为null,允许重复元素; LinkedList类插入、删除效率高,查询效率低; LinkedList类基于链表实现的,因此不存在容量不足的问题,不用动态扩

    2024年02月14日
    浏览(49)
  • 数据结构_链表_双向循环链表的初始化、插入、删除、修改、查询打印(基于C语言实现)

    版本: 2024年4月26日 V1.0 发布于博客园 目录 目录 双向循环链表公式 初始化双向循环链表 构建双向循环链表结点 创建一个空链表(仅头结点) 创建一个新结点 插入数据 头插 中插 尾插 删除数据 头删 中删 尾删 查询打印数据 遍历打印 测试 测试结果: 完整代码 DoubleCirLList.h

    2024年04月27日
    浏览(55)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包