FazBrowse GitHub Viewer
|
Trending
|
URL:
|
Home
Tools:
[Download Repo ZIP]
[View Raw Code]
[Original HTTPS Page]
Java/DataStructures/Lists/DoublyLinkedList.java at master · java66liu/Java · GitHub
java66liu
/
Java
Public
forked from
TheAlgorithms/Java
Notifications
You must be signed in to change notification settings
Fork
0
Star
0
Code
Pull requests
0
Actions
Projects
Security and quality
0
Insights
Additional navigation options
Code
Pull requests
Actions
Projects
Security and quality
Insights
Expand file tree
Breadcrumbs
Java
/
DataStructures
/
Lists
/
DoublyLinkedList.java
Copy path
More file actions
More file actions
Latest commit
History
History
History
248 lines (221 loc) · 6.55 KB
Breadcrumbs
Java
/
DataStructures
/
Lists
/
DoublyLinkedList.java
Copy path
File metadata and controls
248 lines (221 loc) · 6.55 KB
Raw
Copy raw file
Download raw file
Open symbols panel
Edit and raw actions
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
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
;
/**
* Default Constructor
*/
public
DoublyLinkedList
() {
head
=
null
;
tail
=
null
;
}
/**
* 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
);
}
}
/**
* 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 -->
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) -->
}
}
/**
* 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
if
(
tail
==
null
) {
head
=
null
;
}
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
}
}
/**
* 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) -->
}
}
Back
|
FazBrowse Home
|
New Git URL