-
Notifications
You must be signed in to change notification settings - Fork 3
/
DoublyLinkedList.java
128 lines (88 loc) · 2.49 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
package DataStructure;
import java.util.Iterator;
import java.util.NoSuchElementException;
public class DoublyLinkedList<Item> implements Iterable<Item> {
private Node first, last;
private int size;
private class Node {
private Node next;
private Node previous;
private Item item;
}
public DoublyLinkedList() {
size = 0;
first = null;
last = null;
}
public boolean isEmpty() {
return (size == 0);
}
public int size() {
return size;
}
public void enqueue(Item item) {
Node oldFirst = first;
first = new Node();
first.item = item;
first.next = oldFirst;
first.previous = null;
if (isEmpty()) last = first;
size++;
}
public void push(Item item) {
Node oldLast = last;
last = new Node();
last.item = item;
last.next = null;
last.previous = oldLast;
oldLast.next = last;
if (isEmpty()) first = last;
size++;
}
public Item dequeue() {
if (isEmpty()) throw new NoSuchElementException("Empty linked list.");
Item item = first.item;
first = first.next;
size--;
if (isEmpty()) last = first;
return item;
}
public Item pop() {
if (isEmpty()) throw new NoSuchElementException("Empty linked list.");
Item item = last.item;
last = last.previous;
size--;
if (isEmpty()) first = last;
return item;
}
public Iterator<Item> iterator() {
return new LinkedListIterator(false);
}
public Iterator<Item> reverseIterator() {
return new LinkedListIterator(true);
}
private class LinkedListIterator implements Iterator<Item> {
private Node current;
private boolean reverse;
public LinkedListIterator(boolean reverse) {
current = last;
this.reverse = reverse;
}
public void remove() {
throw new UnsupportedOperationException();
}
public boolean hasNext() {
return (current != null);
}
public Item next() {
if (!hasNext()) throw new NoSuchElementException("Has traversed all elements");
Item item = current.item;
if (reverse) {
current = current.previous;
} else {
current = current.next;
}
return item;
}
}
}