当前位置： 首页 > news >正文

LinkedList - 链表

news 来源：原创 2024/5/16 3:32:28

文章目录

  • 1. 链表
    • 1.1 链表的概念与结构
    • 1.2 链表的结构
  • 2. 链表实现
    • 2.1 打印链表
    • 2.2 返回链表长度
    • 2.3 查找 key 元素是否存在链表中
    • 2.4 新增方法 add
      • 2.4.1 头插
      • 2.4.2 尾插
      • 2.4.3 任意位置插入
    • 2.5 删除操作 remove
      • 2.5.1 删除第一次出现的 key 元素
      • 2.5.2 删除链表中所有的 key值
    • 2.6 清空操作
      • 2.6.1 粗暴一点的清空方法
      • 2.6.2 温柔一点的清空方法
  • 链表OJ题目

LinKedList与链表

 

1. 链表

 

1.1 链表的概念与结构

 
链表 ： 就像火车一样， 是节点(车厢)构成的 ， 每个节点之间会连接起来。

 
图示：

查看源图像

 
注意 ： 我们的链表 虽然 看起来是 节点上全部连接起来的如上面的火车一样一节一节的串起来，但是在物理的成面上， 链表其实是不连续的。

 
图解 ：

在这里插入图片描述

 
关于链表 ， 我们现在知道了他是，通过 next 域，来进行 连接的， 那么接下来我们来 了解一下我们 的 链表结构 ， 总共由 八种 ，但是不要担心 我们主要学两种即可 。

 

1.2 链表的结构

关于链表 ： 我们由 这几个 关键字 单向 , 双向 和 带头 , 不带头 还有 循环 , 不循环

将这几个关键字 排列组合 ，能得到以下

  • 单向带头不循环

  • 单向带头循环

  • 双向带头不循环

  • 双向带头循环

  • 单向不带头不循环

  • 单向不带头循环

  • 双向不带头不循环

  • 双向不带头循环

 
这里就 看到了我们 链表的 8种结构 ， 我们主要学习 单项不带头不循环 和 双向不带头不循环 因为后面我们面试中只要考察的是这两种。

 
2.1 单向带头不循环 和 单向不带头不循环
在这里插入图片描述

2.2 单向带头循环 和 单向不带头循环
在这里插入图片描述

 

2.3 双向带头不循环 和 双向不带头不循环

在这里插入图片描述

2.4 双向带头循环 和 双向不带头循环

 
这两个就跟 单向带头循环 和 单向不带头循环一样，只不过多了一个last 域而已

在这里插入图片描述

 
链表的结构看完， 那么我们下面继续 ， 这里还是通过实现 我们自己的链表 ， 来慢慢了解我们的链表。

 

2. 链表实现

 

主要实现的方法

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

 
这里我们先来创建 一个链表， 这里采用的 比较low 的方法， 直接穷举 。 (先不使用插入的方法)

 
第一步创建一个 MySingleList 类 并且在这个类里面创建一个 内部类(静态也可以) ，这个类是专门的节点类用来创建我们的节点对象。

在这里插入图片描述

 
第二步 ： 通过 create 创建我们的链表
 
注意 ： 我们还要创建一个 head 头节点 （用来存放第一个节点的地址）

在这里插入图片描述

 
第三步： 有了链表 接下来我们就来实现我们链表中的方法

 

2.1 打印链表

 
这个方法 可以说 非常简单， 就是创建一个 ListNode cur 让他引用 head 这个引用的 对象，然后 遍历每一个节点 然后打印 。

 
这里主要就只有两个问题 ：

1、如何走到下一个节点

解 ： cur = cur.next

2、什么时候把链表遍历完

解 ： cur != null

 

图解 ：

在这里插入图片描述

 
注意 ： 这我们需要严谨，如果我们的 链表为空我们还能 去打印吗 ？ 这里就可以直接返回或抛出异常

在这里插入图片描述

打印方法实现完 ，下面实现 求链表长度 。

 

