devbox
Li_阴宅
这个屌丝很懒，什么也没留下！
关注作者
热门标签
热门文章
当前位置:   article > 正文

Java数据结构-单链表_单链表java代码

作者：Li_阴宅 | 2024-07-30 20:13:03

赞

踩

单链表java代码

目录

1. 链表相关概念

老铁们好！今天我们要学习一种新的数据结构：链表。链表是一种逻辑上连续，物理上不连续的一种数据结构，它由一个一个的结点构成，每个结点包含数据和下一个结点的地址，如图。由于最后一个结点没有后续的结点，所以next为null
在这里插入图片描述
链表有很多种结构：单向、双向、循环、非循环、有头、无头。链表结构有很多，但是我们只学习两种：无头单向非循环链表（最简单的）和无头双向非循环链表（Java集合框架中的LinkedList的底层），今天我们先实现最简单的无头单向非循环链表。

2. 功能实现

2.1 整体框架

定义MySignalList泛型类，表示一个链表，定义静态内部类ListNode表示链表的结点，内部类中val表示数据，next表示下一个结点的地址，同时提供ListNode构造方法，初始化val，head表示链表的第一个结点，此外，MySignalList类中还有若干的增删查改等功能的方法

public class MySignalList<T> {

    static class ListNode {
        public Object val;
        public ListNode next;

        public ListNode(Object val) {
            this.val = val;
        }
        
    }
    public ListNode head;
    //........
    //若干方法
}  

  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15

接下来我们介绍相关的功能的实现

2.2 增加

addFirst

头插，将申请的新的结点的next指向head，再更新head的值即可

    public void addFirst(T val) {
        ListNode newNode = new ListNode(val);
        newNode.next = head;
        head = newNode;
    }

  • 1
  • 2
  • 3
  • 4
  • 5

addLast

尾插，如果链表没有元素，head为空，则将申请的新结点赋值给head即可，如果链表不为空，需要找到最后一个结点(尾结点)，将尾结点的next指向新的结点即可

    public void addLast(T val) {
        ListNode newNode = new ListNode(val);
        if (head == null) {
        	//如果链表为空
            head = newNode;
            return;
        }
        //找尾
        ListNode tail = head;
        while (tail.next != null) {
            tail = tail.next;
        }
        tail.next = newNode;
    }

  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14

addIndex

在Index位置插入数据，首先需要判断Index的合法性，我们定义一个异常类IndexNotLegalException：

public class IndexNotLegalException extends RuntimeException {
    public IndexNotLegalException() {
        super();
    }
    public IndexNotLegalException(String s) {
        super(s);
    }
}

  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8

如果Index小于0或者Index大于链表的长度size，抛出异常，如果Index等于0，表示头插；如果Index等于链表长度size，表示尾插，头插、尾插直接调用之前写的方法即可
获取链表长度：

    public int size() {
        int size = 0;
        ListNode cur = head;
        while (cur != null) {
            cur = cur.next;
            size++;
        }
        return size;
    }

  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9

排查了Index的合法性后，要在Index位置插入数据，先要找到Index前一个位置（定义临时结点cur，循环往后走Index-1步），找到之后，让新的结点绑定后面的链表，然后将Index前一个结点的next指向新的结点，如图
在这里插入图片描述

    public void addIndex(int Index, T val) {
        //判断Index的合法性
        try {
            if (Index < 0 || Index > size()) {
                throw new IndexNotLegalException("Index不合法");
            }
        } catch (IndexNotLegalException e) {
            e.printStackTrace();
        }
        if (Index == 0) {
            addFirst(val);
            return;
        }
        if (Index == size()) {
            addLast(val);
            return;
        }
        ListNode newNode = new ListNode(val);
        ListNode cur = head;
        for (int i = 0; i < Index - 1; i++) {
            cur = cur.next;
        }
        //cur在index前面
        newNode.next = cur.next;
        cur.next = newNode;
    }

  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21
  • 22
  • 23
  • 24
  • 25
  • 26

2.3 删除

2.3.1 remove

