链表是我们日常编程中使用频率最高的数据结构之一，它的定义为：
一种链式存储的线性表，用一组地址任意的存储单元存放线性表的数据元素，称存储单元为一个节点。
链表也是线性表的一种，与同是线性表的顺序表比起来，却有很大的区别：
- 顺序表由数组实现，会有存储空间的限制。而链表由一个个存储节点组成，理论上不存在空间限制。
- 顺序表的元素的访问时间复杂度为O(1)，而链表节点的访问时间复杂度为O(n)。
- 顺序表删除插入节点时间复杂度为O(n)，而链表为O(1)。
关于链表的具体解释，大家可以参考：
链表及相关函数实现
接下来，以Collection接口中的LinkedList类为模板，为大家介绍双链表的实现。
复制代码
1
2
3
public class LinkedList<E>
extends AbstractSequentialList<E>
implements List<E>, Deque<E>, Cloneable, java.io.SerializableLinkedList是集合类的一种，定义里的继承以及实现关系是集合类要掌握的知识，和我们今天主题不搭边，有兴趣了解集合类的同学可以参考:
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
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
package myLinkedList;
import java.util.ConcurrentModificationException;
import java.util.Iterator;
import java.util.NoSuchElementException;
public class MyLinkedList<T> implements Iterable<T> {
/**
* 内部属性
*/
// 链表长度
private int theSize;
// 链表修改次数，主要用于iterator对象中方法的使用
private int modCount = 0;
// 存储链表头节点，方便操作
private Node<T> head;
// 存储链表尾节点，同上
private Node<T> tail;
/**
* 由内部类来存储链表节点数据
*/
private static class Node<T> {
private T value;
private Node<T> pre;
private Node<T> next;
public Node(T value, Node<T> pre, Node<T> next) {
this.value = value;
this.pre = pre;
this.next = next;
}
}
// 无参构造
public MyLinkedList() {
// 调用构造方法时，初始化双链表
doClear();
}
/*********************** MyLinkedList 对外显示的方法 ***************************/
/**
* 清空双链表
*/
public void clear() {
doClear();
}
/**
* 返回双链表长度
* @return 双链表长度
*/
public int size() {
return this.theSize;
}
/**
* 双链表是否为空
* @return true双链表为空， false双链表不为空
*/
public boolean isEmpty() {
return size() == 0;
}
/**
* 双链表尾插
* @param x 尾插元素的值
* @return 成功插入
*/
public boolean add(T x) {
add(size(), x);
return true;
}
/**
* 在指定下标处添加元素
* @param index 要插入节点的位置
* @param x 要插入节点的值
* @return 成功插入
*/
public boolean add(int index, T x) {
addBefore(getNode(index, 0, size()), x);
return true;
}
/**
* 取指定下标节点的值
* @param index 下标
* @return 节点的值
*/
public T get(int index) {
return getNode(index).value;
}
/**
* 设置指定下标的元素值，并返回旧的值
* @param index 要设置的节点的位置
* @param newValue 设置的值
* @return 返回旧的值
*/
public T set(int index, T newValue) {
Node<T> node = getNode(index);
T old = node.value;
node.value = newValue;
return old;
}
/**
* 删除指定下标的元素，并返回删除元素的值
* @param index 要删除的节点的位置
* @return 删除节点的值
*/
public T remove(int index) {
return remove(getNode(index));
}
/*********************** MyLinkedList 内部方法 ***************************/
/**
* 清空双链表
*/
private void doClear() {
this.head = new Node<>(null, null, null);
this.tail = new Node<>(null, head, null);
head.next = tail;
this.theSize = 0;
this.modCount++;
}
/**
* 在指定节点前插入值为x的元素
* @param node 位置
* @param x 插入节点的值
*/
private void addBefore(Node<T> node, T x) {
Node<T> newNode = new Node<>(x, node.pre, node);
newNode.pre.next = newNode;
newNode.next.pre = newNode;
this.theSize++;
this.modCount++;
}
/**
* 删除指定元素
* @param node 要删除的节点
* @return 删除节点的值
*/
private T remove(Node<T> node) {
node.pre.next = node.next;
node.next.pre = node.pre;
this.theSize++;
this.modCount++;
return node.value;
}
/**
* 根据指定下标得到对应的节点
* @param index 下标
* @return 指定下标的节点
*/
private Node<T> getNode(int index) {
return getNode(index, 0, size()-1);
}
/**
* 在指定范围内根据下标找到对应节点
* @param index 要查找的节点下标
* @param lower 范围下界
* @param upper 范围上界
* @return 对应下标的节点
*/
private Node<T> getNode(int index, int lower, int upper) {
Node<T> cur = null;
if(index<lower || index>upper) {
throw new IndexOutOfBoundsException();
}
// 根据index的大小，分别从头或尾出发，这对于链表的查找来说能够提高效率
if(index < size()/2) {
cur = this.head;
for(int i = 0; i < index; i++) {
cur = cur.next;
}
} else {
cur = this.tail;
for(int i = size(); i > index; i--) {
cur = cur.pre;
}
}
return cur;
}
/**
* 模拟实现LinkedList类的iterator方法
* @return Iterator的一个对象
*/
@Override
public Iterator<T> iterator() {
// 这里我们返回一个继承了 iterator 接口的嵌套类
return new LinkedListIterator();
}
/**
* 继承了Iterator接口的实现类
*/
private class LinkedListIterator implements Iterator<T> {
private Node<T> currentNode = head;
private int expectedModCount = modCount;
private boolean canRemove = false;
@Override
public boolean hasNext() {
return currentNode !=
tail;
}
@Override
public T next() {
if(modCount != expectedModCount) {
throw new ConcurrentModificationException();
}
if(!hasNext()) {
throw new NoSuchElementException();
}
T nextValue = currentNode.value;
currentNode = currentNode.next;
canRemove = true;
return nextValue;
}
@Override
public void remove() {
if(modCount != expectedModCount) {
throw new ConcurrentModificationException();
}
if(!canRemove) {
throw new IllegalStateException();
}
MyLinkedList.this.remove(currentNode.pre);
expectedModCount++;
canRemove = false;
}
}
}
关于LinkedList模拟实现代码，我已上传至 我的GitHub，欢迎大家指导。
最后
以上就是粗心万宝路最近收集整理的关于Java数据结构-2 链表，模拟LinkedList实现的全部内容，更多相关Java数据结构-2内容请搜索靠谱客的其他文章。
本图文内容来源于网友提供，作为学习参考使用，或来自网络收集整理，版权属于原作者所有。
发表评论 取消回复