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

数据结构-3.链表

article 2024/11/15 20:41:13

前言

本篇博客给大家带来的是链表的知识点, 其中包括面试经常会提问的真题 ArrayList 和 LinkedList 的区别 .

文章专栏: Java-数据结构

若有问题 评论区见

欢迎大家点赞 评论 收藏 分享

如果你不知道分享给谁,那就分享给薯条, 如果分享不成功, 那我就会回你一下,那样你就分享成功啦.

你们的支持是我不断创作的动力 .

1.ArrayList的存在的问题

1.ArrayList底层使用连续的空间, 任意位置插入或者删除元素时, 需要将该位置后面的元素整体往前或往后移动,故时间复杂度为 O(N) .

2.增容需要申请新的空间, 拷贝数据, 释放旧空间 会有不小的消耗 .

3.增容一般是呈1.5倍或2倍增长,势必会有一定的空间浪费. 例如当前容量为100时, 假设呈二倍增长,满了以后增容到200, 我们再继续插入5个数据, 后面没有数据插入的话就浪费了95个数据空间.

如果我们想要达到那种随用随取, 有几个数据我就增几个空间,那我们该怎么办呢? - 就是今天要介绍的链表了

2.链表

2.1链表的概念及结构

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

注意: 

1. 从上图可看出, 链式结构再逻辑上是连续的的,但是在物理上不一定连续.

2. 现实中的结点一般都是从堆上申请出来的

3. 从堆上申请的空间, 是按照一定的策略来分配的, 两次申请的空间可能连续, 也可能不连续

实际中链表的结构非常多样, 一下情况组合起来就有8种链表结构 :

1. 单向或者双向

2.带头或者不带头

3.循环或者非循环

虽然有8种链表的结构, 但是我们重点掌握两种: 

1.无头单向非循环链表: 结构简单, 一般不会单独用来存数据. 实际种更多的是作为其他数据结构的子结构, 如: 哈希桶, 图的邻接表等等. 另外这种结构在笔试 面试中出现很多.

2.无头双向链表: 在Java的集合框架库中LinkedList 底层实现 就是无头双向循环链表.

2.2链表的实现(无头单向非循环链表)

写到这里, 我想起上篇 顺序表的实现 , 我直接把代码一丢 没做任何解释, 会让初学者看得很难受, 所以这次我得改正这个错误, 尽量让大家都能看懂并且会自己写. 其实解释也是很耗费时间的, 作为一名大二的学生😭, 上专业课和看网课就让我的时间所剩无几, 完后还要写blog, 我真是累成狗了🐶. 但是我还是很开心的,  一方面能够给大家带来知识, 另一方面也是在巩固我的知识. 

第一步创建一个类 MySingleList 

 我们都知道节点是链表里面的 , 所以节点就是链表的成员,这没有问题,

那问题来了, 节点中的数据data呢? 它可以定义为链表的成员吗? 

显然是不行的, 因为data是节点里面的, 只需要,在MySingleList类当中再定义一个内部类ListNode就可以解决了.

public class MySingleList {

    //因为节点是链表的一部分,所以可以将其定义为内部类
    static class ListNode {
        public int val;//节点的值域
        public ListNode next;//下一个节点的地址

        public ListNode(int val) {
            this.val = val;
        }
    }
public ListNode head;//表示当前链表的头节点
}

所以有了上述代码. 那么接着我想要实现链表的头插法, 尾插法. 我发现没有链表,

那么就自己手动实现一个简单点的,

// 头插法
public void addFirst ( int data ){
}
// 尾插法
public void addLast ( int data ){
} 
public class MySingleList {

    //因为节点是链表的一部分,所以可以将其定义为内部类
    static class ListNode {
        public int val;//节点的值域
        public ListNode next;//下一个节点的地址

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

public ListNode head;//表示当前链表的头节点

//手动实现简单链表
public  void createList() {
        ListNode node1 = new ListNode(12);
        ListNode node2 = new ListNode(23);
        ListNode node3 = new ListNode(34);
        ListNode node4 = new ListNode(45);
        ListNode node5 = new ListNode(56);

        node1.next = node2;
        node2.next = node3;
        node3.next = node4;
        node4.next = node5;

        this.head = node1;
    }
}
好,  到这里 我们就可以来实现链表的基本操作: 

第二步实现链表的基本操作

遍历单链表:

//遍历单链表
    public void display() {
        //指向头节点的引用不能动,所以利用cur代替
        ListNode cur = this.head;
        while(cur != null) {
            System.out.print(cur.val+" ");
            cur = cur.next;
        }
        System.out.println();
    }

求链表的长度:

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

查找关键字key是否包含在链表中:

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

头插法:

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

尾插法:

public void addLast(int data) {
        ListNode node = new ListNode(data);
        ListNode  cur = this.head;
        if(cur == null) {
            head = node;
            return;
        }
        while(cur.next != null) {
            cur = cur.next;
        }
        cur.next = node;
        node.next = null;
    }

任意位置插入,第一个数据节点为0号下标: 

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

清除链表, 直接把head赋值为空即可:

//清除单链表
    public void clear() {
        this.head = null;
    }

删除第一个值为key的节点:

//删除第一个关键字为key的节点
    public void remove(int key){
        if(head == null) {
            return;
        }
        //单独删除头节点
        if(head.val == key) {
            head = head.next;
            return;
        }
        ListNode cur = searchPrev(key);
        if(cur == null) {
            System.out.println("没有找到key");
            return;
        }
        ListNode del = cur.next;
        cur.next = del.next;
    }