删除第一个值为key的结点，如果链表为空直接return。
删除的逻辑：循环遍历链表，使用equals方法比较结点的值是否与key相等，定义前驱结点prev记录前一个结点的位置，定义当前结点cur用于遍历链表。如果找到了，让prev结点的next指向当前结点的下一个结点
在这里插入图片描述

    //删除第一次出现的key
    public void remove(T key) {
        if (head == null) {
            return;
        }
        ListNode cur = head;
        ListNode prev = null;
        while (cur != null) {
            if (cur.val.equals(key)) {
                if (prev == null) {
                	//如果第一个结点的值是key,让head往后走,然后return
                    head = head.next;
                    return;
                }
                prev.next = cur.next;
                return;
            }
            prev = cur;
            cur = cur.next;
        }
    }

  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21

2.3.2 removeall

删除所有值为key的结点，与remove逻辑一样，remove删除之后就return了，removeall删除之后不需要return，继续执行之前的操作即可

    //删除所有的key
    public void removeAll(T key) {
        if (head == null) {
            return;
        }
        //如果前半部分都是key,直接让head往后走,如果head为空了就return
        while (head.val.equals(key)) {
            head = head.next;
            if (head == null) {
                return;
            }
        }
        ListNode cur = head.next;
        ListNode prev = head;
        while (cur != null) {
            if (cur.val.equals(key)) {
                prev.next = cur.next;
            } else {
                prev = cur;
            }
            cur = cur.next;
        }
    }

  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21
  • 22
  • 23

在这里插入图片描述

2.4 查找

contains

判断链表中是否包含某个值，如果包含返回true，否则返回false
循环遍历链表，使用equals方法比较值是否相等，如果有相等的结点返回true

    //是否包含val
    public boolean contains(T val) {
        if (head == null) {
        	//链表为空,返回false
            return false;
        }
        ListNode cur = head;
        while (cur != null) {
            if (cur.val.equals(val)) {
                return true;
            }
            cur = cur.next;
        }
        return false;
    }

  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15

2.4 修改

2.4.1 modify

修改第一个值为oldVal的结点，将其改为newVal
循环遍历链表，找到了该结点就将val修改

    //修改第一次出现的oldVal,将它改为newVal
    public void modify(T oldVal, T newVal) {
        if (head == null) {
            return;
        }
        ListNode cur = head;
        while (cur != null) {
            if (cur.val.equals(oldVal)) {
                cur.val = newVal;
                return;
            }
            cur = cur.next;
        }
    }

  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14

2.4.2 modifyAll

修改所有值为结点oldVal，将其改为newVal
循环链表，直到修改完所有的结点为止

    //修改所有的oldVal,将它改为newVal
    public void modifyAll(T oldVal, T newVal) {
        if (head == null) {
            return;
        }
        ListNode cur = head;
        while (cur != null) {
            if (cur.val.equals(oldVal)) {
                cur.val = newVal;
            }
            cur = cur.next;
        }
    }

  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13

3. 全部代码

//单链表
public class MySignalList<T> {

    static class ListNode {
        public Object val;
        public ListNode next;

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

    public ListNode head;

    //头插
    public void addFirst(T val) {
        ListNode newNode = buyNode(val);
        newNode.next = head;
        head = newNode;
    }

    //尾插
    public void addLast(T val) {
        ListNode newNode = buyNode(val);
        if (head == null) {
            head = newNode;
            return;
        }
        //找尾
        ListNode tail = head;
        while (tail.next != null) {
            tail = tail.next;
        }
        tail.next = newNode;
    }

    //在Index位置插入
    public void addIndex(int Index, T val) {
        //判断Index的合法性
        try {
            if (Index < 0 || Index > size()) {
                throw new IndexNotLegalException("Index不合法");
            }
        } catch (IndexNotLegalException e) {
            e.printStackTrace();
        }
        if (Index == 0) {
            addFirst(val);
            return;
        }
        if (Index == size()) {
            addLast(val);
            return;
        }
        ListNode newNode = buyNode(val);
        ListNode cur = head;
        for (int i = 0; i < Index - 1; i++) {
            cur = cur.next;
        }
        //cur在index前面
        newNode.next = cur.next;
        cur.next = newNode;
    }

    //删除第一次出现的key
    public void remove(T key) {
        if (head == null) {
            return;
        }
        ListNode cur = head;
        ListNode prev = null;
        while (cur != null) {
            if (cur.val.equals(key)) {
                if (prev == null) {
                    head = head.next;
                    return;
                }
                prev.next = cur.next;
                return;
            }
            prev = cur;
            cur = cur.next;
        }
    }

