首页 > 资讯 > 后端开发 > Python >Java数据结构之链表的增删查改详解

167

分享到

Java数据结构之链表的增删查改详解

2024-04-02 19:04:59 167人浏览独家记忆

Python 官方文档：入门教程 => 点击学习

摘要

目录一、链表的概念和结构1.1 链表的概念1.2 链表的分类二、单向不带头非循环链表2.1 创建节点类型2.2 头插法2.3 尾插法2.4 获取链表长度2.5 任意位置插入2.6 查

一、链表的概念和结构

1.1 链表的概念

简单来说链表是物理上不一定连续，但是逻辑上一定连续的一种数据结构

1.2 链表的分类

实际中链表的结构非常多样，以下情况组合起来就有8种链表结构. 单向和双向，带头和不带头，循环和非循环。排列组合和会有8种。
但我这只是实现两种比较难的链表，理解之后其它6种就比较简单了
1.单向不带头非循环链表
2.双向不带头非循环链表

二、单向不带头非循环链表

在这里插入图片描述

2.1 创建节点类型

我们创建了一个 Listnode 类为节点类型，里面有两个成员变量，val用来存储数值，next来存储下一个节点的地址。
还有一个带一个参数的构造方法在实例化对象的同时给val赋值，因为我们不知道下一个节点的地址所以next是默认值一个null


