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

Java数据结构之链表（单链表）_java 单链表代表类都有哪些

作者：酷酷是懒虫 | 2024-07-30 20:17:33

赞

踩

java 单链表代表类都有哪些

文章目录

提示：以下是本篇文章正文内容，Java系列学习将会持续更新

一、链表

概念

链表：逻辑上连续，多个节点采用挂载式进行连接。但是物理上非连续存储结构。（火车）
在这里插入图片描述
结构：从头开始遍历，一直到达尾部。
火车：当数据空间不够时，就新增一节车厢挂载到火车尾。
在这里插入图片描述

结构

链表的结构十分多样，以下条件组合起来会有8种链表结构：
  ①单向、双向
  ②带头、不带头
  ③循环、非循环
重点掌握其中两种：
  ①无头单向非循环链表：结构简单，一般不会单独用来存数据。实际中更多是作为其他数据结构的子结构，如哈希桶、图的邻接表等等。另外这种结构在笔试面试中出现很多。
  ②无头双向链表：在Java的集合框架库中LinkedList底层实现就是无头双向循环链表。

回到目录…

二、无头单链表

图解

单向遍历，默认从前向后遍历。只能从头部车厢开始遍历，依次走到尾部。
请添加图片描述

代码实现

/*火车车厢类，一个车厢只能存放一个元素*/
public class Node {
    //存放具体数据
    int value;
    //保存下一个车厢的地址
    Node next;
    public Node(int value){ this.value = value;}
}


  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
/**
 * 火车类，是由多个车厢连接起来的
 */
public class SingleLinkedList {
    //当前火车中车厢节点的个数(实际就是元素的个数)
    private int size;
    //当前火车的头车厢地址
    private Node head;

    /****  添加  *********************/
    //头插法
    public void addFirst(int value){
        //新建一个车厢节点
        Node node = new Node(value);
        //先判断当前火车是否为空
        if(head == null){
            head = node;
        }else{
            //火车头有节点，要把当前新车厢挂载到火车头部
            //先把原本的头部车厢指向新车厢的下一节
            node.next = head;
            //再将这个新增的车厢node指向头部head
            head = node;
        }
        size++;
    }
    //索引插入
    public void addIndex(int index,int value){
        //先判断是否索引越界
        if(index<0||index>size){
            System.err.println("add index illegal!");
            return;
        }
        //index==0，说明是头插
        if(index == 0){
            addFirst(value);
            return;
        }
        //创建一个新的车厢
        Node node = new Node(value);
        //建一个prev，寻找插入位置的前驱,从头节点开始向后走index-1步
        Node prev = head;
        for(int i=0;i<index-1;i++){
            prev = prev.next;
        }
        //node的下一节指向前驱temp的下一节
        node.next = prev.next;
        //前驱的下一节指向node
        prev.next = node;
        size++;
    }
    //尾插
    public void addLast(int value){
        addIndex(size,value);
    }

    /****  查找  *********************/
    //返回索引处value的值
    public int get(int index){
        if(rangeCheck(index)){
            //从头节点开始，走到index的位置
            Node node = head;
            for(int i=0;i<index;i++){
                node = node.next;
            }
            return node.value;
        }else{
            System.err.println("get index illegal!");
            return -1;
        }
    }
    //判断链表中是否有value这个数据、
    public boolean contains(int value){
        for(Node temp=head;temp!=null;temp=temp.next){
            if(temp.value == value)
                return true;
        }
        return false;
    }

    /****  修改  *********************/
    //将单链表中索引为index的元素修改，并返回修改前的值
    public int set(int index,int value){
        if(rangeCheck(index)){
            Node node = head;
            for(int i=0;i<index;i++){
                node = node.next;
            }
            int old = node.value;
            node.value = value;
            return old;
        }else{
            System.err.println("set index illegal!");
            return -1;
        }
    }

    /****  删除  *********************/
    //删除索引处的数据
    public void removeIndex(int index){
        if(rangeCheck(index)){
            if(index == 0){
                Node temp = head;
                head = head.next;
                temp.next = null;
                size--;
            }else{
                //找到待删除节点的前驱
                Node prev = head;
                for(int i=0;i<index-1;i++){
                    prev = prev.next;
                }
                //cur表示待删除节点
                Node cur = prev.next;
                prev.next = cur.next;
                cur.next = null;
                size--;
            }
        }else{
            System.err.println("remove index illegal!");
        }
    }
    //删除单链表中的第一个value值
    public void removeOnceValue(int value){
        //遍历链表，找到value的节点的前驱
        //头节点没有前驱，要特殊处理
        if(head!=null && head.value == value){
            removeIndex(0);
            return;
        }
        //找待删节点的前驱，该前驱的下一节点就是value
        Node prev = head;
        while(prev.next != null){
            if(prev.next.value == value){
                //cur就是待删节点
                Node cur = prev.next;
                prev.next = cur.next;
                cur.next = null;
                size--;
                return;
            }
            //prev不是待删节点的前驱，让prev继续向后走
            prev = prev.next;
        }
    }
    //删除单链表中的全部value值
    public void removeAllValue(int value){
        //判断头节点是否为待删除节点
        while(head!=null && head.value==value){
            head = head.next;
            size--;
        }
        if(head == null){
            //说明链表中全是待删节点，此时链表被删空
            return;
        }else{
            //此时head一定不是待删节点,再看链表中的其它节点
            Node prev = head;
            while(prev.next != null){
                if(prev.next.value == value){
                    //cur就是待删节点
                    Node cur = prev.next;
                    prev.next = cur.next;
                    cur.next = null;
                    size--;
                }else{
                    //只有确保prev的下一个不是待删节点，才让prev继续向后走一步
                    prev = prev.next;
                }
            }
        }
    }