    //找到关键字key的前驱
    private ListNode searchPrev(int key) {
        ListNode cur = this.head;
        while(cur.next != null) {
            if(cur.next.val == key) {
                return cur;
            }
            cur = cur.next;
        }
        return null;
    }

删除值为key的所有节点:

 //删除所有关键为key的节点
    public void removeAll(int key){
        if(head == null) {
            return;
        }

        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(head.val == key) {
            head = head.next;
        }
    }

下面是全部代码:

//因为节点是链表的一部分,所以可以将其定义为内部类
    static class ListNode {
        public int val;//节点的值域
        public ListNode next;//下一个节点的地址

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

    public ListNode head;//表示当前链表的头节点

    public  void createList() {
        ListNode node1 = new ListNode(12);
        ListNode node2 = new ListNode(23);
        ListNode node3 = new ListNode(34);
        ListNode node4 = new ListNode(45);
        ListNode node5 = new ListNode(56);

        node1.next = node2;
        node2.next = node3;
        node3.next = node4;
        node4.next = node5;

        this.head = node1;
    }

    //遍历单链表
    public void display() {
        //指向头节点的引用不能动,所以利用cur代替
        ListNode cur = this.head;
        while(cur != null) {
            System.out.print(cur.val+" ");
            cur = cur.next;
        }
        System.out.println();
    }

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

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

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

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

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

        //删除第一个关键字为key的节点
    public void remove(int key){
        if(head == null) {
            return;
        }
        //单独删除头节点
        if(head.val == key) {
            head = head.next;
            return;
        }
        ListNode cur = searchPrev(key);
        if(cur == null) {
            System.out.println("没有找到key");
            return;
        }
        ListNode del = cur.next;
        cur.next = del.next;
    }

    //找到关键字key的前驱
    private ListNode searchPrev(int key) {
        ListNode cur = this.head;
        while(cur.next != null) {
            if(cur.next.val == key) {
                return cur;
            }
            cur = cur.next;
        }
        return null;
    }

    //删除所有关键为key的节点
    public void removeAll(int key){
        if(head == null) {
            return;
        }

        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(head.val == key) {
            head = head.next;
        }
    }

    //清除单链表
    public void clear() {
        this.head = null;
    }

3.LinkedList的模拟实现(无头双向链表)

无头双向链表跟上述的单向链表的实现大致相同,不过是多了一个前驱,故不做解释

static class ListNode {
        private int val;//数据域
        private ListNode prev;//前驱
        private ListNode next;//后继

        public ListNode(int val) {
            this.val = val;
        }
    }
    public ListNode head;//双向链表的头节点.
    public ListNode last;//双向链表的尾节点.

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

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

    //任意位置插入,第一个数据节点为0号下标
    public void addIndex(int index,int data){
        ListNode node = new ListNode(data);
        ListNode cur = head;
        if(index == 0) {
            addFirst(data);
            return;
        }
        if(index == size()) {
            addLast(data);
            return;
        }
        if(index != 0 && index != size()) {
            for (int i = 0; i < index-1; i++) {
                cur = cur.next;
            }
            node.next = cur.next;
            cur.next.prev = node;
            cur.next = node;
            node.prev = cur;
        }

    }
//判断Index是否合法
    private void checkIndex(int index) {
        if(index < 0 || index > size()) {
            throw new IndexOutOfException("index 不合法" + index);
        }
    }

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

    //删除第一次出现关键字为key的节点
    public void remove(int key){
        ListNode cur = head;
        if(head.val == key) {
            head = head.next;
            if(head != null) {
                //考虑只有一个节点的情况下
                head.prev = null;
            }else{
                last = null;
            }
            return;
        }
        if(last.val == key) {
            last = last.prev;
            last.next = null;
            return;
        }
        while(cur != null) {
            if(cur.val == key) {
                cur.prev.next = cur.next;
                cur.next.prev = cur.prev;
                return;
            }
            cur = cur.next;
        }
    }

