forked from TheAlgorithms/Java
-
Notifications
You must be signed in to change notification settings - Fork 0
Expand file tree
/
Copy pathDoublyLinkedList.java
More file actions
214 lines (188 loc) · 4.82 KB
/
DoublyLinkedList.java
File metadata and controls
214 lines (188 loc) · 4.82 KB
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
/**
* This class implements a DoublyLinkedList. This is done using the classes
* LinkedList and Link.
*
* A linked list is simplar to an array, it holds values. However,
* links in a linked list do not have indees. 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
*
*/
class DoublyLinkedList{
/** Head refers to the front of the list */
private Link head;
/** Tail refers to the back of the list */
private Link tail;
/**
* Constructor
*/
public DoublyLinkedList(){
head = null;
tail = null;
}
/**
* 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
}
/**
* 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 -->
tail.next = newLink; // currentTail(tail) --> newLink -->
newLink.previous = tail; // currentTail(tail) <--> newLink -->
tail = newLink; // oldTail <--> newLink(tail) -->
}
/**
* Delete the element at the head
*
* @return The new head
*/
public Link deleteHead(){
Link temp = head;
head = head.next; // oldHead <--> 2ndElement(head)
head.previous = null; // oldHead --> 2ndElement(head) nothing pointing at old head so will be removed
if(head == null)
tail = null;
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
tail.next = null; // 2ndLast(tail) --> null
return temp;
}
/**
* Delete the element from somewhere in the list
*
* @param x element to be deleted
* @return Link deleted
*/
public Link delete(int x){
Link current = head;
while(current.value != x) //Find the position to delete
current = current.next;
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
}
return current;
}
/**
* 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
}
}
/**
* 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();
}
}
/**
* 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.insertTail(11);
myList.display(); // <-- 10(head) <--> 7 <--> 13 <--> 11(tail) -->
myList.deleteTail();
myList.display(); // <-- 10(head) <--> 7 <--> 13(tail) -->
myList.delete(7);
myList.display(); // <-- 10(head) <--> 13(tail) -->
myList.insertOrdered(23);
myList.insertOrdered(67);
myList.insertOrdered(3);
myList.display(); // <-- 3(head) <--> 10 <--> 13 <--> 23 <--> 67(tail) -->
}
}