数据结构-链表结构-单向链表

链表结构

说到链表结构就不得不提起数据结构,什么是数据结构?就是用来组织和存储数据的某种结构。那么到底是某种结构呢?

数据结构分为:

  • 线性结构
    • 数组,链表,栈,队列
  • 树形结构
    • 二叉树,B树,红黑树等
  • 图形结构
    • 邻接矩阵,邻接表等

那么链表就是我们这本文的主角,之前其实我们都接触过链表就是集合中基于List实现的linkedlist,但是在练习的过程中我发现好多同志只会用,不知道其中原理,知其然而不知其所以然。但是也会有同志说了我会用不就不就醒了,各位凡是要做到精益求精,知其然跟要知其所以然。为实现科技报国我们的祖国就需要这种人才,一起创新创建共创科技大国。

链表结构的定义

什么是链表

在逻辑结构上一个挨一个的数据,但是在实际存储时所在的内存地址却并不连续,相反数据随机分布在内存中的各个位置。

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-Uo1YfDER-1690775932877)(E:\Java笔记\数据结构\线形结构\链表结构.assets\image-20230731093517699.png)]

通过数据的指针指向下一个数据,这种存储结构称为链式存储,而这种链式存储所生成的表就是链表

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-63Npk2QJ-1690775932878)(E:\Java笔记\数据结构\线形结构\链表结构.assets\image-20230731093456452.png)]

链表分类

  • 单向链表
  • 双向链表
  • 双向循环链表

单向链表

什么是单向链表

上面说到了什么是链表,那么在单向链表中我们将数据分为两个区域

  • 数据域:存储数据
  • 指针域:存储下一个节点的内存地址
    [外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-WFVtGpFY-1690775932878)(E:\Java笔记\数据结构\线形结构\链表结构.assets\image-20230731095437329.png)]

在链表中它有一个专业名字叫做:节点。

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-4HrBVGMO-1690775932879)(E:\Java笔记\数据结构\线形结构\链表结构.assets\image-20230731095418610.png)]

一个节点指向下一个节点,这种链式结构称为单向链表

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-DaVYtHbB-1690775932879)(E:\Java笔记\数据结构\线形结构\链表结构.assets\image-20230731095536584.png)]

在单向链表中,链表的第一个节点称为首元节点

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-LVWMVy6h-1690775932880)(E:\Java笔记\数据结构\线形结构\链表结构.assets\image-20230731095809932.png)]

链表的最后一个节点称为尾节点

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-RExs1D0C-1690775932880)(E:\Java笔记\数据结构\线形结构\链表结构.assets\image-20230731095856557.png)]

中间的这个节点的前一个节点称为前驱
在这里插入图片描述

中间的这个节点的后一个节点称为后继

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-mg6JU2zh-1690775932881)(E:\Java笔记\数据结构\线形结构\链表结构.assets\image-20230731100047613.png)]

通常在链表的前面会有一个节点称为头节点,当然头节点不是必须存在的。

  • 头节点的作用是:用来存储链表的长度

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-jXLTPxvG-1690775932882)(E:\Java笔记\数据结构\线形结构\链表结构.assets\image-20230731100239606.png)]

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-29rianmB-1690775932882)(E:\Java笔记\数据结构\线形结构\链表结构.assets\image-20230731100320069.png)]

在每一个链表中都会配备一个头指针,指针始终指向第一个节点,如果有链表中配备头节点则指向头节点,如果没有配备头节点则指向首元节点

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-dTTJDnYf-1690775932883)(E:\Java笔记\数据结构\线形结构\链表结构.assets\image-20230731100533063.png)]

头指针的定义是:用于在链表中挪动指针查找数据,直到找到对应的数据

在这里插入图片描述