    //删除所有值为key的节点
    public void removeAllKey(int key){
        ListNode cur = head;
        while(cur != null) {
            if(cur.val == key) {
                if(cur == head) {
                    head = head.next;
                    head.prev = null;
                    cur = cur.next;
                    continue;
                }
                if(cur == last) {
                    last = last.prev;
                    last.next = null;
                    cur = cur.next;
                    continue;
                }
                cur.prev.next = cur.next;
                cur.next.prev = cur.prev;
                cur = cur.next;
            }
            cur = cur.next;
        }
    }

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

    //遍历链表
    public void display(){
        ListNode cur = head;
        for (int i = 0; i < size(); i++) {
            System.out.print(cur.val + " ");
            cur = cur.next;
        }
        System.out.println();
    }

    //清除链表
    public void clear(){
        /*ListNode cur = head;
        while(cur.next != null) {
            cur = cur.next;
            cur.prev.next = null;
            cur.prev = null;
        }
        //while循环走出来有两种情况:
        //1.head.next = null;
        //2.cur走到了尾节点.
        if(head.next == null) {
            head = head.next;
        }else {
            cur.prev = null;
        }
        head = null;
        last = null;*/

        //gaobo写法:
        ListNode cur = head;
        while(cur != null) {
            ListNode curNext = cur.next;
            cur.prev = null;
            cur.next = null;
            cur = curNext;
        }
        head = null;
        last = null;
    }

4.LinkedList的使用

4.1LinkedList的介绍

LinkedList的官方文档:

LinkedList (Java Platform SE 8 ) (oracle.com)

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

说明:

1. LinkedList实现了List接口

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

3. LinkedList没有实现RandomAccess接口, 因此LinkedList不支持随机访问

4. LinkedList的任意位置插入和删除元素时的效率比较高,时间复杂度为O(1)

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

4.2LinkedList的使用

1.LinkedList的构造

public class Test3 {
    public static void main(String[] args) {
        //构造一个空的LinkedList
        List<Integer> list1 = new LinkedList<>();

        List<String> list2 = new ArrayList<>();
        list2.add("2334");
        list2.add("ieie");
        list2.add("uuy");

        //使用ArrayList构造LinkedList
        List<String> list3 = new LinkedList<>(list2);
        System.out.println(list3);
    }
}

第二种构造方法与 顺序表中第二种构造方法相似. 这里看不懂的可以去上篇看看顺序表中关于构造方法的讲解.

2.LinekedList的其他常用方法

int indexOf(Object o)    返回第一个o所在下标    
int lastlndexOf(Object 0)    返回最后一个o的下标    
List<E> subList(int fromlndex, int tolndex)    截取部分 list

5.ArrayList和LinkedList的区别

从不同点处记忆即可


http://www.kler.cn/a/319789.html

相关文章：

  • 设计模式之装饰器模式(SSO单点登录功能扩展，增加拦截用户访问方法范围场景)
  • MQTT协议解析 : 物联网领域的最佳选择
  • 一文简单了解Android中的input流程
  • 结构体（c语言）
  • 32位、64位、x86与x64：深入解析计算机架构
  • TCP/IP协议，TCP和UDP区别
  • 无人机在隧道中如何实现在无卫星信号下的自主导航
  • 将ipad作为数位板使用教程/出现延迟拖拽怎么办？
  • 在jupyter notebook中取消代理服务器的解决方案
  • 编程遇到问题了？一个命令让 AI 解决你的困惑！
  • Android——内部/外部存储
  • HTTP常见状态码 HTTP的逐步发展（通俗易懂版）
  • 利士策分享，赚钱有道，底线思维不可抛
  • 网络安全-shire写任务计划、反弹shell、写私钥、反序列化
  • 机器学习算法与Python实战 | 三万字详解！GPT-5：你需要知道的一切（上）建议收藏！
  • 性能监控之Python实战SkyWalking链路追踪
  • [java][git]git学习
  • Linux动态库防止逆向编译参数
  • keil的debug功能
  • IT行业的未来：技术变革与创新的持续推动
  • 解决fatal: unable to access ‘https://........git/‘: Recv failure: Operation time
  • ~关于 CAS 机制、ABA问题、偏向锁、synchronized 实现原理、信号量、Callable
  • Prompt最佳实践｜如何用参考文本让ChatGPT答案更精准？
  • 深入理解Kubernetes供应链安全：CKS考试核心知识点实践
  • 在 expressjs 中MySQL 的datetime类型，怎么插入数据
  • 使用java实现ffmpeg的各种操作