2.2 返回链表长度

 
这个方法， 就只需要返回链表中节点的个数 ， 这里同样是需要一个循环， 此时就需要思考 我们的循环结束的条件 。

 

想一想 ： 我们是不是要数节点的个数，那么是不是需要走到每一个节点，那么 这里同样是要创建一个 cur 让他引用 head的对象，然后结束条件是不是就和打印一样cur != null 如果是 cur.next != null 那么 最后一个节点同样是没有记录的 。
 
分析完我们就可以直接来写代码 ：

在这里插入图片描述

 
另外 ：还有一种方法 ，看到这个size 了吗 ？ 我们就可以在 后面些的新增方法中使用，每次添加一个元素 然后 让``size ++` 最后返回的size 就是我们的 链表长度

在这里插入图片描述

 
这里这个方法就写完了， 下面来完成我们的 contains 方法 判断 key 是否存在单链表中

 

2.3 查找 key 元素是否存在链表中

 
这个方法我们同样需要使用循环， 这里同样是要遍历 整条链表，那么 我们循环结束的条件就是 cur != null ，同理 我们不能使用head 去遍历， 所以需要创建一个 cur 来代替 head ， 这里我们 判断是否纯在，那么 拿 每个节点的value 与当前的 key 比较即可 相等放回 true ， 不像等返回 false (注意这里我们是 int 类型，所以 可以直接使用 == ， 如果是包装类 ，需要使用 equals 如果是 自定义类型 重写 equals 即可)

 

代码如下 ：

在这里插入图片描述

 

这里我们是使用非常low 的方法创建了一条链表， 完成了上面这些方法， 其实你创建链表这几个方法 也能实现为啥我创建了呢？
 
是因为 我们可以写完一个方法 在main函数里面去测试 ，但是 上面我并没有去测试 ， 这里可以去测试一下 。

 
下面就来学习一下新增方法， 头插和尾插 然后真正的创建一条链表.

 

2.4 新增方法 add

 
新增方法 总共有 3 个 一个是头插， 一个是尾插 ，一个是 任意位置插入

 

2.4.1 头插

 
图解 ：

在这里插入图片描述

 
代码实现 ：

在这里插入图片描述

 
这里 如果 我们的 链表为空， 也不要紧 ， 你想 head == null , 那么 cur.next = null , cur.next 本来就是null 在赋值一个 null 也是没有问题的， 最后在让 这个 cur 变为新的head

 
补充： 对比一下 顺序表的插入 ，链表的插入是不是就非常高效， 我们链表插入的数据是不是就不需要挪动 元素，只需要改变指向即可。

 

2.4.2 尾插

 
图解 ：
在这里插入图片描述

 
代码实现 ：

在这里插入图片描述

 

2.4.3 任意位置插入

 
index特殊位置分析

在这里插入图片描述

 
index 正常位置插入
在这里插入图片描述

代码实现 ： 

/**
     * 任意节点插入
     * @param index
     * @param data
     */
    public void addIndex(int index, int data) {
        // 创建 新的节点
        ListNode cur = new ListNode(data);
        // 1.判断 index 位置的合法性
        if (index < 0 || index > size()) {
            // 此时我们需要抛出异常
            throw new IndexWrongFulException("index 位置不合法 !!!!");
        }
        // 2.如果 index == 0 头插
        if (index == 0) {
            // 调用头插的方法
            addFirst(data);
            return;
        }
        // 3. 如果 index == size() 尾插
        if (index == size()) {
            addLast(data);
            return;
        }
        // 4.此时 正常情况(中间插入)， 将我们 执行的 代码 封装成一个方法(解耦)
        // 先 走 index - 1 步
        // cur2 拿到我们的前一个节点
        ListNode cur2 = findIndexSubOne(index);
        cur.next = cur2.next;
        cur2 = cur;
       // 此时就完成了我们的 插入

    }

    private ListNode findIndexSubOne(int index) {
        ListNode cur = head;
        while (index - 1 != 0) {
            cur = cur.next;
            index--;
        }
        return cur;
    }

 
添加就学完了， 会了添加 那么对应的删除 也是不可少的， 下面就来学习一下删除操作 。

 

2.5 删除操作 remove

 
这里主要实现两种 删除 ：

  • 第一种 删除 ：删除第一次出现的 key 元素
  • 第二种 删除 ：删除链表中 所有的 key 元素

 

2.5.1 删除第一次出现的 key 元素

在这里插入图片描述

 
代码实现 ：

这里先来完成我们找前一个节点的方法 。

在这里插入图片描述

 
这里的 找前驱 (前一个节点)的方法写完了， 就来完成我们的remove 方法

在这里插入图片描述

 

2.5.2 删除链表中所有的 key值

 
解法一 (不推荐)： 循环调用 删除第一次出现的key 的方法
 
上面我们写完了删除一个key ，那么删除多个key 还不简单吗？
 
直接 写一个循环 调用 这个方法 ， 执行 链表的长度次，这样就能 将 链表中的所有的key 全部删除.
 
为啥不推荐呢 ？ 你想我们 删除第一个key 的方法时间复杂度是不是 0(N) ， 然后我们有需要循环N 次 (链表长度) ，然后调用这个方法 ，那么时间复杂度是不是就是O(N ^ 2) , 时间复杂度太高了 ， 那么 肯定是不推荐的。
 
下面就来学习一下 时间复杂度O(N) 的 方法。
 

解法二 :

 
图一 ：
在这里插入图片描述

 
图二 ：

在这里插入图片描述

 
图三 ：

在这里插入图片描述

删除方法就完成了， 下面就来完成最后一个方法清空链表

 

2.6 清空操作

 
这里清空操作 可以有两种写法 ， 一种比较粗暴一点，直接让头节点置为空 这样就没有人引用 这个链表自然我们就达成了清空操纵
 
第二种那么就是 ，将每一个节点 的 next 域置为空即可 。
 

2.6.1 粗暴一点的清空方法

在这里插入图片描述

 

2.6.2 温柔一点的清空方法

在这里插入图片描述

 
附上代码：



import java.util.List;

public class MySingleList {

    private int size;

    static class ListNode {
        // 使用一个静态内部类 创建我们的节点类，通过这个类来创建对象
        public int value; // 注意： 这里我们并不一定是整形类型
        // 也可以别的类型 所以这里可是使用我们的泛型
        public ListNode next;

        public ListNode(int value) {
            this.value = value;
        }
    }

    private ListNode head; // 头节点

    public void create() {
        ListNode listNode1 = new ListNode(12);
        ListNode listNode2 = new ListNode(23);
        ListNode listNode3 = new ListNode(34);
        ListNode listNode4 = new ListNode(45);
        ListNode listNode5 = new ListNode(56);
        listNode1.next = listNode2;
        listNode2.next = listNode3;
        listNode3.next = listNode4;
        listNode5.next = null;
        head = listNode1;
    }

    /**
     * 打印链表里面的数据
     */
    public void display() {
        if (head == null) {
            // 链表为空，无法打印抛出异常 这里省事直接返回
            return;
        }
        ListNode cur = head;
        while (cur != null) {
            System.out.printf(cur.value + " ");
            // 如果是 cur.next != null ,
            // cur 等于了最后的一个节点， cur.next == null 就不会进入循环
            // 那么最后一个值就不会打印
        }
        System.out.println();
    }

    /**
     * 返回单链表长度
     */

    public int size() {
        if (head == null) {
            // head == null 说明 链表为空
            return -1; // 这里同样是可以自定义异常的
        }
        ListNode cur = head;
        int count = 0; // 用来记录当前节点个数
        while (cur != null) {
            count++;
            cur = cur.next;
        }
        return count;
    }

    /**
     * 查找是否包含关键字key是否存在单链表中
     */
    public boolean contains(int key) {
        // 这里我们的 结束循环条件是 cur != null
        // 那么即便 head == null 即 cur == null
        // 那么也进入不了 循环直接返回了 false
        ListNode cur = head;
        while (cur != null) {
            if (cur.value == key) {
                return true;
            }
            cur = cur.next;
        }
        // 走到这里说明 链表已经遍历完成了，还没找到 key 返回false
        return false;
    }

    /**
     * 头插法
     */
    public void addFirst(int data) {
        ListNode cur = new ListNode(data);
        cur.next = head;
        head = cur;
    }

    /**
     * 尾插法
     */
    public void addLast(int data) {
        ListNode cur = new ListNode(data);
        if (head == null) {
            head = cur;
            return;
            // 注意 我们 需要判断链表是否为空
        }

        ListNode cur2 = head;
        while (cur2.next != null) {
            // 如果我们没有判断链表是否为空 ，
            // 那么 null.next 是不是就空指针异常了。
            cur2 = cur2.next;
        }
        // 进行尾插
        cur2.next = cur;
    }

    /**
     * 任意节点插入
     *
     * @param index
     * @param data
     */
    public void addIndex(int index, int data) {
        // 创建 新的节点
        ListNode cur = new ListNode(data);
        // 1.判断 index 位置的合法性
        if (index < 0 || index > size()) {
            // 此时我们需要抛出异常
            throw new IndexWrongFulException("index 位置不合法 !!!!");
        }
        // 2.如果 index == 0 头插
        if (index == 0) {
            // 调用头插的方法
            addFirst(data);
            return;
        }
        // 3. 如果 index == size() 尾插
        if (index == size()) {
            addLast(data);
            return;
        }
        // 4.此时 正常情况(中间插入)， 将我们 执行的 代码 封装成一个方法
        // 先 走 index - 1 步
        // cur2 拿到我们的前一个节点
        ListNode cur2 = findIndexSubOne(index);
        cur.next = cur2.next;
        cur2 = cur;
        // 此时就完成了我们的 插入

    }

    private ListNode findIndexSubOne(int index) {
        ListNode cur = head;
        while (index - 1 != 0) {
            cur = cur.next;
            index--;
        }
        return cur;
    }

    public void remove(int key) {
        // 1.判断当前链表是否为空
        if (head == null) {
            return;
        }
        // 2. 特殊情况 头节点是我们的 key 删除头节点
        if (head.value == key) {
            head = head.next;
            return;
        }
        // 3. 之前分析过的
        ListNode cur = findPrevOfKey(key);
        if (cur == null) {
            // 抛出异常 ， 这里偷懒直接打印了
            System.out.println("没有你要删除的 " + key);
            return;
        }
        cur.next = cur.next.next;
        // 或则  ListNode show = cur.next;
        // cur.next = show.next;
    }

    // 将找前一个节点 的步骤封装 成一个方法
    public ListNode findPrevOfKey(int key) {
        ListNode cur = head;
        while (cur.next != null) {
            // 这里我们并不需要遍历完
            if (cur.next.value == key) {
                // 此时说明 cur 的下一个节点就是要删除的节点
                return cur;
            }
            cur = cur.next;
        }
        // 此时说明没有找到 返回 null 即可
        return null;
    }


    public void removeAllkey(int key) {
        if (head == null) {
            return;
        }
        ListNode prev = head;
        ListNode cur = prev.next;

        while (cur != null) {
            if (cur.value == key) {
                prev.next = cur.next;
            } else {
                prev.next = cur;
            }
            cur = cur.next;
        }
        // 此时如果头节点 等于 key 删除即可
        if (head.value == key) {
            head = head.next;
        }
    }

    public void clear() {
//        head = null;
        while(head != null){
            ListNode cur = head.next;
            head.next = null;
            head = cur;
        }
        // 先保留 head 的下一个 节点的地址，
        // 置空 当前的节点 然后去 引用下一个节点，继续置空
    }
}

 
这样我们的 单向 不带头不循环的链表就实现完成了， 下面我们就可以来写几道oj题目来看看我们对链表的掌握情况 。
 

链表OJ题目

链接 提供 :

1.移除链表元素

2.反转链表

3.链表的中间结点

4.链表中倒数第k个结点_

5.合并两个有序链表

6.链表分割

7.链表的回文结构

8.相交链表

9.环形链表

10.环形链表 II

如果上面的题目写完 还 嫌不够的话 ，这里还有 力扣 和牛客 链表的合集 也可以写一些

链表知识点题库 - 力扣（LeetCode）

牛客网 - 链表

本文完 : 下文这些 OJ 题目 的讲解。

相关文章：

  • 【MySQL从入门到精通】【高级篇】（二十四）EXPLAIN中select_type，partition，type，key，key_len字段的剖析
  • C | 函数指针数组妙用
  • springboot：生成excel并且通过邮件发送
  • 【自然语言处理】【文本生成】使用Transformers中的BART进行文本摘要
  • 【Vue】Vue中的计算属性computed
  • 一文步入python大门，基础教程大全（25分钟）
  • 计算机学院第二周语法组及算法组作业
  • 13、设计模式总结
  • [LeetCode][面试算法]逻辑闭环的二分查找代码思路
  • 无卷积步长或池化:用于低分辨率图像和小物体的新 CNN 模块SPD-Conv
  • Mysql数据备份（mysqldump的操作）
  • 面向对象编程技术从0总结——“让你对基础技术有一个新的认识”（国庆五万字总结）
  • Spring Webflux - 01 MVC的困境
  • 自动登录禅道和自动开Bug（JMeter中HTTP Cookie管理器和HTTP请求默认值的用法）
  • 【Day23】力扣：LeetCode算法刷题 [927. 三等分 ] [415. 字符串相加]
  • [译] React v16.8： 含有Hooks的版本
  • 【翻译】babel对TC39装饰器草案的实现
  • JS 面试题总结
  • Terraform入门 - 3. 变更基础设施
  • Vue实战(四)登录/注册页的实现
  • Webpack4 学习笔记 - 01：webpack的安装和简单配置
  • 飞驰在Mesos的涡轮引擎上
  • 经典排序算法及其 Java 实现
  • 浏览器缓存机制分析
  • 想使用 MongoDB ，你应该了解这8个方面！
  • 移动端解决方案学习记录
  • ​520就是要宠粉，你的心头书我买单
  • %3cscript放入php,跟bWAPP学WEB安全(PHP代码)--XSS跨站脚本攻击
  • (02)Hive SQL编译成MapReduce任务的过程
  • （4）Elastix图像配准：3D图像
  • （Matalb时序预测）WOA-BP鲸鱼算法优化BP神经网络的多维时序回归预测
  • （Redis使用系列） Springboot 实现Redis消息的订阅与分布 四
  • （附源码）小程序儿童艺术培训机构教育管理小程序 毕业设计 201740
  • (原創) 如何讓IE7按第二次Ctrl + Tab時，回到原來的索引標籤? (Web) (IE) (OS) (Windows)...
  • .bashrc在哪里，alias妙用
  • .equal()和==的区别 怎样判断字符串为空问题： Illegal invoke-super to void nio.file.AccessDeniedException
  • .gitignore文件_Git：.gitignore
  • .NET Core 成都线下面基会拉开序幕
  • .Net mvc总结
  • .net程序集学习心得
  • @Service注解让spring找到你的Service bean
  • @zabbix数据库历史与趋势数据占用优化（mysql存储查询）
  • [Angular] 笔记 21：@ViewChild
  • [BJDCTF 2020]easy_md5
  • [BZOJ4566][HAOI2016]找相同字符(SAM)
  • [CF703D]Mishka and Interesting sum/[BZOJ5476]位运算
  • [CISCN2019 华北赛区 Day1 Web5]CyberPunk --不会编程的崽
  • [codevs] 1029 遍历问题
  • [HackMyVM]靶场 VivifyTech
  • [IE9] IE9 RC版下载链接
  • [IE编程] WebBrowser控件中设置页面的缩放
  • [one_demo_15]模拟交通灯管理系统
  • [one_demo_3]漩涡递增矩阵
  • [POJ - 2386]
  • [Python进阶] 消息框、弹窗：pywin32