forked from TheAlgorithms/Java
-
Notifications
You must be signed in to change notification settings - Fork 0
/
DoublyLinkedList.java
357 lines (322 loc) · 9.43 KB
/
DoublyLinkedList.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
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
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
package DataStructures.Lists;
/**
* This class implements a DoublyLinkedList. This is done using the classes LinkedList and Link.
*
* <p>A linked list is similar to an array, it holds values. However, links in a linked list do not
* have indexes. With a linked list you do not need to predetermine it's size as it grows and
* shrinks as it is edited. This is an example of a double ended, doubly linked list. Each link
* references the next link and the previous one.
*
* @author Unknown
*/
public class DoublyLinkedList {
/** Head refers to the front of the list */
private Link head;
/** Tail refers to the back of the list */
private Link tail;
/** Size refers to the number of elements present in the list */
private int size;
/** Default Constructor */
public DoublyLinkedList() {
head = null;
tail = null;
size = 0;
}
/**
* Constructs a list containing the elements of the array
*
* @param array the array whose elements are to be placed into this list
* @throws NullPointerException if the specified collection is null
*/
public DoublyLinkedList(int[] array) {
if (array == null) throw new NullPointerException();
for (int i : array) {
insertTail(i);
}
size = array.length;
}
/**
* Insert an element at the head
*
* @param x Element to be inserted
*/
public void insertHead(int x) {
Link newLink = new Link(x); // Create a new link with a value attached to it
if (isEmpty()) // Set the first element added to be the tail
tail = newLink;
else head.previous = newLink; // newLink <-- currenthead(head)
newLink.next = head; // newLink <--> currenthead(head)
head = newLink; // newLink(head) <--> oldhead
++size;
}
/**
* Insert an element at the tail
*
* @param x Element to be inserted
*/
public void insertTail(int x) {
Link newLink = new Link(x);
newLink.next = null; // currentTail(tail) newlink -->
if (isEmpty()) { // Check if there are no elements in list then it adds first element
tail = newLink;
head = tail;
} else {
tail.next = newLink; // currentTail(tail) --> newLink -->
newLink.previous = tail; // currentTail(tail) <--> newLink -->
tail = newLink; // oldTail <--> newLink(tail) -->
}
++size;
}
/**
* Insert an element at the index
*
* @param x Element to be inserted
* @param index Index(from start) at which the element x to be inserted
*/
public void insertElementByIndex(int x, int index) {
if (index > size) throw new IndexOutOfBoundsException("Index: " + index + ", Size: " + size);
if (index == 0) {
insertHead(x);
} else {
if (index == size) {
insertTail(x);
} else {
Link newLink = new Link(x);
Link previousLink = head; //
for (int i = 1; i < index; i++) { // Loop to reach the index
previousLink = previousLink.next;
}
// previousLink is the Link at index - 1 from start
previousLink.next.previous = newLink;
newLink.next = previousLink.next;
newLink.previous = previousLink;
previousLink.next = newLink;
}
}
++size;
}
/**
* Delete the element at the head
*
* @return The new head
*/
public Link deleteHead() {
Link temp = head;
head = head.next; // oldHead <--> 2ndElement(head)
if (head == null) {
tail = null;
} else {
head.previous =
null; // oldHead --> 2ndElement(head) nothing pointing at old head so will be removed
}
--size;
return temp;
}
/**
* Delete the element at the tail
*
* @return The new tail
*/
public Link deleteTail() {
Link temp = tail;
tail = tail.previous; // 2ndLast(tail) <--> oldTail --> null
if (tail == null) {
head = null;
} else {
tail.next = null; // 2ndLast(tail) --> null
}
--size;
return temp;
}
/**
* Delete the element from somewhere in the list
*
* @param x element to be deleted
* @return Link deleted
*/
public void delete(int x) {
Link current = head;
while (current.value != x) { // Find the position to delete
if (current != tail) {
current = current.next;
} else { // If we reach the tail and the element is still not found
throw new RuntimeException("The element to be deleted does not exist!");
}
}
if (current == head) deleteHead();
else if (current == tail) deleteTail();
else { // Before: 1 <--> 2(current) <--> 3
current.previous.next = current.next; // 1 --> 3
current.next.previous = current.previous; // 1 <--> 3
}
--size;
}
/**
* Inserts element and reorders
*
* @param x Element to be added
*/
public void insertOrdered(int x) {
Link newLink = new Link(x);
Link current = head;
while (current != null && x > current.value) // Find the position to insert
current = current.next;
if (current == head) insertHead(x);
else if (current == null) insertTail(x);
else { // Before: 1 <--> 2(current) <--> 3
newLink.previous = current.previous; // 1 <-- newLink
current.previous.next = newLink; // 1 <--> newLink
newLink.next = current; // 1 <--> newLink --> 2(current) <--> 3
current.previous = newLink; // 1 <--> newLink <--> 2(current) <--> 3
}
++size;
}
/**
* Deletes the passed node from the current list
*
* @param z Element to be deleted
*/
public void deleteNode(Link z) {
if (z.next == null) {
deleteTail();
} else if (z == head) {
deleteHead();
} else { // before <-- 1 <--> 2(z) <--> 3 -->
z.previous.next = z.next; // 1 --> 3
z.next.previous = z.previous; // 1 <--> 3
}
--size;
}
public static void removeDuplicates(DoublyLinkedList l) {
Link linkOne = l.head;
while (linkOne.next != null) { // list is present
Link linkTwo = linkOne.next; // second link for comparison
while (linkTwo.next != null) {
if (linkOne.value == linkTwo.value) // if there are duplicates values then
l.delete(linkTwo.value); // delete the link
linkTwo = linkTwo.next; // go to next link
}
linkOne = linkOne.next; // go to link link to iterate the whole list again
}
}
/**
* Reverses the list in place
*
* @param l the DoublyLinkedList to reverse
*/
public void reverse() {
// Keep references to the head and tail
Link thisHead = this.head;
Link thisTail = this.tail;
// Flip the head and tail references
this.head = thisTail;
this.tail = thisHead;
// While the link we're visiting is not null, flip the
// next and previous links
Link nextLink = thisHead;
while (nextLink != null) {
Link nextLinkNext = nextLink.next;
Link nextLinkPrevious = nextLink.previous;
nextLink.next = nextLinkPrevious;
nextLink.previous = nextLinkNext;
// Now, we want to go to the next link
nextLink = nextLinkNext;
}
}
/** Clears List */
public void clearList() {
head = null;
tail = null;
size = 0;
}
/**
* Returns true if list is empty
*
* @return true if list is empty
*/
public boolean isEmpty() {
return (head == null);
}
/** Prints contents of the list */
public void display() { // Prints contents of the list
Link current = head;
while (current != null) {
current.displayLink();
current = current.next;
}
System.out.println();
}
/**
* Prints the contents of the list in reverse order
*/
public void displayBackwards() {
Link current = tail;
while (current != null) {
current.displayLink();
current = current.previous;
}
System.out.println();
}
}
/**
* This class is used to implement the nodes of the linked list.
*
* @author Unknown
*/
class Link {
/** Value of node */
public int value;
/** This points to the link in front of the new link */
public Link next;
/** This points to the link behind the new link */
public Link previous;
/**
* Constructor
*
* @param value Value of node
*/
public Link(int value) {
this.value = value;
}
/** Displays the node */
public void displayLink() {
System.out.print(value + " ");
}
/**
* Main Method
*
* @param args Command line arguments
*/
public static void main(String args[]) {
DoublyLinkedList myList = new DoublyLinkedList();
myList.insertHead(13);
myList.insertHead(7);
myList.insertHead(10);
myList.display(); // <-- 10(head) <--> 7 <--> 13(tail) -->
myList.displayBackwards();
myList.insertTail(11);
myList.display(); // <-- 10(head) <--> 7 <--> 13 <--> 11(tail) -->
myList.displayBackwards();
myList.deleteTail();
myList.display(); // <-- 10(head) <--> 7 <--> 13(tail) -->
myList.displayBackwards();
myList.delete(7);
myList.display(); // <-- 10(head) <--> 13(tail) -->
myList.displayBackwards();
myList.insertOrdered(23);
myList.insertOrdered(67);
myList.insertOrdered(3);
myList.display(); // <-- 3(head) <--> 10 <--> 13 <--> 23 <--> 67(tail) -->
myList.insertElementByIndex(5, 1);
myList.display(); // <-- 3(head) <--> 5 <--> 10 <--> 13 <--> 23 <--> 67(tail) -->
myList.displayBackwards();
myList.reverse(); // <-- 67(head) <--> 23 <--> 13 <--> 10 <--> 5 <--> 3(tail) -->
myList.display();
myList.clearList();
myList.display();
myList.displayBackwards();
myList.insertHead(20);
myList.display();
myList.displayBackwards();
}
}