    //删除所有的key
    public void removeAll(T key) {
        if (head == null) {
            return;
        }
        //如果前半部分都是key
        while (head.val.equals(key)) {
            head = head.next;
            if (head == null) {
                return;
            }
        }
        ListNode cur = head.next;
        ListNode prev = head;
        while (cur != null) {
            if (cur.val.equals(key)) {
                prev.next = cur.next;
            } else {
                prev = cur;
            }
            cur = cur.next;
        }
    }

    //是否包含val
    public boolean contains(T val) {
        if (head == null) {
            return false;
        }
        ListNode cur = head;
        while (cur != null) {
            if (cur.val.equals(val)) {
                return true;
            }
            cur = cur.next;
        }
        return false;
    }

    //返回结点
    public ListNode find(T findVal) {
        if (head == null) {
            return null;
        }
        ListNode ret = head;
        while (ret != null) {
            if (ret.val.equals(findVal)) {
                return ret;
            }
            ret = ret.next;
        }
        return null;
    }

    //修改第一次出现的oldVal,将它改为newVal
    public void modify(T oldVal, T newVal) {
        if (head == null) {
            return;
        }
        ListNode cur = head;
        while (cur != null) {
            if (cur.val.equals(oldVal)) {
                cur.val = newVal;
                return;
            }
            cur = cur.next;
        }
    }

    //修改所有的的oldVal,将它改为newVal
    public void modifyAll(T oldVal, T newVal) {
        if (head == null) {
            return;
        }
        ListNode cur = head;
        while (cur != null) {
            if (cur.val.equals(oldVal)) {
                cur.val = newVal;
            }
            cur = cur.next;
        }
    }

    public int size() {
        int size = 0;
        ListNode cur = head;
        while (cur != null) {
            cur = cur.next;
            size++;
        }
        return size;
    }
}

  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21
  • 22
  • 23
  • 24
  • 25
  • 26
  • 27
  • 28
  • 29
  • 30
  • 31
  • 32
  • 33
  • 34
  • 35
  • 36
  • 37
  • 38
  • 39
  • 40
  • 41
  • 42
  • 43
  • 44
  • 45
  • 46
  • 47
  • 48
  • 49
  • 50
  • 51
  • 52
  • 53
  • 54
  • 55
  • 56
  • 57
  • 58
  • 59
  • 60
  • 61
  • 62
  • 63
  • 64
  • 65
  • 66
  • 67
  • 68
  • 69
  • 70
  • 71
  • 72
  • 73
  • 74
  • 75
  • 76
  • 77
  • 78
  • 79
  • 80
  • 81
  • 82
  • 83
  • 84
  • 85
  • 86
  • 87
  • 88
  • 89
  • 90
  • 91
  • 92
  • 93
  • 94
  • 95
  • 96
  • 97
  • 98
  • 99
  • 100
  • 101
  • 102
  • 103
  • 104
  • 105
  • 106
  • 107
  • 108
  • 109
  • 110
  • 111
  • 112
  • 113
  • 114
  • 115
  • 116
  • 117
  • 118
  • 119
  • 120
  • 121
  • 122
  • 123
  • 124
  • 125
  • 126
  • 127
  • 128
  • 129
  • 130
  • 131
  • 132
  • 133
  • 134
  • 135
  • 136
  • 137
  • 138
  • 139
  • 140
  • 141
  • 142
  • 143
  • 144
  • 145
  • 146
  • 147
  • 148
  • 149
  • 150
  • 151
  • 152
  • 153
  • 154
  • 155
  • 156
  • 157
  • 158
  • 159
  • 160
  • 161
  • 162
  • 163
  • 164
  • 165
  • 166
  • 167
  • 168
  • 169
  • 170
  • 171
  • 172
  • 173
  • 174
  • 175
  • 176
  • 177
  • 178

今天的内容就到这里，感谢老铁们的点赞、收藏、评论~❤

声明：本文内容由网友自发贡献，不代表【wpsshop博客】立场，版权归原作者所有，本站不承担相应法律责任。如您发现有侵权的内容，请联系我们。转载请注明出处：https://www.wpsshop.cn/w/Li_阴宅/article/detail/905225
推荐阅读
相关标签

Copyright © 2003-2013 www.wpsshop.cn 版权所有，并保留所有权利。

  

闽ICP备14008679号