手写链表

什么是链表

​ 链表是一种物理存储结构上非连续存储结构,数据元素的逻辑顺序是通过链表中的引用次序来实现的。通俗的说链表就是由一个个结点组成,这些结点逻辑上连续,物理上不连续。

单向链表

​ 结点中只有一个引用的链表叫做单向链表,这是最简单的链表结构。由两部分组成:data域、next域

  • data域:数据域,用来存储元素数据。
  • next域:用于指向下一个结点。

1.png

优点:

  1. 在找出结点后,插入和删除速度相对于循环表更快。
  2. 不需要预分配空间,元素个数不受限制。

缺点:

  1. 查找数据元素的速度相较于顺序表更慢。

代码实现:

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
public class SingleLinkedList<T> {

private Node head;
private int size;

public SingleLinkedList(){
this.head = null;
this.size = 0;
}

private class Node{
private Node next;
private T t;

public Node(T t,Node next){
this.t = t;
this.next = next;
}

public Node(T t){
this(t,null);
}
}

/**
* 头部插入结点
* @param t
*/
public void addHead(T t){
Node node;
if (null==this.head){
node = new Node(t);
}else{
node = new Node(t,this.head);
}
this.head = node;
this.size++;
}

/**
* 尾部插入结点
* @param t
*/
public void addRear(T t){
this.add(t,this.size);
}

/**
* 根据索引插入结点
* @param t
* @param index
*/
public void add(T t,int index){
if (index<0||index>this.size){
return;
}
if (index == 0){
this.addHead(t);
return;
}
Node preNode = this.head;
for (int i = 0; i < index - 1; i++) {
preNode = preNode.next;
}
Node node = new Node(t,preNode.next);
preNode.next = node;
this.size++;
}

/**
* 删除头结点
*/
public void removeHead(){
if (null==this.head){
return;
}
this.head = this.head.next;
this.size--;
}

/**
* 删除尾结点
*/
public void removeRear(){
if (null==this.head){
return;
}
Node cur = this.head;
Node pre = null;
while (null!=cur.next){
pre = cur;
cur = cur.next;
}
pre.next = null;
this.size--;
}

/**
* 删除匹配的结点
* @param t
*/
public void remove(T t){
if (null==this.head){
return;
}
if (this.size == 1 || this.head.t.equals(t)){
this.removeHead();
return;
}
Node cur = this.head;
while (null!=cur.next){
if (cur.next.t.equals(t)){
cur.next = cur.next.next;
cur = cur.next;
this.size--;
}else{
cur = cur.next;
}
}
}

/**
* 使用虚拟结点方式删除结点
* @param t
*/
public void removeElt(T t){
Node dummy = new Node(t,this.head);
Node cur = dummy;
while (null!=cur.next){
if (cur.next.t.equals(t)){
cur.next = cur.next.next;
this.size--;
}else{
cur = cur.next;
}
}
this.head = dummy.next;
}

/**
* 使用虚拟结点方式插入结点
* @param t
* @param des
*/
public void insert(T t,T des){
Node dummy = new Node(null,this.head);
Node dNode = new Node(des);
Node cur = dummy;
while (null!=cur.next){
if (cur.next.t.equals(t)){
dNode.next = cur.next;
cur.next = dNode;
this.size++;
break;
}else{
cur = cur.next;
}
}
this.head = dummy.next;
}

/**
* 判断链表中是否存在该结点
* @param t
* @return
*/
public boolean contains(T t){
Node cur = this.head;
while (null!=cur){
if (cur.t.equals(t)){
return true;
}else{
cur = cur.next;
}
}
return false;
}

/**
* 获取链表长度
* @return
*/
public int getSize(){
return this.size;
}

/**
* 遍历链表
* @return
*/
@Override
public String toString() {
StringBuffer sb = new StringBuffer();
Node cur = this.head;
while (cur!=null){
sb.append(cur.t+"->");
cur = cur.next;
}
sb.append("NULL");
return sb.toString();
}
}

双向链表

​ 结点中有两个引用的链表叫做双向链表。由三部分组成:data域、next域、front域

  • data域:数据域,用来存储元素数据。
  • next域:用于指向后一节点。
  • front域:用于指向前一节点。

2.png

优点:

  1. 在单链表的基础上进一步改进,查找元素可以反向查找前缀结点,一定程度上提升了查找数据的速度。

缺点:

  1. 需要记录前缀结点,增加了额外的内存空间开销。

