单向链表
单向链表比顺序结构的线性表最大的好处就是不用保证存放的位置，它只需要用指针去指向下一个元素就能搞定。
单链表图解
图画的比较粗糙，简单的讲解一下：
上面四个长方形，每个长方形都是一个节点。在长方形中，一种包含两个东西，一个是当前节点的元素，一个是指向下一节点的地址。这个下一个节点的地址指向了下一个节点中的元素。以此类推。
在最左边的叫做头节点，同样，最后面的叫尾节点。
所以，我们所有的操作都是根据节点来进行操作。
代码
这些代码都有很详细的注释，我就不做过多的解释了，你直接复制代码到本地idea运行一遍就全部知道了。
|
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
|
package com.zxy.lianbiao;/** * @Author Zxy * @Date 2021/2/3 21:25 * @Version 1.0 *//** * 基于单向链表实现元素的存取 * * @param <E> */public class MySinglyLinkedList<E> implements MyList<E> { /** * 定义单向链表中的节点对象 */ class Node<E> { private E item; // 存储元素 private Node next; // 存储下一个节点对象 public Node(E item, Node next) { this.item = item; this.next = next; } } private Node head; // 存放链表中的头节点 private int size; // 记录元素的个数 /** * 向链表中添加元素 * * @param element */ @Override public void add(E element) { // 创建节点 Node<E> node = new Node<>(element, null); // 找到尾节点 Node tail = getTail(); // 节点的挂接 if (tail == null) { // 如果没有尾节点，那意思就是头节点都不存在 // 没有头节点，那么就把创建的节点给头节点 this.head = node; } else { tail.next = node; } // 记录元素的个数 this.size++; } /** * 找尾节点 */ private Node getTail() { // 判断头节点是否存在 if (this.head == null) { return null; } // 查找尾节点 Node node = this.head; while (true) { if (node.next == null) { break; } node = node.next; // 移动指针指向下一个 } return node; } /** * 根据元素的位置获取元素 * * @param index * @return */ @Override public E get(int index) { // 校验index的合法性 this.checkIndex(index); // 根据位置获取指定节点 Node<E> node = this.getNode(index); // 将该节点中的元素返回 return node.item; } /** * 对index进行校验 */ private void checkIndex(int index) { // 0<=index<size if (!(index >= 0 && index < this.size)) { throw new IndexOutOfBoundsException("Index: " + index + " this.size: " + this.size); } } /** * 根据位置获取节点 */ private Node<E> getNode(int index) { Node<E> node = this.head; for (int i = 0; i < index; i++) { node = node.next; } return node; } /** * 获取元素的个数 * * @return */ @Override public int size() { return this.size; } /** * 根据元素位置删除元素 * * @param index * @return */ @Override public E remove(int index) { // 校验index合法性 this.checkIndex(index); // 根据位置找到节点对象 Node<E> node = getNode(index); // 获取该节点对象中的元素 E item = node.item; // 将该节点对象从单向链表中移除 // 判断当前删除的节点是否为头节点 if (this.head == node) { this.head = node.next; } else { Node<E> temp = this.head; for (int i = 0; i < index - 1; i++) { temp = temp.next; // 此时的temp就是要删除的那个节点的前一个节点 } temp.next = node.next; // 将当前节点的前一个节点指向当前节点的后一个节点 } // 然后将当前节点的下一个节点指向null node.next = null; // 记录元素个数 this.size--; // 将该元素返回 return item; } /** * 插入节点思路：如果当前共有三个节点分别是1，2，3，在1和2的中间插入4，原本的指向是1->2 现改变成1->4 4->2 先获取到指定位置的node，再获取到前一个位置的node和下一个位置的node */ public void insert(int index, E element) { // 先根据要插入的位置拿到这个位置的节点对象 Node<E> item = getNode(index); // 根据插入的元素新建一个节点 Node<E> eNode = new Node<>(element, null); // 如果是头节点，那么就找不到前一个，直接把这个赋值给head if (index == 0){ // index==0代表是替换掉头节点 this.head = eNode; eNode.next = item; this.size++; }else { // 根据当前的节点对象去找到前一个节点对象和后一个节点对象 Node<E> before = this.head; // 根据头节点去找 for (int i = 0; i < index - 1; i++) { before = before.next; // 此时的before就是当前节点的前一个节点 } before.next = eNode; eNode.next = item; this.size++; } } public static void main(String[] args) { MySinglyLinkedList<String> list = new MySinglyLinkedList<>(); System.out.println("添加节点开始------------------------"); list.add((String) "a"); list.add((String) "b"); list.add((String) "c"); list.add((String) "d"); System.out.println("添加节点完成-------------------------\n"); System.out.println("插入指定的元素"); list.insert(0,"f"); for (int i = 0; i < list.size; i++) { System.out.println(list.get(i)); } }} |
双向链表
昨天写完单向链表和栈结构之后，看了看程杰大大的书中有介绍双向链表的部分。虽然是c语言写的，但是我还是用Java给翻译出来了。
思路如下：
首先，双向链表和单向链表的最大区别就是，双向链表比单链表多了个指向前一节点的指针。代码量其实并不比单链表多很多，只是思路的转变需要克服一下。
其次就是在插入元素的时候，我们可以在链表的头部插入，也可以在链表的尾部插入（因为有两个指针嘛）
编码
代码其实和单链表差不多，如果感兴趣的话可以去看看我之前写的单链表的文章。虽然文笔很烂，但是代码货真价实。
|
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
|
package com.zxy.lianbiao;/** * @Author Zxy * @Date 2021/2/4 20:11 * @Version 1.0 *//** * 基于双向链表实现元素存取的容器 * * @param <E> */public class MyDoublyLinkedList<E> implements MyList<E> { /** * 定义双向链表节点对象 */ class Node<E> { E item; // 记录元素 Node<E> prev; // 记录前一个节点对象 Node<E> next; // 记录下一个节点对象 public Node(Node<E> prev, E item, Node<E> next) { this.item = item; this.prev = prev; this.next = next; } } private Node head; // 记录头节点 private Node tail; // 记录尾节点 private int size; // 记录元素个数 /** * 向双向链表中添加元素的方法 * * @param element */ @Override public void add(E element) { linkLast(element); } /** * 将节点对象添加到双向链表的尾部 */ private void linkLast(E element) { Node t = this.tail; // 获取尾节点 Node<E> node = new Node<>(t, element, null); // 创建节点对象 this.tail = node; // 将新节点定义为尾节点 因为原来的尾节点被这个新节点替代了 if (t == null) { // 说明一个节点都没有，这个还得是头节点 this.head = node; } else { t.next = node; } this.size++; } /** * 根据指定位置获取元素 * * @param index * @return */ @Override public E get(int index) { this.checkIndex(index); // 根据位置查找节点对象 Node<E> node = this.getNode(index); return node.item; } /** * 对index的合法性校验 */ private void checkIndex(int index) { if (!(index >= 0 && index < this.size)) { throw new IndexOutOfBoundsException(); } } /** * 根据位置获取指定节点对象 */ private Node getNode(int index) { // 判断当前位置距离头或者尾哪个节点更近 使用二分法 if (index < (this.size >> 1)) { Node node = this.head; for (int i = 0; i < index; i++) { node = node.next; } return node; } else { Node node = this.tail; for (int i = this.size - 1; i > index; i--) { node = node.prev; } return node; } } /** * 返回元素的个数 * * @return */ @Override public int size() { return this.size; } /** * 删除元素 * * @param index * @return */ @Override public E remove(int index) { // 对index进行合法性校验 this.checkIndex(index); Node node = this.getNode(index); // 根据位置获取到节点对象 // 获取节点对象的元素 E item = (E) node.item; // 判断当前节点是否为头节点 if (node.prev == null) { this.head = node.next; } else { node.prev.next = node.next; } // 判断当前节点是否为尾节点 if (node.next == null) { // node.prev.next = null; this.tail = node.prev; } else { node.next.prev = node.prev; } // 当前节点断掉与他后继节点的连接 node.next = null; // 当前节点断掉与直接前驱节点的连接 node.prev = null; node.item = null; this.size--; return item; } /** * 在双向链表的头添加元素 */ public void addFirst(E element) { this.linkFirst(element); } /** * 在链表的头添加元素 * * @param element */ public void linkFirst(E element) { // 获取头节点对象 Node head = this.head; Node<E> eNode = new Node<>(null, element, head); // 将新节点定义为头节点 this.head = eNode; if (head == null) { // 如果为空，说明该链表中一个节点都没有 也就是该头节点也是尾节点 this.tail = eNode; } else { head.prev = eNode; } this.size++; } /** * 在链表的尾部添加元素 * * @param element */ public void addLast(E element) { this.linkLast(element); } public static void main(String[] args) { MyDoublyLinkedList<String> list = new MyDoublyLinkedList<>(); list.add("a"); list.add("b"); list.add("c"); list.add("d"); list.add("e"); System.out.println(list.remove(2)); System.out.println(list.size); for (int i = 0; i < list.size(); i++) { System.out.println(list.get(i)); } }} |
总结
本篇文章就到这里了，希望能给你带来帮助，也希望您能够多多关注服务器之家的更多内容！
原文链接：https://blog.csdn.net/weixin_43581288/article/details/113660067
