Monodyee

这个屌丝很懒，什么也没留下！

热门标签

Java链表入门(超详细)

作者：Monodyee | 2024-02-12 21:49:28

踩

java链表

什么是链表

			说起链表,可以说是让刚接触数据结构的同学非常懵逼的
1

那么什么是链表呢??

~~链表（Linked list）是一种常见的基础数据结构，是一种线性表，但是并不会按线性的顺序存储数据，而是在每一个节点里存到下一个节点的指针(Pointer)。~~

那么这是链表吗,是的,但是究竟是什么意思呢
在这里插入图片描述

其实,链表就像是解密游戏一样,只有到达一个地点,才会有NPC给你下一个地点的地图,从而才能知道下个地点的位置
所以链表也是一样,对于一个链表,一个结点除了要保存结点自身的值以外,还需要保存下一个结点的地址.

这是一个简单链表的单个结点,val代表当前结点存储的值,next是一个引用,指向下一个结点
由于Java中不存在指针,所以结点通常为一个类,而next则是一个结点类实例的引用

可以看到,每一结点都保存了下一个节点的地址,所以,链表不要求每个结点中的地址空间连续

创建链表

–> 怎么创建一个链表呢 <–

1. 创建一个结点

上面说到,链表是由一个一个的结点组成,后一个结点依靠前一个才能找到,那么如何构造结点呢?
在Java中,我们用一个类来表示结点这个结构

//结点类  采用内部类
private static class Node{
	//值
	public int value;
	// Node 节点类型,引用当前结点的下一个结点
	public Node next; 
	