代码实现:

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
public class TwoWayLinkedList<T> {
private int size;
private Node head;

private class Node{
private T t;
private Node next;
private Node pre;

public Node(T t){
this(t,null,null);
}

public Node(T t,Node next){
this(t,next,null);
}

public Node(T t,Node next,Node pre){
this.t = t;
this.next = next;
this.pre = pre;
}
}

/**
* 头部插入结点
* @param t
*/
public void addHead(T t){
Node node;
if (null==this.head){
node = new Node(t);
}else{
node = new Node(t,this.head);
this.head.pre = node;
}
this.head = node;
this.size++;
}

/**
* 尾部插入结点
* @param t
*/
public void addRear(T t){
this.add(t,this.size);
}

/**
* 根据索引插入结点
* @param t
* @param index
*/
public void add(T t,int index){
if (index<0||index>this.size){
return;
}
if (index == 0){
this.addHead(t);
return;
}
Node preNode = this.head;
for (int i = 0; i < index - 1; i++) {
preNode = preNode.next;
}
Node node = new Node(t,preNode.next,preNode);
if (index != this.size){
preNode.next.pre = node;
}
preNode.next = node;
this.size++;
}

/**
* 删除头结点
*/
public void removeHead(){
if (null==this.head){
return;
}
this.head.next.pre = null;
this.head =this.head.next;
this.size--;
}

/**
* 删除尾结点
*/
public void removeRear(){
if (null==this.head){
return;
}
Node cur = this.head;
while (null!=cur.next){
cur = cur.next;
}
cur.pre.next = null;
this.size--;
}

/**
* 删除匹配的结点
* @param t
*/
public void remove(T t){
if (null==this.head){
return;
}
if (this.size == 1 || this.head.t.equals(t)){
this.removeHead();
return;
}
Node cur = this.head;
while (null!=cur.next){
if (cur.next.t.equals(t)){
cur.next.next.pre = cur.next.pre;
cur.next = cur.next.next;
cur = cur.next;
this.size--;
}else{
cur = cur.next;
}
}
}

/**
* 使用虚拟结点方式删除结点
* @param t
*/
public void removeElt(T t){
Node dummy = new Node(null,this.head);
Node cur = dummy;
while (null!=cur.next){
if (cur.next.t.equals(t)){
cur.next.next.pre = cur.next.pre;
cur.next = cur.next.next;
this.size--;
}else{
cur = cur.next;
}
}
this.head = dummy.next;
}

/**
* 使用虚拟结点方式插入结点
* @param t
* @param des
*/
public void insert(T t,T des){
Node dummy = new Node(null,this.head);
Node node = new Node(des);
Node cur = dummy;
while (null!=cur.next){
if (cur.next.t.equals(t)){
node.pre = cur.next.pre;
node.next = cur.next;
cur.next.pre = node;
cur.next = node;
this.size++;
break;
}else {
cur = cur.next;
}
}
this.head = dummy.next;
}

/**
* 判断链表中是否存在该结点
* @param t
* @return
*/
public boolean contains(T t){
Node cur = this.head;
while (null!=cur){
if (cur.t.equals(t)){
return true;
}else{
cur = cur.next;
}
}
return false;
}

/**
* 获取链表长度
* @return
*/
public int getSize(){
return this.size;
}

/**
* 遍历链表
* @return
*/
@Override
public String toString() {
StringBuffer sb = new StringBuffer();
Node cur = this.head;
while (null!=cur){
sb.append("['pre':"+(null!=cur.pre?cur.pre.t:cur.pre)+",'data:'"+cur.t+",'next':"+(null!=cur.next?cur.next.t:cur.next)+"]->");
cur = cur.next;
}
sb.append("NULL");
return sb.toString();
}

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

测试

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
public class Main {
public static void main(String[] args) {
// 单向链表测试
// SingleLinkedList<String> list = new SingleLinkedList<>();
// list.add("s0",0);
// list.addHead("s2");
// list.addRear("s55");
// list.add("s1",1);
// list.insert("s0","s22");
// System.out.println(list);
// list.removeHead();
// list.removeRear();
// list.remove("s2");
// list.removeElt("s2");
// System.out.println(list);

// 双向链表测试
// TwoWayLinkedList<String> list = new TwoWayLinkedList<>();
// list.add("s0",0);
// list.addHead("s11");
// list.addRear("s33");
// list.add("s55",1);
// System.out.println(list);
// list.insert("s0","s99");
// System.out.println(list);
// list.removeHead();
// list.removeRear();
// list.remove("s55");
// list.removeElt("s55");
// System.out.println(list);
}
}

总结

关于循环链表和静态链表后续,我再更新上来。

3.png