大作业！
这本来是一个学习数据结构过程中的大作业，实现双向链表，但是没有给答案，自己试着实现了一下，基本的增删查改的功能都实现了，如果有需要的欢迎拿去使用啊！！
双向链表
链表是一个真正的动态数据结构，相对于数组来说不用实现反复的扩容和”减容”的过程，可以有效的规避复杂度的震荡。
但是单向链表无法查看上一个节点，对于许多的查找不是很方便，特此实现一下双向链表。
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
package Alibrary.DS.list;
import javafx.util.Pair;
/**
* @ author: yxh
* @ created: 2021-12-21 : 9:26 PM
*/
public class LinkedListD<E> {
/**
* 定义内部类作为双向链表的节点
*/
private class Node {
//定义三个变量，节点的值，节点的上一个节点，与下一个节点
private E e;
private Node prev;
private Node next;
//带赋值的节点
public Node(E e) {
this.e = e;
}
private Node() {
}
@Override
public String toString() {
return e.toString();
}
}
//定义头节点和尾节点和链表大小
private Node head;
private Node tail;
private int size;
public LinkedListD() {
head = null;
tail = null;
size = 0;
}
public int getSize() {
return size;
}
public boolean isEmpty() {
return size == 0;
}
/**
* @description 这一部分为列表的快速查值，包括当前，前后，头尾
* @author yxh
* @date 2021-12-21 22:38:52
* @para * @param: index
* @return
*/
//返回对应index的node（对于后面复现使用很方便，用while遍历也可）
public Node getNode(int index){
if(isEmpty() && (index > size-1))
throw new IndexOutOfBoundsException("Index : "+index + " is out of range");
Node temp = head;
for (int i = 0; i < index - 1; i++) {
temp = temp.next;
}
return temp.next;
}
//根据index返回值
public E getValue(int index){
return getNode(index) == null ? null : getNode(index).e;
}
//根据node返回值
public E getValue(Node node){
return node == null ? null : node.e;
}
//返回下一个节点，若没有返回null
public Node getNextNode(Node node){
return node.next == null ? null : node.next;
}
//返回上一个节点，若没有返回null
public Node getPrevNode(Node node){
return node.prev == null ? null : node.prev;
}
//返回头节点
public Node getHead(){
return head;
}
//返回尾节点
public Node getTail(){
return tail;
}
/**
* @description 这一部分是对于链表的增删
* @author yxh
* @date 2021-12-21 22:42:16
* @para * @param: index
* @param: e
* @return
*/
//增加一个新的节点
public void add(int index, E e) {
if (index < 0 || index > size)
throw new IllegalArgumentException("Add failed. Illegal index.");
Node node = new Node(e);
if (isEmpty()) {//如果为空，直接生成一个节点
head = node;
tail = node;
} else {
if (index == 0) {//在头部增加，则直接替换head
Node temp = head;
head = node;
temp.prev = head;
head.next = temp;
} else if (index > size - 1) {//在尾部增加，则直接替换tail
Node temp = tail;
tail = node;
temp.next = tail;
tail.prev = temp;
} else {
Node temp = getNode(index);
Node prev = temp.prev;
prev.next = node;
node.next = temp;
temp.prev = node;
node.prev = prev;
}
}
size++;
}
public void addFirst(E e) {
add(0, e);
}
public void addLast(E e) {
add(size, e);
}
//删除一个节点
public E remove(int index) {
if (index < 0 || index >= size)
throw new IllegalArgumentException("Remove failed. Index is illegal.");
Node temp = new Node();
if (index == 0) {
head = head.next;
head.prev = null;
} else if (index > size - 1) {
tail = tail.prev;
tail.next = null;
} else {
temp = getNode(index);
Node prev = temp.prev;
Node next = temp.next;
prev.next = next;
next.prev = prev;
temp.next = null;
temp.prev = null;
}
size++;
return temp.e;
}
public E removeFirst() {
return remove(0);
}
public E removeLast() {
return remove(size - 1);
}
/**
* @description 这部分是改
* @author yxh
* @date 2021-12-21 22:47:49
* @para * @param: index
* @param: e
* @return
*/
public void set(int index, E e) {
if (index < 0 || index >= size)
throw new IllegalArgumentException("Set failed. Illegal index.");
Node cur = head;
for (int i = 0; i < index; i++)
cur = cur.next;
cur.e = e;
}
public boolean contains(E e) {
Node cur = head;
while (cur != null) {
if (cur.e.equals(e))
return true;
cur = cur.next;
}
return false;
}
@Override
public String toString() {
StringBuilder res = new StringBuilder();
Node cur = head;
while (cur != null) {
res.append(cur + "->");
cur = cur.next;
}
res.append("NULL");
return res.toString();
}
}