	//构造方法初始化
	/**
     * @param value 值
     */
    public Node(int value){
        this.value = value;
        next = null;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

节点创建完毕,那么,链表究竟有些什么操作呢?

		//头插法
        public void addFirst(int value){}
        //尾插法
        public void addLast(int value){}
        //任意位置插入,第一个数据节点为0号下标
        public boolean addIndex(int index,int value){return false;}
        //查找是否包含关键字key是否在单链表当中
        public boolean contains(int key){return false;}
        //删除第一次出现关键字为key的节点
        public void remove(int key){}
        //删除所有值为key的节点
        public void removeAllKey(int key){}
        //得到单链表的长度
        public int size(){return -1;}
        public void display(){}
        public void clear(){}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

太多了吧!!! 在这里插入图片描述

接下来,一起欣赏每个方法具体如何实现

再此之前,我们要先创建一个链表,此处采用手工创建方法,具体方法后面演示.

public void createLinkedList(){
        Node node = new Node(0);
        Node node1 = new Node(1);
        Node node2 = new Node(2);
        Node node3 = new Node(3);
        Node node4 = new Node(4);

        //创建一个链表
        head = node;
        node.next = node1;
        node1.next  = node2;
        node2.next = node3;
        node3.next = node4;
    }
1
2
3
4
5
6
7
8
9
10
11
12
13
14

2. 插入一个结点

插入一个结点的方式一般有三种,一种头插法,一种尾插法,最后一种指定位置加入元素

头插法 : 在链表的起始位置加入一个元素
尾插法 : 在链表的末尾位置加入一个元素
指定位置插入 : 调用方法时传入index下表,将要加入的元素插入到下标位置

– 头插

在这里插入图片描述

由上述代码创建的链表就长这个样子啦

插入一个元素6,就变成如下模样~~

那么,代码呢!!

	//头插法
    public void addFirst(int val) {
        //根据值创建新结点
        Node node = new Node(val);
        //判断链表是否为空
        if(size == 0){
            this.head = node;
        }else {
            //链表不为空
            node.next = head;
            head = node;
        }
        //元素个数+1
        this.size++;
    }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

– 尾插

和头插法相似,插入后的链表长这个样子

注意:因为这是单向链表,所以,要想插入到最后一个位置,需要遍历链表.
具体代码如下

	//尾插法
    public void addLast(int val) {
        //根据值创建新结点
        Node node = new Node(val);
        //判断链表是否为空
        if (size == 0) {
            this.head = node;
        } else {
            //链表不为空
            //创建临时变量记录头结点,防止遍历后找不到头结点
            Node tmpHead = head;
            Node cur = tmpHead.next;
            while (cur != null) {
                tmpHead = cur;
                cur = cur.next;
            }
            // 循环结束后,tmpHead为最后一个结点
            tmpHead.next = node;
        }
        this.size++;
    }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

– 指定位置插入

对于指定位置插入,需要用户数据需要插入的位置.
如须在上述链表中index = 2 的位置插入10,链表如下

!!! : 第一个元素下标为 0

	//任意位置插入,第一个数据节点为0号下标
    public boolean addIndex(int index, int val) {
        //判断index是否合理
        if(index < 0 || index > this.size){
            System.out.println("输入下标不合理...");
            return false;
        }
        Node node = new Node(val);

        Node tmpHead = this.head;

        //如果index为0进行头插
        if(index == 0){
            node.next = head;
            head = node;
            return true;
        }

        //循环结束后,tmpHead 在待插入位置的前一个位置
        while (index > 1){
            tmpHead = tmpHead.next;
            index--;
        }

        node.next = tmpHead.next;
        tmpHead.next = node;

        this.size++;

        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

插入操作到此结束

3.查找是否包含关键字key是否在单链表当中

遍历链表,按个查找即可

	//查找是否包含关键字key是否在单链表当中
    public boolean contains(int key) {
        //记录头结点
        Node next = this.head;

        //遍历每一个结点
        while (next != null) {
            //如果找到,返回true
            if (next.value == key) {
                return true;
            }
            next = next.next;
        }
        //未找到,返回 false
        return false;
    }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

4.删除元素

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

关键之处在于
node = next;
next = next.next;

	//删除第一次出现关键字为key的节点
    public void remove(int key) {
        if (!contains(key)) {
            System.out.println("没有该元素");
        }
        Node next = this.head;
        Node node = next;
        //判断第一个元素
        if (next.value == key) {
            this.head = next.next;
            next.next = null;
            this.size--;
            return;
        }
        //循环判断后续元素
        while (next != null) {
            if (next.value == key) {
                //跳过中间元素
                node.next = next.next;
                //置空
                next.next = null;
                //元素减一
                this.size--;
                return;
            }
            //让 next 始终在 node 的下一个元素
            node = next;
            next = next.next;
        }
    }
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

–删除所有值为key的节点

与删除一个元素不同的是,删除所有key值元素在循环判断时找到指定元素时不退出,继续进行查找,直到链表遍历完成.

	//删除所有值为key的节点
    public void removeAllKey(int key) {
        if (this.head == null) {
            return;
        }

        Node cur = this.head.next;
        Node pre = this.head;

        //遍历整个链表,判断每个元素
        while (cur != null) {
            if (cur.value == key) {
                // 跳过 指定元素
                pre.next = cur.next;
            } else {
                pre = cur;
            }
            cur = cur.next;
        }
        /*
        Node cur = this.head.next;
        Node pre = this.head;
        上述代码跳过了head.value
        所以需要单独判断
        */
        if (this.head.value == key) {
            this.head = this.head.next;
        }
    }
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

4.得到单链表的长度

	//得到单链表的长度
 	public int size() {
        return this.size;
    }
1
2
3
4

5.清空链表

直接使用 this.head = null;可以达到一样的效果,但此处对每个结点引用置空.

	public void clear() {
        this.size = 0;
        Node tmp;
        while (head.next != null) {
            tmp = this.head.next;
            //置空
            head.next = null;
            head = tmp;
        }
        this.head = null;
    }
1
2
3
4
5
6
7
8
9
10
11

6.打印链表

	//打印链表
    public void display() {
        Node tmp = this.head;
        System.out.print("[");
        while (tmp != null) {
            if (tmp.next == null) System.out.print(tmp.value);
            else System.out.print(tmp.value + ",");
            tmp = tmp.next;
        }
        System.out.println("]");
    }
1
2
3
4
5
6
7
8
9
10
11

7.反转链表

反转链表的核心在于,需要一个pre记录下一个结点是否为空,因为在程序运行过程中,cur会断开与下一个节点的连接,所以需要单独添加引用记录.

  	//反转链表
    public Node reverse() {
        if (this.size == 0) {
            return null;
        }
        if (head.next == null) {
            return head;
        }
        Node cur = head.next;
        head.next = null;
        //pre记录下一个元素
        Node pre;
        while (cur != null) {
            pre = cur.next;
            cur.next = head;
            head = cur;
            cur = pre;
        }
        return head;
    }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

8.返回中间结点

采用快慢指针的思想,慢指针一次移动一步,快指针一次移动2步,当快指针移动到链表末尾时,慢指针就在链表中间位置

  	//返回中间结点
    public Node middleNode() {
        Node fast = head;
        Node slow = head;
        while(fast != null && fast.next != null){
            fast = fast.next.next;
            slow = slow.next;
        }
        return slow;
    }
1
2
3
4
5
6
7
8
9
10

9.创建一个链表

传入一个数组快速创建一个链表,实际中,根据情况做判断.

	//创建一个链表
	public void create(int[] arr){
        if(this.head != null){
            System.out.println("链表不为空!");
        }
        Node tmp = null;
        for (int i = 0; i < arr.length; i++) {
            Node node = new Node(arr[i]);
            if(this.head == null){
                this.head = node;
                tmp = this.head;
            }
            tmp.next = node;
            tmp = tmp.next;
        }
        this.size = arr.length;
    }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

到这里为止,关于链表的基本操作就结束了…
下面是整个源码.
对于链表,以上演示的是无头单向不循环链表,对应的还有很多的不同实现的链表,如,有头双向循环链表
对于循环链表,就是每一个结点都记录了前后2个节点的引用,
对于双向链表,就是除了头结点外,还记录了尾节点.

无头结点单向链表

//无头结点单向链表
public class LinkedList {

    //结点类
    private static class Node {
        public int value;
        public Node next;

        public Node(int value) {
            this.value = value;
            next = null;
        }
    }

    //指定头结点为空
    private Node head = null;
    private int size = 0;

    public void createLinkedList() {
        Node node = new Node(0);
        Node node1 = new Node(1);
        Node node2 = new Node(2);
        Node node3 = new Node(3);
        Node node4 = new Node(4);

        //创建一个链表
        head = node;
        node.next = node1;
        node1.next = node2;
        node2.next = node3;
        node3.next = node4;
        size = 5;
    }

    //头插法
    public void addFirst(int val) {
        //根据值创建新结点
        Node node = new Node(val);
        //判断链表是否为空
        if (size == 0) {
            this.head = node;
        } else {
            //链表不为空
            node.next = head;
            head = node;
        }
        this.size++;
    }

    //尾插法
    public void addLast(int val) {
        //根据值创建新结点
        Node node = new Node(val);
        //判断链表是否为空
        if (size == 0) {
            this.head = node;
        } else {
            //链表不为空
            //创建临时变量记录头结点,防止遍历后找不到头结点
            Node tmpHead = head;
            Node cur = tmpHead.next;
            while (cur != null) {
                tmpHead = cur;
                cur = cur.next;
            }
            // 循环结束后,tmpHead为最后一个结点
            tmpHead.next = node;
        }
        this.size++;
    }

    //任意位置插入,第一个数据节点为0号下标
    public boolean addIndex(int index, int val) {
        //判断index是否合理
        if (index < 0 || index > this.size) {
            System.out.println("输入下标不合理...");
            return false;
        }
        Node node = new Node(val);

        Node tmpHead = this.head;

        //如果index为0进行头插
        if (index == 0) {
            node.next = head;
            head = node;
            return true;
        }

        //循环结束后,tmpHead 在待插入位置的前一个位置
        while (index > 1) {
            tmpHead = tmpHead.next;
            index--;
        }

        node.next = tmpHead.next;
        tmpHead.next = node;

        this.size++;

        return true;
    }

    //查找是否包含关键字key是否在单链表当中
    public boolean contains(int key) {
        //记录头结点
        Node next = this.head;

        //遍历每一个结点
        while (next != null) {
            //如果找到,返回true
            if (next.value == key) {
                return true;
            }
            next = next.next;
        }
        //未找到,返回 false
        return false;
    }

    //删除第一次出现关键字为key的节点
    public void remove(int key) {
        if (!contains(key)) {
            System.out.println("没有该元素");
        }
        Node next = this.head;
        Node node = next;
        //判断第一个元素
        if (next.value == key) {
            this.head = next.next;
            next.next = null;
            this.size--;
            return;
        }
        //循环判断后续元素
        while (next != null) {
            if (next.value == key) {
                //跳过中间元素
                node.next = next.next;
                //置空
                next.next = null;
                //元素减一
                this.size--;
                return;
            }
            //让 next 始终在 node 的下一个元素
            node = next;
            next = next.next;
        }
    }

    //删除所有值为key的节点
    public void removeAllKey(int key) {
        if (this.head == null) {
            return;
        }

        Node cur = this.head.next;
        Node pre = this.head;

        //遍历整个链表,判断每个元素
        while (cur != null) {
            if (cur.value == key) {
                // 跳过 指定元素
                pre.next = cur.next;
            } else {
                pre = cur;
            }
            cur = cur.next;
        }


        /*
        Node cur = this.head.next;
        Node pre = this.head;
        上述代码跳过了head.value
        所以需要单独判断
        */
        if (this.head.value == key) {
            this.head = this.head.next;
        }
    }

    //得到单链表的长度
    public int size() {
        return this.size;
    }

    //打印链表
    public void display() {
        Node tmp = this.head;
        System.out.print("[");
        while (tmp != null) {
            if (tmp.next == null) System.out.print(tmp.value);
            else System.out.print(tmp.value + ",");
            tmp = tmp.next;
        }
        System.out.println("]");
    }

    //清空链表
    public void clear() {
        this.size = 0;
        Node tmp;
        while (head.next != null) {
            tmp = this.head.next;
            head.next = null;
            head = tmp;
        }
        this.head = null;
    }

    //反转链表
    public Node reverse() {
        if (this.size == 0) {
            return null;
        }
        if (head.next == null) {
            return head;
        }

        Node cur = head.next;
        head.next = null;
        //pre记录下一个元素
        Node pre;
        while (cur != null) {
            pre = cur.next;
            cur.next = head;
            head = cur;
            cur = pre;
        }
        return head;
    }

    //返回中间结点
    public Node middleNode() {
        Node fast = head;
        Node slow = head;
        while(fast != null && fast.next != null){
            fast = fast.next.next;
            slow = slow.next;
        }
        return slow;
    }


    public void create(int[] arr){
        if(this.head != null){
            System.out.println("链表不为空!");
        }
        Node tmp = null;
        for (int i = 0; i < arr.length; i++) {
            Node node = new Node(arr[i]);
            if(this.head == null){
                this.head = node;
                tmp = this.head;
            }
            assert tmp != null;
            tmp.next = node;
            tmp = tmp.next;
        }
        this.size = arr.length;
    }
}
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
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264

双向循环链表


	public class MyDoubleLinkedList {

    static private class Node {
        public int val;
        //记录前一个结点
        public Node pre;
        //记录后一个结点
        public Node next;

        public Node(int val) {
            this.val = val;
            this.pre = null;
            this.next = null;
        }
    }

	//记录头结点
    private Node head;
    //记录尾结点
    private Node last;

    //头插法
    public void addFirst(int val) {
        Node tmp = new Node(val);
        if (head == null) {
            head = tmp;
            last = head;
        } else {
            tmp.next = head;
            head.pre = tmp;
            head = tmp;
        }
    }

    //尾插法
    public void addLast(int val) {
        Node tmp = new Node(val);
        if (head == null) {
            head = tmp;
            last = head;
        } else {
            last.next = tmp;
            tmp.pre = last;
            last = tmp;
        }
    }

    //任意位置插入,第一个数据节点为0号下标
    public void addIndex(int index, int val) {
        if (index < 0 || index > size()) {
            System.out.println("下标越界");
        }
        Node tmp = new Node(val);
        Node next = head;
        if(head == null){
            head = tmp;
            last = tmp;
            return;
        }
        if (index == 0) {
            tmp.next = head;
            head.pre = tmp;
            head = tmp;
            return;
        }
        if (index == size()) {
            last.next = tmp;
            tmp.pre = last;
            last = tmp;
            return;
        }

        while (index > 0) {
            next = next.next;
            index--;
        }
        next.pre.next = tmp;
        tmp.next = next;
        tmp.pre = next.pre;
        next.pre = tmp;
    }

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

    //删除第一次出现关键字为key的节点
    public boolean remove(int key) {
        if(head == null || head.next == null){
            head = null;
            return true;
        }
        if(head.val == key){
            head = head.next;
            head.pre = null;
            return true;
        }
        Node tmp = head;
        while (tmp.val != key){
            tmp = tmp.next;
            if(tmp == null){
                return false;
            }
        }

        if(tmp == last){
            last.pre.next = null;
            return true;
        }
        tmp.pre.next = tmp.next;
        tmp.next.pre = tmp.pre;
        return true;
    }

    //删除所有值为key的节点
    public void removeAllKey(int key) {
        boolean b = true;
        while (b){
            b = false;
            boolean remove = remove(key);
            if(remove) b = true;
        }
    }

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

    public void display() {
        Node next = head;
        System.out.print("[");
        while (next != null) {
            System.out.print(next.val + " ");
            next = next.next;
        }
        System.out.println("]");
    }

    public void clear() {
        while (head.next != null){
            head = head.next;
            head.pre = null;
        }
        head = null;
        last = null;
    }
}

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

Java标准库中的链表

在Java标准库中,内置了一个双向链表LinkedList类

方法	解释
boolean add(E e)	尾插 e
void add(int index, E element)	将 e 插入到 index 位置
boolean addAll(Collection<? extends E> c)	尾插 c 中的元素
E remove(int index)	删除 index 位置元素
boolean remove(Object o)	删除遇到的第一个 o
E get(int index)	获取下标 index 位置元素
E set(int index, E element)	将下标 index 位置元素设置为 element
void clear()	清空
boolean contains(Object o)	判断 o 是否在线性表中
int indexOf(Object o)	返回第一个 o 所在下标
int lastIndexOf(Object o)	返回最后一个 o 的下标
List subList(int fromIndex, int toIndex)	截取部分 list

LinkedList代码演示

public static void main(String[] args) {
	LinkedList<Integer> list = new LinkedList<>();
	list.add(1); // add(elem): 表示尾插
	list.add(2);
	list.add(3);
	list.add(4);
	list.add(5);
	list.add(6);
	list.add(7);
	System.out.println(list.size());
	System.out.println(list);
	// 在起始位置插入0
	list.add(0, 0); // add(index, elem): 在index位置插入元素elem
	System.out.println(list);
	list.remove(); // remove(): 删除第一个元素，内部调用的是removeFirst()
	list.removeFirst(); // removeFirst(): 删除第一个元素
	list.removeLast(); // removeLast(): 删除最后元素
	list.remove(1); // remove(index): 删除index位置的元素
	System.out.println(list);
	// contains(elem): 检测elem元素是否存在，如果存在返回true，否则返回		false
	if(!list.contains(1)){
		list.add(0, 1);
	}
	list.add(1);
	System.out.println(list);
	System.out.println(list.indexOf(1)); // indexOf(elem): 从前往后找到第一个elem的位置
	System.out.println(list.lastIndexOf(1)); // lastIndexOf(elem): 从后往前找第一个1的位置
	int elem = list.get(0); // get(index): 获取指定位置元素
	list.set(0, 100); // set(index, elem): 将index位置的元素设置为elem
	System.out.println(list);
	// subList(from, to): 用list中[from, to)之间的元素构造一个新的LinkedList返回
	List<Integer> copy = list.subList(0, 3); 
	System.out.println(list);
	System.out.println(copy);
	list.clear(); // 将list中元素清空
	System.out.println(list.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

运行结果
在这里插入图片描述

LinkedList 和 ArrayList 的区别

不同点	ArrayList	LinkedList
存储空间上	物理上一定连续	逻辑上连续，但物理上不一定连续
随机访问	支持O(1)	不支持：O(N)
头插	需要搬移元素，效率低O(N)	只需修改引用的指向，时间复杂度为O(1)
插入	空间不够时需要扩容	没有容量的概念
应用场景	元素高效存储+频繁访问	任意位置插入和删除频繁

第一次发博客,希望大家多多支持

在这里插入图片描述
新人博主水平有限,如有不足,多多指正.

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