单向链表的功能

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-FPscmp6z-1690775932884)(E:\Java笔记\数据结构\线形结构\链表结构.assets\image-20230731103625505.png)]

    • 向链表的尾节点添加节点

      • 将新添加节点的内存地址存放到该链表尾节点的指针域中。通俗的讲:将尾节点的指针域指向新添加的节点

      • 此时尾节点就是新添加的这个节点

        [外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-EOecEUmO-1690775932884)(E:\Java笔记\数据结构\线形结构\链表结构.assets\20230731_104622.gif)]

    • 向链表的首元节点之前添加节点

      • 将链表的首元节点的内存地址存放到新添加节点的指针域中。通俗的讲:新节点的指针指向首元节点

      • 此时首元节点是新添加的这个节点

        [外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-NGbrG5IA-1690775932885)(E:\Java笔记\数据结构\线形结构\链表结构.assets\20230731_105455.gif)]

    • 向链表中间添加节点

      • 将新添加节点的内存地址存放到前驱的指针域中,新添加节点的指针域存放后继的内存地址。通俗的讲:修改前驱的指针方向指向新添加的节点,新添加的节点执行后继即可

      [外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-4JmT2yty-1690775932885)(E:\Java笔记\数据结构\线形结构\链表结构.assets\20230731_110227.gif)]

    • 删除尾节点

      • 尾节点的前驱的指针域不在存储尾节点的内存地址。通俗的讲:尾节点的指针域不在指向尾节点
    • 删除首元节点

      • 首元节点的指针域不存放后继的内存地址。通俗的讲:首元节点的指针与不在指向后继节点
    • 删除中间的某个节点

      • 删除节点的前驱指针域不再存放删除节点的内存地址,删除节点的指针域不再存储后继的内存地址,通俗的讲:删除节点的前驱指向删除节点的后继

        [外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-jK3f0kcV-1690775932886)(E:\Java笔记\数据结构\线形结构\链表结构.assets\20230731_110948-16907732210771.gif)]

      注意:被删除的节点称之为:野节点,这并不是真正意义上的删除,它在内存中依旧存在。那么野节点的最终归宿是被JVM的GC(垃圾回收器)所回收,也就是释放该节点的内存空间,这才是真正意义上的删除

      额外知识:java中的垃圾回收器(Garbage Collector,GC)负责管理内存的分配和释放。当一个对象没有任何引用指向它时,它就变得不可达,而垃圾回收器会将其标记为垃圾对象,并在适当的时候回收该对象所占用的内存空间。这个过程称为垃圾回收。

    • 挪动指针找到要修改的节点,之后讲修改节点的数据域中的数据修改掉
    • 挪动指针找到要所要查找的数据。

特点

  • 节点在存储器中的位置是任意的,即逻辑上相邻的数据元素在物理上不一定相邻。

  • 数据元素的个数可以自由扩充,插入,删除,只需要修改节点的指针方向,效率高

  • 修改和查找节点数据需要挪动指针,按照节点的顺序进行依次查找或者修改,效率比较低

与数组的区别

回顾数组

数组的功能

    • 数据不能超过定义的数组长度
    • 数据少于定义数组的长度会造成内存浪费
    • 数组中间添加数据会将之后的数据内存位置往后挪动

    [外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-rbC5fv9m-1690775932886)(E:\Java笔记\数据结构\线形结构\链表结构.assets\20230731_115259.gif)]

区别

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-kpln7pfQ-1690775932886)(E:\Java笔记\数据结构\线形结构\链表结构.assets\image-20230731115828188.png)]

实现单项链表

MyList
/**
 * @CreateName SIN
 * @CreateDate 2023/07/27 16:28
 * @description 定义链表功能规范,避免子类编码随意性。同时也实现了程序的解耦,提高代码的可维护性。
 */
//泛型E任何数据类型
public interface MyList<E> {
    //添加节点数据
    void add(E element);
    //获取节点数据(根据具体的指针找到对应的数据)
    E get(int index);
    //获取链表的长度
    int size();
    //根据指针移除节点
    E remove(int index);
    //修改节点数据
    E set(int index,E element);
}

MyLinkedList
package com.sin.linkedList;

/**
 * @CreateName SIN
 * @CreateDate 2023/07/27 16:35
 * @description
 */
public class MyLinkedList<E> implements MyList<E>{

    // 存放链表的头节点
    private Node head;

    // 记录链表的长度
    private int size;