    //打印
    public String toString(){
        String str = "";
        //遍历这个火车类，从头部(head)走到尾部
        //暂时存储头节点地址，避免遍历结束影响head的值
        Node node = head;
        while(node != null){
            str += node.value;
            str += " -> ";
            //当前地址指向下一节车厢的地址
            node = node.next;
        }
        str += "NULL";
        return str;
    }

    //判断 查、改、删操作时，索引是否越界
    private boolean rangeCheck(int index){
        if(index<0||index>=size)
            return false;
        else
            return true;
    }
}


  • 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
  • 179
  • 180
  • 181
  • 182
  • 183
  • 184
  • 185
  • 186
  • 187
  • 188
  • 189
  • 190
  • 191
  • 192
  • 193
  • 194
  • 195
  • 196
  • 197
  • 198

特点

1.每次增、删操作时，都要改动size的值
2.每当对head进行操作时，必须先考虑head是否为空. (防止空指针异常)
3.进行查、改、删操作时，需要判断用户输入的索引是否越界[0,size)
4.在进行索引插入和删除操作时，都需要找前驱节点。(但是头节点没有前驱，所以要特殊处理)

回到目录…

三、带头单链表

为何引入带头单链表

 因为初学的单链表每次插入和删除元素时，都需要找前驱；此时需要特殊处理头节点。(因为头节点没有前驱)
 为了避免这一步繁琐的操作，将所有节点都一视同仁 ——> 不用处理头节点 ——> 虚拟头节点(这个节点仅仅作为链表的头部，不储存具体元素) ——> 火车头不坐乘客请添加图片描述

代码实现

/**
 * 带头单链表
 */
public class SingleLinkedListWithHead {
    //表示当前链表中元素的个数
    private int size;
    //创建虚拟头节点
    private Node dummyHead = new Node(-1);

    /****  添加  *********************/
    public void addIndex(int index,int value){
        //判断index合法性
        if(index<0 || index>size){
            System.err.println("add index illegal!");
            return;
        }
        //此时的插入就不可能是头插
        Node node = new Node(value);
        //找到插入位置的前驱
        Node prev = dummyHead;
        for(int i=0;i<index;i++){
            //因为链表的头部有个虚拟节点，所以要走index步才行
            prev = prev.next;
        }
        //此时prev指向待插位置的前驱
        node.next = prev.next;
        prev.next = node;
        size++;
    }
    public void addFirst(int value){
        addIndex(0,value);
    }
    public void addLast(int value){
        addIndex(size,value);
    }

    /****  查找  *********************/
    //返回索引处value的值
    public int get(int index){
        if(rangeCheck(index)){
            Node node = dummyHead.next;
            for(int i=0;i<index;i++){
                node = node.next;
            }
            return node.value;
        }else{
            System.err.println("get index illegal!");
            return -1;
        }
    }
    //判断链表中是否有value这个数据
    public boolean contains(int value){
        for(Node temp=dummyHead.next;temp!=null;temp=temp.next){
            if(temp.value == value)
                return true;
        }
        return false;
    }

    /****  修改  *********************/
    //将单链表中索引为index的元素修改，并返回修改前的值
    public int set(int index,int value){
        if(rangeCheck(index)){
            Node node = dummyHead.next;
            for(int i=0;i<index;i++){
                node = node.next;
            }
            int old = node.value;
            node.value = value;
            return old;
        }else{
            System.err.println("set index illegal!");
            return -1;
        }
    }

    /****  删除  *********************/
    public void removeIndex(int index){
        if(rangeCheck(index)){
            Node prev = dummyHead;
            for(int i=0;i<index;i++){
                prev = prev.next;
            }
            Node cur = prev.next;
            prev.next = cur.next;
            cur.next = null;
            size--;
        }else{
            System.err.println("remove index illegal!");
        }
    }
    public void removeOnceValue(int value){
        Node prev = dummyHead;
        while(prev.next!=null){
            if(prev.next.value == value){
                Node cur = prev.next;
                prev.next = cur.next;
                cur.next = null;
                size--;
                return;
            }
            prev = prev.next;
        }
    }
    public void removeAllValue(int value){
        Node prev = dummyHead;
        while(prev.next!=null){
            if(prev.next.value == value){
                Node cur = prev.next;
                prev.next = cur.next;
                cur.next = null;
                size--;
            }else{
                prev = prev.next;
            }
        }
    }

    public String toString(){
        String str = "";
        Node temp = dummyHead.next;
        while(temp!=null){
            str += temp.value;
            str += " -> ";
            temp = temp.next;
        }
        str += "NULL";
        return str;
    }

    private boolean rangeCheck(int index){
        if(index<0 || index>=size)
            return false;
        else
            return true;
    }

    public int size(){
        return this.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

注意

1.虚拟头节点的值最好取value范围之外的值。Node dummyHead = new Node(value:-1);
2.dummyHead只是虚假的节点，进行查、改操作时，要避开它，从它的下一个节点开始遍历。

回到目录…

总结:
提示：这里对文章进行总结：
以上就是今天的学习内容，本文是Java数据结构的链表部分，介绍了链表的实现原理，以及带头单链表的引入。之后的学习内容将持续更新！！！

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

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

  

闽ICP备14008679号