class ListNode {
    public int val;//数值
    public ListNode next;//下一个节点的地址

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

我们在 MyLinkedList 里创建一个head变量来标识链表的头部，接着就是实现单链表的增删查改了

在这里插入图片描述

2.2 头插法

这个头插法并不要考虑第一次插入，每次插入只需要把插入的节点node 的next值改成头节点，再把头节点指向node

在这里插入图片描述


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

2.3 尾插法

尾插法首先要考虑是不是第一次插入，如果是的话直接把head指向node就好了，如果不是第一次插入，则需要定义一个cur来找尾巴节点，把尾巴节点的next值改成node就好了。因为如果不用尾巴节点的话，head就无法标识到头部了

在这里插入图片描述


//尾插法
public void addLast(int data) {
    ListNode node = new ListNode(data);
    ListNode cur = this.head;
    //第一次插入
    if(this.head == null) {
        this.head = node;
    }else{
        while (cur.next != null) {
            cur = cur.next;
        }
        cur.next = node;
    }
}

2.4 获取链表长度

定义一个计数器count，当cur遍历完链表的时候直接返回count就好


//得到单链表的长度
public int size() {
    int count = 0;
    ListNode cur = this.head;
    while (cur != null) {
        cur = cur.next;
        count++;
    }
    return count;
}

2.5 任意位置插入

我们假设链表的头是从0位置开始的，任意位置插入需要考虑几点
1.位置的合法性，如果位置小于0，或者大于链表长度则位置不合法
2.如果要插入的是0位置直接使用头插法
3.如果插入的位置等于链表长度则使用尾插法，因为我们这链表是从0开始的

最关键的就是从中间任意位置插入要从中间位置插入，就需要找到要插入位置的前一个节点的位置。再插入到它们中间。

在这里插入图片描述


  
public ListNode findIndexSubOne(int index) {
    int count = 0;
    ListNode cur = this.head;
    while (count != index-1) {
        cur = cur.next;
        count++;
    }
    return  cur;
}
//任意位置插入,第一个数据节点为0号下标
public void addIndex(int index,int data) {
    //判断合法性
    if(index < 0 || index > size()) {
            System.out.println("index位置不合法");
            return;
    }
    //头插法
    if(index == 0) {
        this.addFirst(data);
        return;
    }
    //尾插法
    if(index == size()) {
        this.addLast(data);
        return;
    }
    //找前驱,cur指向的是 index 的前一个节点
    ListNode cur = findIndexSubOne(index);
    ListNode node = new ListNode(data);
    node.next = cur.next;
    cur.next = node;
}

2.6 查找关键字

当我们要查找链表中是否有某一个关键字时，只需要定义一个cur从头开始遍历即可


//查找是否包含关键字key是否在单链表当中
public boolean contains(int key) {
    ListNode cur = this.head;
    while (cur != null) {
        if(cur.val == key) {
            return true;
        }
        cur = cur.next;
    }
    return false;
}

2.7 删除第一次出现值为key的节点

这个思路其实也很简单，考虑到两种情况即可

1.如果要删除的是头节点只需要把头节点指向它的向一个节点即可
2.还有一种则是不存在key的情况，所以这里写了一个方法来判读key是否存在，如果存在则返回key的前一个节点的位置
3.存在则把要删除的节点的前驱的next改成它的next即可



public ListNode searchPrev(int key) {
    ListNode prev = this.head;
    while (prev.next != null) {
        if (prev.next.val == key) {
            return prev;
        }
        prev = prev.next;
    }
    return null;
}
//删除第一次出现关键字为key的节点
public void remove(int key) {
    if(this.head.val == key) {
        this.head = this.head.next;
        return;
    }
    //找 key 的前驱节点
    ListNode prev = searchPrev(key);
    if(prev == null) {
        System.out.println("没有key这个关键字");
        return;
    }
    //删除
    ListNode delete = prev.next;
    prev.next = delete.next;
}

2.8 删除所有值为key的节点

在这里插入图片描述

假设要删除的是3，思路：

定义两个节点点类型的变量，prev指向head，cur指向head的下一个节点。
如果判断cur的val值是要删除的值，如果是则直接跳过这个节点如果不是则让prev和cur往后走，直到整个链表遍历完。
到最后会发现头节点并没有遍历到，循环结束后则需要判读头节点是不是要删除的节点

记住一定要边画图边写代码！


//删除所有值为key的节点
public void removeAllKey(int key) {
    ListNode prev = this.head;
    ListNode cur = this.head.next;
    while (cur != null) {
        if(cur.val == key) {
            prev.next = cur.next;
            cur = cur.next;
        }else {
            prev = cur;
            cur = cur.next;
        }
    }
    //判断第一个节点是否是要删除的节点
    if(this.head.val == key) {
        this.head = this.head.next;
    }
}

2.9 遍历打印链表

定义一个cur直接遍历打印就好


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

置空链表

置空链表只需要一个个置空即可，并不建议直接把头节点置空这种暴力做法


//置空链表
public void clear() {
    ListNode cur = this.head;
    //一个个制空
    while (cur != null) {
        ListNode curNext = cur.next;
        cur.next = null;
        cur = curNext;
    }
    this.head = null;
}

三、双向不带头非循环链表

双向链表和单向链表的最大的区别就是多了一个前驱节点prev，同样来实现双向链表的增删查改

在这里插入图片描述


public class TestLinkedList {
    public ListNode head;
    public ListNode last;
}

3.1 创建节点类型

同样先定义节点类型，比单向链表多了一个前驱节点而已。


class ListNode {
    public int val;
    public ListNode prev;
    public ListNode next;

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

双向链表还定义了一个last来标识尾巴节点，而单链表只是标识了头节点。

在这里插入图片描述

3.2 头插法

因为这是双向链表，第一次插入要让head和last同时指向第一个节点。
如果不是第一次插入，则需要
1.把head的前驱节点改成node,
2.再把node的next改成head，
3.然后把头节点head再指向新的头节点node。

在这里插入图片描述


//头插法
public void addFirst(int data) {
    ListNode node = new ListNode(data);
    //第一次插入
    if(this.head == null) {
        this.head = node;
        this.last = node;
    }else {
        head.prev = node;
        node.next = this.head;
        this.head = node;
    }
}

3.3 尾插法

双向链表有一个last来标识尾巴节点，所以在尾插的时候不用再找尾巴节点了。和头插法类似


//尾插法
public void addLast(int data) {
    ListNode node = new ListNode(data);
    //第一次插入
    if(this.head == null) {
        this.head = node;
        this.last = node;
    }else {
        this.last.next = node;
        node.prev = this.last;
        this.last = node;
    }
}

3.4 获取链表长度

这个和单链表一样，直接定义个cur遍历


//得到链表的长度
public int size() {
    ListNode cur = this.head;
    int count = 0;
    while (cur != null) {
        count++;
        cur = cur.next;
    }
    return count;
}

3.5 任意位置插入

任意位置插入也和单链表类似有三种情况。判断合法性和头插尾插就不多了主要还是在中间的随机插入，一定要注意修改的顺序！

要修改的地方一共有四个，一定要画图理解！

在这里插入图片描述


//找要插入的节点的位置
public ListNode searchIndex(int index) {
    ListNode cur = this.head;
    while (index != 0) {
        cur = cur.next;
        index--;
    }
    return  cur;
}
//任意位置插入,第一个数据节点为0号下标
public void addIndex(int index,int data) {
    //判断index位置的合法性
    if(index < 0 || index > this.size()) {
        System.out.println("index的位置不合法");
        return;
    }
    //头插法
    if(index == 0) {
        this.addFirst(data);
        return;
    }
    //尾插法
    if(index == this.size()) {
        this.addLast(data);
        return;
    }
    //中间插入
    ListNode node = new ListNode(data);
    ListNode cur = searchIndex(index);
    node.next = cur;
    node.prev = cur.prev;
    cur.prev.next = node;
    cur.prev = node;
}

3.6 查找关键字

这里和单链表一样，直接定义个cur遍历看看链表里有没有这个值即可


//查找是否包含关键字key是否在单链表当中
public boolean contains(int key) {
    ListNode cur = this.head;
    while (cur != null) {
        if(cur.val == key) {
            return true;
        }
        cur = cur.next;
    }
    return false;
}

3.7 删除第一次出现的关键字key的节点

思路：遍历链表找第一次出现的节点，删完return。一共分三种情况
1.头节点是要删除的节点
2.尾巴节点是要删除的节点
3.中间的节点是要删除的节点


//删除第一次出现关键字为key的节点
public void remove(int key) {
    ListNode cur = this.head;
    while (cur != null) {
        if(cur.val == key) {
            //要删除的是头节点
            if(this.head == cur) {
                this.head = this.head.next;
                this.head.prev = null;
            }else {
                //尾巴节点和中间的节点两种情况
                cur.prev.next = cur.next;
                if(this.last == cur) {
                    //删除尾巴节点
                    cur = cur.prev;
                }else {
                    cur.next.prev = cur.prev;
                }
            }
            //已经删完了
            return;
        }else {
            cur = cur.next;
        }
    }
}

3.8 删除所有值为key的节点

思路和删除一个key类似，但需要注意两个点。

1.删完就不用return了，而是继续往后走，因为这里是删除所有为key需要把列表遍历完
2.还有就是要考虑当整个链表都是要删除的情况，if判断一下不然会发生空指针异常


//删除所有值为key的节点
public void removeAllKey(int key) {
    ListNode cur = this.head;
    while (cur != null) {
        if(cur.val == key) {
            //要删除的是头节点
            if(this.head == cur) {
                this.head = this.head.next;
                //假设全部是要删除的节点
                if(this.head != null) {
                    this.head.prev = null;
                }else {
                 //防止最后一个节点不能被回收
                 this.last = null;
                }
            }else {
                //尾巴节点和中间的节点两种情况
                cur.prev.next = cur.next;
                if(this.last == cur) {
                    //删除尾巴节点
                    cur = cur.prev;
                }else {
                    cur.next.prev = cur.prev;
                }
            }
            //走一步
            cur = cur.next;
        }else {
            cur = cur.next;
        }
    }
}

3.9 遍历打印链表


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

置空链表

遍历链表一个一个置为null，再把头节点和尾巴节点值为null。防止内存泄漏


//置空链表
public void clear() {
    ListNode cur = this.head;
    //一个一个置空
    while (cur != null) {
        ListNode curNext = cur.next;
        cur.prev = null;
        cur.next = null;
        cur = curNext;
    }
    this.head = null;
    this.last = null;
}

四、总结

1.这里实现了两种较难的链表：单向不带头非循环和双向不带头非循环

2.链表物理上不一定连续，但逻辑上一定连续。

3.增：链表插入一个元素只需要修改指向，所以时间复杂度为O(1)

4:删：链表删除元素，同样只需修改指向，时间复杂度为O(1)

5.查：链表如果需要查找一个元素需要遍历链表，所以时间复杂度为O(n)

6.改：链表要去找到要修改的元素，所以时间复杂度为O(n).

什么时候用链表？
如果是插入和删除比较频繁的时候，使用链表。注意：是不涉及到移动数据的情况！

到此这篇关于Java数据结构之链表的增删查改详解的文章就介绍到这了,更多相关Java链表内容请搜索编程网以前的文章或继续浏览下面的相关文章希望大家以后多多支持编程网！

您可能感兴趣的文档:

点击免费下载>>软考高级考试备考技巧/历年真题/备考精华资料

--结束END--

本文标题: Java数据结构之链表的增删查改详解

本文链接: https://www.lsjlt.com/news/126596.html(转载时请注明来源链接)

有问题或投稿请发送至: 邮箱/279061341@qq.com QQ/279061341

本篇文章演示代码以及资料文档资料下载

下载Word文档到电脑，方便收藏和打印～

下载Word文档

去做题

猜你喜欢

Java数据结构之链表的增删查改详解

目录一、链表的概念和结构1.1 链表的概念1.2 链表的分类二、单向不带头非循环链表2.1 创建节点类型2.2 头插法2.3 尾插法2.4 获取链表长度2.5 任意位置插入2.6 查...

99+

2024-04-02
【数据结构】—— 单链表的增删改查

❤️一名热爱Java的大一学生，希望与各位大佬共同学习进步❤️ 🧑个人主页：@周小末天天开心各位大佬的点赞👍 收藏⭐ 关注✅，是本人学习的最大动力感谢！ 📕该篇文章收录专栏—...

99+

2023-09-04

java 开发语言数据结构
Java数据结构之链表详解

目录一、链表的介绍二、单链表的实现三、双向链表的实现四、循环链表的实现五，链表相关的面试题一、链表的介绍什么是链表链表是一种物理存储单元上非连续、非顺序的存储结构，数据元素的逻辑...

99+

2024-04-02
C语言数据结构之单链表与双链表的增删改查操作实现

目录前言单链表的增删改查定义结构体以及初始化增加结点删除结点查找修改结点移除结点最终效果双链表的基本操作初始化建表遍历双链表指定位置插入结点指定位置删除结点查找结点位置最终效果结语前...

99+

2024-04-02
Java数据结构之单链表详解

目录一、图示二、链表的概念及结构三、单链表的实现四、完整代码的展示一、图示二、链表的概念及结构链表是一种物理存储结构上非连续存储结构，数据元素的逻辑顺序是通过链表中的...

99+

2024-04-02
MySQL增删查改数据表详解

目录前言一、新增数据二、查询数据全列查询指定列查询表达式查询指定别名查询去重查询排序查询条件查询分页查询三、修改数据四、删除数据前言 CRUD代表: 增加(create) ,查询(retrieve) ,更新(updat&...

99+

2022-11-19

MySQL增删查改 MySQL数据库操作
Python数据结构之链表详解

目录0.学习目标1.线性表的链式存储结构1.1指针相关概念1.2指针结构1.3结点1.4结点类2.单链表的实现2.1单链表的初始化2.2获取单链表长度2.3读取指定位置元素2.4查找...

99+

2024-04-02
Redis数据结构之链表详解

目录1 链表和链表节点的结构2 链表相关的API1 链表和链表节点的结构 1.1 节点结构节点的结构大概长下边这个样子：那么，把这些节点就连起来就成了这个样子： 1.2 链表...

99+

2024-04-02
C++数据结构之链表详解

目录前言一、删除链表中给定值为key的节点二、反转链表三、返回链表的中间节点四、删除链表的倒数第K个节点五、分割链表六、合并两个有序链表七、删除有序链表中重复节点八、环形链表九、相交...

99+

2024-04-02
Java单链表的增删改查与面试题详解

目录一、单链表的增删改查1、创建结点2、单链表的添加操作3、单链表的删除操作4、单链表的有效结点的个数二、大厂面试题一、单链表的增删改查 1、创建结点单链表是由结点连接而成，所以...

99+

2024-04-02
Java数据结构之删除链表中重复的结点

目录解析一：（不提倡）解析二：（正解）核心考点：链表操作，临界条件检查，特殊情况处理在一个排序的链表中，存在重复的结点，请删除该链表中重复的结点，重复的结点不保留，返回链表头指针。...

99+

2024-04-02
Python数据结构之双向链表详解

目录0. 学习目标1. 双向链表简介1.1 双向链表介绍1.2 双向链表结点类1.3 双向链表优缺点2. 双向链表实现2.1 双向链表的初始化2.2 获取双向链表长度2.3 读取指定...

99+

2024-04-02
Java数据结构之链表的概念及结构

目录1、链表的概念2、结点3、链表的使用场景4、链表分类和常用结构5、与顺序表的比较1、链表的概念概念：链表是一种物理存储结构上非连续、非顺序的存储结构，数据元素的逻辑顺序是通过链...

99+

2023-05-14

Java 数据结构链表概念结构数据结构链表概念数据结构链表结构
数据结构TypeScript之链表实现详解

目录链表结构特点面向对象方法封装链表构造函数基本单元：链表节点主体：链表查找节点增加节点删除节点链表结构特点链表是线性表的其中一种，用于存储有固定顺序的元素。而元素之间会通过&r...

99+

2023-01-30

TypeScript数据结构链表 TypeScript数据结构
Python数据结构之循环链表详解

目录0. 学习目标1. 循环链表简介2. 循环单链表实现2.1 循环单链表的基本操作2.2 简单的实现方法2.3 循环单链表应用示例2.4 利用循环单链表基本操作实现复杂操作3. 循...

99+

2024-04-02
Java数据结构之双向链表图解

双向链表（Doubly linked list）什么是双向链表？双向链表也叫双链表，是链表的一种，它的每个数据结点中都有两个指针，分别指向直接后继和直接前驱。所以，从双向链表中的...

99+

2024-04-02
Java数据结构之顺序表和链表精解

目录前言1. 顺序表代码实现2. 链表链表图解代码实现前言两个数据结构：顺序表和链表数据结构是一门学科，和语言无关。数据 + 结构：一种描述和组织数据的方式。 1. 顺序表顺...

99+

2024-04-02
Python数据结构与算法之链表,无序链表详解

目录我们首先来构造节点。节点（Node）的类构建完毕后，接下来我们开始构建整个链表（LinkList）的类。那么我们还需要一个方法来判断链表头的指向。接下来我们构建链表节点的添加方法...

99+

2024-04-02
数据结构——链表(java)

文章目录链表1. 基本介绍1.1 定义1.2 链表分类3.不带头非循环单链表CURD4.不带头非循环双向链表CURD 链表 1. 基本介绍 1.1 定义链表是一种物理存储结构...

99+

2023-10-02

数据结构链表 java
Java数据结构之散列表详解

目录介绍1 散列表概述1.1 散列表概述1.2 散列冲突（hash collision）2 散列函数的选择2.1 散列函数的要求2.2 散列函数构造方法3 散列冲突的解决3.1 分离...

99+

2024-04-02