    /**
     * 向链表中添加节点
     * @param element 添加的节点
     */
    @Override
    public void add(E element) {
        //创建一个新的节点,存储传入的元素
        Node<E> node = new Node<E>(element,null);
        //获取链表尾节点
        Node tail = getTail();
        //如果链表为空,
        if (tail == null){
            //将新节点设置为头节点
            this.head = node;
        }else{
            //否则,在尾节点后面添加新节点
            tail.next = node;
        }
        //记录元素的个数
        this.size++;
    }

    /**
     * 获取尾节点
     * @return 返回尾节点
     */
    private Node getTail(){
        //判断当前头节点是否为空
        if(this.head == null){
            return null;
        }
        //遍历链表
        //从头节点开始遍历链表
        Node node = this.head;
        while (true){
            //如果下一个节点为空,则表示当前节点为尾节点,则跳出循环
            if(node.next == null){
                break;
            }
            //在循环的过程中,移动指针,指向下一个节点
            node = node.next;
        }
        //返回尾节点
        return node;
    }

    /**
     * 根据指针获取节点数据
     * @param index
     * @return 返回节点数据
     */
    @Override
    public E get(int index) {
        //1,校验index的合法性
        pointerIndex(index);
        //2,根据具体位置获取对应的节点数据
        Node<E> node = getNode(index);
        //3,将节点中的元素返回
        return node.item;
    }

    /**
     * 校验所给定的指针是否在链表的有效范围内
     * @param index
     */
    private void pointerIndex(int index){
        // 大于等于0并且小于链表长度
        if (!(index >= 0 && index < this.size)){
            //获取最大的索引指
            int a = this.size-1;
            // 抛出索引越界异常,显示错误信息
            throw new IndexOutOfBoundsException("你输入的指针为:"+index + "最大指针为:"+a);
        }
    }

    /**
     * 根据指针获取节点
     * @return 返回给定索引处的节点
     */
    private Node getNode(int index){
        //从头节点开始遍历链表
        Node<E> node = this.head;
        //移动指针,指向下一个节点,直到所给定的索引位置
        for (int i = 0;i< index;i++){
            node = node.next;
        }
        //返回给定索引处的节点
        return node;
    }

    @Override
    public int size() {
        return this.size;
    }

    @Override
    public E remove(int index) {
        //校验index的合法性
        this.pointerIndex(index);

        //根据index指针找到该节点对象数据
        Node<E> node = this.getNode(index);
        //获取该节点对象中的元素
        E item = node.item;
        //向该节点对象中单向链表删除

        //判断当前删除的节点是否为头节点
        if (this.head == node){
            this.head = node.next;//如果是删除头节点,头节点的下一个节点,赋值给了头节点
        }else {
            Node<E> node1 = this.head;//拿头节点
            for (int i = 0 ; i<index - 1 ; i++){
                node1=node1.next;
            }
            node1.next = node.next;//将节点的下一个节点赋值给该节点
        }
        node.next = null;

        this.size -- ;//删除成功长度减一

        return item;//返回元素
    }

    /**
     * 修改节点数据
     * @param index 挪动指针
     * @return 返回修好的值
     */
    @Override
    public E set(int index,E element) {
        //校验index的合法性
        pointerIndex(index);
        //获取index处的节点
        Node<E> node = getNode(index);
        //将节点值数据进行赋值替换
        return node.item = element;
    }
    /**
     * 使用内部类定义单向链表中的节点对象
     *
     */
    class Node<E>{
        //数据域
        private E item;//存储的数据

        //指针域
        private Node next;//存储下一个节点对象的地址

        //无参构造方法
        public Node(){

        }
        //全参构造方法
        public Node(E item,Node next){
            this.item = item;
            this.next = next;
        }

    }
}

