-
Notifications
You must be signed in to change notification settings - Fork 1
/
DoublyLinkedList.java
240 lines (192 loc) · 10.7 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
/**
* Created by jkeys on 9/23/2015.
*/
import java.util.*;
public class DoublyLinkedList {
/* instance variables */
DIntNode head;
DIntNode tail;
/* constructors */
public DoublyLinkedList() {
head = new DIntNode();
tail = new DIntNode();
head.setNext(tail);
tail.setPrev(head);
}
/* getters and setters */
public DIntNode getHead() { return head; }
public DIntNode getTail() { return tail; }
public void setHead(DIntNode _head) { head = _head; }
public void setTail(DIntNode _tail) { tail = _tail; }
/**
* Add an element to the end of the list.
* @param element The element to be added.
*/
public void addEnd(int element) {
DIntNode tailPrev = tail.getPrev(); //get ref to the now-second-to-last node
DIntNode newTail = new DIntNode(element, tailPrev, tail); //create the new last node
tail.setPrev(newTail); //and link it with the tail dummy node
tailPrev.setNext(newTail);
}
//let n = the number of nodes in the list.
//To remove a node from the head, takes 5+0n operations. (Same number of operations if one node in list, or one thousand.)
//Specifically, two accesses to reference variables and three assignments.
//Therefore, this method has O(1) running time, constant.
/**
* Remove the head node.
*/
public void removeFromHead() {
DIntNode nodeToRemove = head.getNext(); //get reference to the node we're removing
DIntNode newHead = nodeToRemove.getNext(); //and reference to the new actual head
nodeToRemove.setPrev(null); //remove links contained in node we're removing
nodeToRemove.setNext(null);
head.setNext(newHead); //and link the new actual head back with the dummy head.
newHead.setPrev(head);
}
//simple toString method
public String toString() {
StringBuilder result = new StringBuilder("(Forward)\t"); //StringBuilder for efficient concat; much quicker
DIntNode rover = head.getNext(); //than constant String allocation (String being immutable in Java)
//walk forward
while(rover != tail) {
result.append("(" + rover.getData() + ")");
if(rover.getNext() != tail) //skip adding arrow for final iteration
result.append("<-->");
rover = rover.getNext(); //walk fwd
}
result.append("\n(Backward)\t");
rover = tail.getPrev();
//walk backwards
while(rover != head) {
result.append("(" + rover.getData() + ")");
if(rover.getPrev() != head) //skip adding arrow for final iteration
result.append("<-->");
rover = rover.getPrev(); //walk backwd
}
return result.toString(); //String return type for toString methods, call toString on StringBuilder
}
//copied with slight tweaks from Lab4
private int size() {
int count = 0;
DIntNode rover = head.getNext();
while(rover != tail) {
count++;
rover = rover.getNext();
}
return count;
}
/**
* Return a DoublyLinkedList containing the sub list starting at beginIdx and ending at endIdx. The precondition(s) is (are)
* that the indexes must be within bounds, and beginIdx < endIdx.
* @param beginIdx The index of the new head copied from the old list.
* @param endIdx The index of the new tail copied from the old list.
* @return A DoublyLinkedListObject containing the sub list.
*/ //O(n), linear, complexity
public DoublyLinkedList subList(int beginIdx, int endIdx) {
if(beginIdx < 0 || beginIdx > endIdx || endIdx >= size()) //3 operations
throw new IndexOutOfBoundsException();
DIntNode rover = head.getNext(); //1 operation
//walk forward the appropriate number of times (min of 0, if beginIdx == 0)
for(int i = 0; i < beginIdx; i++) { //beginIdx operations; beginIdx <= n; worst case, n operations.
if(rover != tail) //n operations
rover = rover.getNext(); //n operations (worst-case)
}
//create the newList which will contain a COPY
DoublyLinkedList newList = new DoublyLinkedList(); //1 operation (roughly, more like 3 with constructor)
//create the new head of the list and a couple of reference variables to walk over the old and new list respectively
//copy the head to begin with and create its node object. Link its prev up to the dummy.
DIntNode newHead = new DIntNode(rover.getData(), newList.getHead(), null); //1 operation
DIntNode newListRover = newHead; //1 operation
DIntNode newNode;
//loop the number of elements to be copied minus 1 (the head has already been copied, see previous lines)
for(int i = 0; i < (endIdx - beginIdx); i++) { //<= n operations
rover = rover.getNext(); //move the rover fwd //<= n operations
//create the newNode object to be added to the sub list
newNode = new DIntNode(rover.getData(), newListRover, null); //<= n operations
//then link up the newNode and advance the newListRover
newListRover.setNext(newNode); //<= n operations
newNode.setPrev(newListRover); //<= n operations
newListRover = newNode; //<= n operations
}
//after final iteration, newListRover == final node (discounting dummy);
//so, make its next point to dummy
newListRover.setNext(newList.getTail());
//and then link the dummy head up with the actual head
newList.getHead().setNext(newHead); //2 operations
//and then link the dummy tail with the actual tail
newList.getTail().setPrev(newListRover); //2 operations
//and return the copied list
return newList; //1 operation
} //total operations: 3 + 1 + n + n + 1 + 1 +1 + 6n + 2 + 2 + 1 = 8n + 12 operations. Big-O complexity is O(n), linear.
//let n = number of nodes in the list.
//The total operations is 4n + 3 operations. Big-O time is O(n), linear.
/**
* Count the occurrences of a given value, e, in the list.
* @param e The value to be searched for and counted.
* @return The number of times e appears in the list.
*/
public int countOccurrence(int e) {
int count = 0; //1 op
DIntNode rover = head.getNext(); //1 op
while(rover != tail) { //n ops
if (rover.getData() == e) //n ops
count++; //n ops (worst-case)
rover = rover.getNext(); //n ops
}
return count; //1 op
}
//create removeOne, so removeAll is easy: call removeOne until it returns false (nothing removed).
private boolean removeOne(int e) {
DIntNode roverPrev = head;
DIntNode rover = head.getNext(); //track three nodes at once, to make removal of the middle node (the searched node) simple
DIntNode roverNext = rover.getNext();
while(rover != tail) { //iterate over the list until dummy node
if(rover.getData() == e) { //if e found
roverPrev.setNext(roverNext); //removeOne(2) =>
roverNext.setPrev(roverPrev); //take care of linking up the prev and next nodes: (1)<---->(2)<---->(3) becomes => (1)<->(3)
rover.setNext(null); //null out the removed node (prev)<->(rover)<->(next)
rover.setPrev(null);
return true; //true if removed
}
roverPrev = rover; //advance the ref vars
rover = rover.getNext();
if(rover != null) //avoid null (de)reference
roverNext = rover.getNext();
}
return false; //if end of method reached, nothing found; return false.
}
//I believe this (removeAll) is O(n^2), where n = number of nodes in list. To removeOne(e) will take n trips; to removeAll will take n*n trips.
//the caveat is that n shrinks by 1 every iteration, so that makes it a weird summation of n + (n-1) + (n-2) + ... + (n-(n-1)) iterations.
//I don't know what to call that besides O(n^2).
/**
* Remove all occurrences of the value e in the list.
* @param e The value to be searched for and removed.
* @return true if e is found (and removed), false otherwise.
*/
public boolean removeAll(int e) {
boolean result = false;
//this line is doing the bulk of this method's work.
while(removeOne(e)) { //take advantage of fact that while loop is just an if statement that repeats.
result = true; //go until !removeOne(e)
}
return result; //if removeOne != true (never triggers the loop), this is false. Else true.
}
/**
* Print statistics for the list (each unique value, and its number of occurrences).
*/
public void printStatistics() {
HashMap<Integer, Integer> dict = new HashMap<Integer, Integer>(); //HashMap examples taken from StackOverflow
DIntNode rover = head.getNext();
while(rover != tail) { //iterate over list
if(!dict.containsKey(rover.getData())) //if key not in dictionary
dict.put(rover.getData(), 1); //then give init value of 1 (first time finding key)
else
dict.put(rover.getData(), (dict.get(rover.getData()) + 1) ); //else increase key's value by 1 (found one more time)
rover = rover.getNext(); //march onward
}
System.out.println("number\t\toccurrence");
for(Map.Entry<Integer, Integer> entry : dict.entrySet()) { //use special for loop to loop over Entry.s (ex taken from StackOverflow)
System.out.println(entry.getKey() + "\t\t\t" + entry.getValue()); //print key, couple of tabs, value
}
}
}