This repository was archived by the owner on Dec 21, 2021. It is now read-only.
-
Notifications
You must be signed in to change notification settings - Fork 0
Expand file tree
/
Copy pathDoubleLinkedList.java
More file actions
157 lines (136 loc) · 4.38 KB
/
Copy pathDoubleLinkedList.java
File metadata and controls
157 lines (136 loc) · 4.38 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
/* This class is a variation on the LinkedList class. Adding and removing happens in O(1) no matter at which side.
* It is actually a LinkedList and a reversed LinkedList combined.
* Each element of the list has a pointer to the next and the previous element.
* This means that the structure can be traversed in two directions.
* Author: Seppe Lampe
*/
public class DoubleLinkedList {
private class DoubleLinkedListElement {
private Object data;
private DoubleLinkedListElement nextElement;
private DoubleLinkedListElement previousElement;
public DoubleLinkedListElement(Object v, DoubleLinkedListElement next, DoubleLinkedListElement previous) {
data = v;
nextElement = next;
previousElement = previous;
if (nextElement != null) nextElement.previousElement = this;
if (previousElement != null) previousElement.nextElement = this;
}
public DoubleLinkedListElement(Object v) {
this(v,null , null);
}
public DoubleLinkedListElement previous() { //O(1)
return previousElement;
}
public Object value() { //O(1)
return data;
}
public DoubleLinkedListElement next() { //O(1)
return nextElement;
}
public void setNext(DoubleLinkedListElement value) { //O(1)
nextElement = value;
}
public void setPrevious(DoubleLinkedListElement value) { //O(1)
previousElement = value;
}
}
private int count ;
private DoubleLinkedListElement head;
private DoubleLinkedListElement tail;
public DoubleLinkedList() {
head = null;
tail = null;
count = 0;
}
// This method returns the first element of the DoubleLinkedList
public Object getFirst() { //O(1)
return head.value();
}
// This method returns the last element of the DoubleLinkedList
public Object getLast() { //O(1)
return tail.value();
}
// This method returns the size of the DoubleLinkedList
public int size() { //O(1)
return count;
}
// This method adds an element to the front of the DoubleLinkedList
public void addFirst(Object value) { //O(1)
head = new DoubleLinkedListElement (value, head, null);
if (tail == null) tail = head;
count++;
}
// This method adds an element to the back of the DoubleLinkedList
public void addLast(Object value) { //O(1)
tail = new DoubleLinkedListElement (value , null , tail);
if (head == null) head = tail;
count++;
}
// This method removes the first of the DoubleLinkedList
public void removeFirst() { //O(1)
if(head != null) {
head = head.next();
if(head == null) tail = null;
else head.setPrevious(null);
count--;
}
}
// This method removes the last of the DoubleLinkedList
public void removeLast() { //O(1)
if(tail != null) {
tail = tail.previous();
if(tail == null) head = null;
else tail.setNext(null);
count--;
}
}
// This method prints out a representation of the DoubleLinkedList
public void print() { //O(n)
DoubleLinkedListElement d = head;
System.out.print("(");
while (d != null)
{
System.out.print(d.value() + " ");
d = d.next();
}
System.out.println(")");
}
// This method prints out a representation of the reverse of the DoubleLinkedList
public void printReverse() { //O(n)
DoubleLinkedListElement d = tail;
System.out.print("(");
while (d != null)
{
System.out.print(d.value() + " ");
d = d.previous();
}
System.out.println(")");
}
// This method returns a String representation of the elements in the DoubleLinkedList
public String toString() { //O(n)
String result = new String();
DoubleLinkedListElement plus = head;
while (plus != null) {
result += plus.value().toString() + " ";
plus = plus.next();
}
result = result.substring(0, result.length() - 1); // Remove the space before the closing bracket
return result;
}
// This method reverses a DoubleLinkedList
public void reverse() { //O(n)
head = tail;
DoubleLinkedListElement temp = head;
DoubleLinkedListElement plus = head.previous();
head.nextElement = head.previousElement;
DoubleLinkedListElement prev = head;
while(plus!=null) {
plus = plus.previous();
temp = temp.next();
temp.nextElement = plus;
temp.previousElement = prev;
prev = temp;
}
}
}