测试
public static void main(String[] args) {
    MyLinkedList myLinkedList = new MyLinkedList();

    myLinkedList.add(12);
    myLinkedList.add(13);
    myLinkedList.add(14);
    myLinkedList.add(15);
    myLinkedList.add(16);
    System.out.println("根据指针找到值"+myLinkedList.get(4));
    System.out.println("删除的节点"+myLinkedList.remove(0));
    System.out.println(myLinkedList);
    System.out.println(myLinkedList.size());
    System.out.println(myLinkedList.set(3,"张三");


    for (int i=0;i<myLinkedList.size(); i++){

        System.out.print(myLinkedList.get(i)+",");
    }

}

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

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

相关文章

P1219 [USACO1.5] 八皇后 Checker Challenge

题目 思路 非常经典的dfs题&#xff0c;需要一点点的剪枝 剪枝①&#xff1a;行、列&#xff0c;对角线的标记 剪枝②&#xff1a;记录每个皇后位置 代码 #include<bits/stdc.h> using namespace std; const int maxn105; int a[maxn];int n,ans; bool vis1[maxn],vis…

解决:请求的资源[/xxx/]不可用 描述 源服务器未能找到目标资源的表示或者是不愿公开一个已经存在的资源表示。

1. 复现错误 今天启动jsp servlet项目&#xff0c;却报出如下错误&#xff1a; 2. 分析问题 报出该错误&#xff0c;一般是tomcat无法访问webapp下的文件&#xff0c;特采用如下方法解决问题。 检查涉及到jdk的版本号是否一致&#xff0c;我的是1.8的版本&#xff0c;所以&am…

AI革命:揭开微软无与伦比的AI技术面纱

来源&#xff1a;猛兽财经 作者&#xff1a;猛兽财经 2023年7月25日&#xff0c;全球科技行业的领导者之一微软(MSFT)公布了其2023财年第四季度的财报。 除了举世闻名的Windows操作系统&#xff0c;微软还通过笔记本电脑、个人电脑和服务器等产品改变了世界&#xff0c;该公司…

QMessageBox类

QMessageBox类 静态方法例子 静态方法 调用这一些静态成员函数&#xff0c;就可以得到模态提示框 枚举值为&#xff1a; 例子 头文件&#xff1a; #ifndef MAINWINDOW_H #define MAINWINDOW_H#include <QMainWindow> #include <QMessageBox>QT_BEGIN_NAMESPACE…

gorm基础

Gorm 官方文档&#xff1a;https://gorm.io/zh_CN/ 安装 go get -u github.com/jinzhu/gorm连接数据库 连接不同的数据库都需要导入对应数据的驱动程序&#xff0c;GORM已经贴心的为我们包装了一些驱动程序&#xff0c;只需要按如下方式导入需要的数据库驱动即可&#xff1…

Android Studio 关于BottomNavigationView 无法预览视图我的解决办法

一、前言&#xff1a;最近在尝试一步一步开发一个自己的软件&#xff0c;刚开始遇到的问题就是当我们引用 com.google.android.material.bottomnavigation.BottomNavigationView出现了无法预览视图的现象&#xff0c;我也在网上查了很多中解决方法&#xff0c;最后在执行了如下…

会议oa系统项目部署流程

目录 1.项目部署环境 2.初始化数据库 2.1获取数据库脚本 2.2创建数据库 1.创立数据库连接 2.创建数据库&#xff0c;命名 3.运行sql文件 4.查看导入数据 ​编辑 ​编辑 3项目环境部署 3.1导入项目资源 3.2加载框架 加载成功标志 服务器配置&#xff08;用来保存排…

glide加载content://com.android.contacts图片源码粗略梳理

获取链路是这样的&#xff1b; UriLoader类里定义了协议头&#xff1a; 里面有个内部类StreamFactory&#xff1a; 通过StreamLocalUriFetcher类的loadResource方法获取InputStream然后把流转换成为图片&#xff1b; 在这里作个草稿笔记给自己看

数字IC验证高频面试问题整理附答案(二)

近日后台有同学私信还想要验证的面试题目&#xff0c;这不就来了~ Q16.权重约束中”:”和”: /”的区别 : 操作符表示值范围内的每一个值的权重是相同的,比如[1:3]:40,表示1&#xff0c;2&#xff0c;3取到的概率为40/120&#xff1b; :&#xff0f;操作符表示权重要平均分到…

企业级开发中协同开发与持续集成持续部署

文章目录 1 创建代码仓库2 使用git协同开发2.1 独立团队开发2.2 多团队开发git工作流 2 持续集成和持续部署2.1 创建docker镜像2.2 使用coding构建 1 创建代码仓库 每个项目有唯一的代码仓库&#xff0c;所以不是每个开发者都需要创建一个代码仓库&#xff0c;一般都是项目负责…

力扣每日一题--2050. 并行课程 III(拓补排序例题)

题目传送门 题目描述&#xff1a; 给你一个整数 n &#xff0c;表示有 n 节课&#xff0c;课程编号从 1 到 n 。同时给你一个二维整数数组 relations &#xff0c;其中 r e l a t i o n s [ j ] [ p r e v C o u r s e j , n e x t C o u r s e j ] relations[j] [prevCours…

第五章 HL7 架构和可用工具 - 创建新的自定义架构

文章目录 第五章 HL7 架构和可用工具 - 创建新的自定义架构创建新的自定义架构定义新段 第五章 HL7 架构和可用工具 - 创建新的自定义架构 创建新的自定义架构 要从管理门户启动自定义架构编辑器&#xff0c;请从主页选择互操作性 > 互操作 > HL7 v2.x >HL7 v2.x 架…

Python-如何使用正则表达式

如何利用Python使用正则表达式 目录 正则表达式常用匹配规则 ​编辑re库的使用 match()方法&#xff1a; search()方法: findall()方法 : sub()方法: compile()方法; 通用匹配 贪婪与非贪婪匹配 贪婪匹配 非贪婪匹配 修饰符 转义匹配 正则表达式是处理字符的强大…

RabbitMQ 教程 | 第5章 RabbitMQ 管理

&#x1f468;&#x1f3fb;‍&#x1f4bb; 热爱摄影的程序员 &#x1f468;&#x1f3fb;‍&#x1f3a8; 喜欢编码的设计师 &#x1f9d5;&#x1f3fb; 擅长设计的剪辑师 &#x1f9d1;&#x1f3fb;‍&#x1f3eb; 一位高冷无情的编码爱好者 大家好&#xff0c;我是 DevO…

MATLAB | 如何绘制这样的描边散点图?

part.-1 前前言 最近略忙可能更新的内容会比较简单&#xff0c;见谅哇&#xff0c;今日更新内容&#xff1a; part.0 前言 看到gzhBYtools科研笔记(推荐大家可以去瞅瞅&#xff0c;有很多有意思的图形的R语言复现&#xff01;&#xff01;)做了这样一张图&#xff1a; 感觉很…

【论文阅读24】Better Few-Shot Text Classification with Pre-trained Language Model

论文相关 论文标题&#xff1a;论文标题&#xff1a;Label prompt for multi-label text classification&#xff08;基于预训练模型对少样本进行文本分类&#xff09; 发表时间&#xff1a;2021 领域&#xff1a;多标签文本分类 发表期刊&#xff1a;ICANN&#xff08;顶级会…

CASAIM自动化平面度检测设备3D扫描零部件形位公差尺寸测量

平面度是表面形状的度量&#xff0c;指示沿该表面的所有点是否在同一平面中&#xff0c;当两个表面需要连接在一起形成紧密连接时&#xff0c;平面度检测至关重要。 CASAIM自动化平面度检测设备通过搭载领先的激光三维测头和智能检测软件自动获取零部件高质量测量数据&#xf…

【LeetCode】最小路径和

最小路径和 题目描述算法流程编程代码 链接: 最小路径和 题目描述 算法流程 编程代码 class Solution { public:int minPathSum(vector<vector<int>>& grid) {int m grid.size();int n grid[0].size();vector<vector<int>> dp(m1,vector<in…

Ae 效果:CC Kernel

颜色校正/CC Kernel Color Correction/CC Kernel CC Kernel&#xff08;CC 卷积核&#xff09;效果主要用于图像的卷积处理&#xff0c;通过在卷积矩阵中设置不同的权重值&#xff0c;可以实现图像的锐化 Sharpen、模糊 Blur、查找边缘 Find Edges以及浮雕 Emboss等效果。 ◆ …

<C语言> 预处理和宏

1.预定义符号 __FILE__ //进行编译的源文件 __LINE__ //文件当前的行号 __DATE__ //文件被编译的日期 __TIME__ //文件被编译的时间 __STDC__ //如果编译器遵循ANSI C&#xff0c;其值为1&#xff0c;否则未定义这些预定义符号都是C语言内置的。 举个例子&…