SHOW:
|
|
- or go back to the newest paste.
1 | // | |
2 | // Created by Julio Tentor <jtentor@fi.unju.edu.ar> | |
3 | // | |
4 | ||
5 | import java.util.Iterator; | |
6 | ||
7 | public class DoubleLinkedList<ELEMENT> implements ILinkedList<ELEMENT> { | |
8 | ||
9 | //region Node Class | |
10 | ||
11 | protected class Node<ELEMENT> { | |
12 | protected ELEMENT item; | |
13 | protected Node<ELEMENT> next; | |
14 | protected Node<ELEMENT> prev; | |
15 | ||
16 | protected Node() { | |
17 | this(null, null, null); | |
18 | } | |
19 | protected Node(ELEMENT item) { | |
20 | this(item, null, null); | |
21 | } | |
22 | protected Node(ELEMENT item, Node<ELEMENT> next) { | |
23 | this(item, next, null); | |
24 | } | |
25 | protected Node(ELEMENT item, Node<ELEMENT> next, Node<ELEMENT> prev) { | |
26 | this.item = item; | |
27 | this.next = next; | |
28 | this.prev = prev; | |
29 | } | |
30 | ||
31 | @Override | |
32 | public String toString() { | |
33 | return this.item.toString(); | |
34 | } | |
35 | } | |
36 | //endregion | |
37 | ||
38 | //region Attributes | |
39 | ||
40 | private Node<ELEMENT> head; | |
41 | private int count; | |
42 | private Node<ELEMENT> tail; | |
43 | //endregion | |
44 | ||
45 | //region Constructors | |
46 | ||
47 | public DoubleLinkedList() { | |
48 | this.head = null; | |
49 | this.count = 0; | |
50 | this.tail = null; | |
51 | } | |
52 | //endregion | |
53 | ||
54 | //region Linked List Methods | |
55 | ||
56 | // Returns the number of elements in this list. | |
57 | public int size() { | |
58 | return this.count; | |
59 | } | |
60 | ||
61 | public void addFirstRookieVersion(ELEMENT item) { | |
62 | if (this.size() <= 0) { | |
63 | this.head = this.tail = new Node<ELEMENT>(item, null, null); | |
64 | ++this.count; | |
65 | } | |
66 | else { | |
67 | Node<ELEMENT> temp = new Node<ELEMENT>(item, null, null); | |
68 | temp.next = this.head; | |
69 | this.head.prev = temp; | |
70 | this.head = temp; | |
71 | ++this.count; | |
72 | } | |
73 | } | |
74 | // Inserts the specified element at the beginning of this list. | |
75 | public void addFirst(ELEMENT item) { | |
76 | Node<ELEMENT> temp = new Node<ELEMENT>(item, this.head, null); | |
77 | if (this.size() <= 0) { | |
78 | this.tail = temp; | |
79 | } | |
80 | else { | |
81 | this.head.prev = temp; | |
82 | } | |
83 | this.head = temp; | |
84 | ++this.count; | |
85 | } | |
86 | ||
87 | public void addLastRookieVersion(ELEMENT item) { | |
88 | if (this.size() <= 0) { | |
89 | this.head = this.tail = new Node<ELEMENT>(item, null, null); | |
90 | ++this.count; | |
91 | } | |
92 | else { | |
93 | Node<ELEMENT> temp = new Node<ELEMENT>(item, null, null); | |
94 | temp.prev = this.tail; | |
95 | this.tail.next = temp; | |
96 | this.tail = temp; | |
97 | ++this.count; | |
98 | } | |
99 | } | |
100 | // Appends the specified element to the end of this list. | |
101 | public void addLast(ELEMENT item) { | |
102 | Node<ELEMENT> temp = new Node<ELEMENT>(item, null, this.tail); | |
103 | if (this.size() <= 0) { | |
104 | this.head = temp; | |
105 | } | |
106 | else { | |
107 | this.tail.next = temp; | |
108 | } | |
109 | this.tail = temp; | |
110 | ++this.count; | |
111 | } | |
112 | ||
113 | // Removes and returns the first element from this list. | |
114 | public ELEMENT removeFirst() { | |
115 | if (this.size() <= 0) { | |
116 | throw new RuntimeException("La lista está vacía..."); | |
117 | } | |
118 | ELEMENT item = this.head.item; | |
119 | this.head = this.head.next; | |
120 | if (this.head == null) { | |
121 | this.tail = null; | |
122 | } | |
123 | else { | |
124 | this.head.prev = null; | |
125 | } | |
126 | --this.count; | |
127 | return item; | |
128 | } | |
129 | ||
130 | // Removes and returns the last element from this list. | |
131 | public ELEMENT removeLast() { | |
132 | if (this.size() <= 0) { | |
133 | throw new RuntimeException("La lista está vacía..."); | |
134 | } | |
135 | ELEMENT item = this.tail.item; | |
136 | if (this.head.next == null) { | |
137 | this.head = this.tail = null; | |
138 | } else { | |
139 | this.tail = this.tail.prev; | |
140 | this.tail.next = null; | |
141 | } | |
142 | --this.count; | |
143 | return item; | |
144 | } | |
145 | //endregion | |
146 | ||
147 | //region Object Methods | |
148 | ||
149 | @Override | |
150 | public String toString() { | |
151 | ||
152 | if (this.size() <= 0) { | |
153 | return ""; | |
154 | } | |
155 | ||
156 | // from https://docs.oracle.com/en/java/javase/15/docs/api/java.base/java/lang/StringBuilder.html | |
157 | StringBuilder sb = new StringBuilder(); | |
158 | ||
159 | sb.append("[" + this.head.item.toString()); | |
160 | for (Node<ELEMENT> skip = this.head.next; skip != null; skip = skip.next) { | |
161 | sb.append(", " + skip.item.toString()); | |
162 | } | |
163 | sb.append("]"); | |
164 | ||
165 | return sb.toString(); | |
166 | } | |
167 | //endregion | |
168 | ||
169 | //region Iterable Methods | |
170 | @Override | |
171 | public Iterator<ELEMENT> iterator() { | |
172 | return new DoubleLinkedListIterator(this.head); | |
173 | } | |
174 | ||
175 | public class DoubleLinkedListIterator implements Iterator<ELEMENT> { | |
176 | private Node<ELEMENT> current; | |
177 | ||
178 | public DoubleLinkedListIterator(Node<ELEMENT> current) { | |
179 | this.current = current; | |
180 | } | |
181 | ||
182 | @Override | |
183 | public boolean hasNext() { | |
184 | return this.current != null; | |
185 | } | |
186 | ||
187 | @Override | |
188 | public ELEMENT next() { | |
189 | if (!this.hasNext()) { | |
190 | throw new RuntimeException("La lista está vacía..."); | |
191 | } | |
192 | ELEMENT item = this.current.item; | |
193 | this.current = this.current.next; | |
194 | return item; | |
195 | } | |
196 | } | |
197 | ||
198 | public Iterator<ELEMENT> iteratorBack() { | |
199 | return new DoubleLinkedListIteratorBack(this.tail); | |
200 | } | |
201 | ||
202 | public class DoubleLinkedListIteratorBack implements Iterator<ELEMENT> { | |
203 | private Node<ELEMENT> current; | |
204 | ||
205 | public DoubleLinkedListIteratorBack(Node<ELEMENT> current) { | |
206 | this.current = current; | |
207 | } | |
208 | ||
209 | @Override | |
210 | public boolean hasNext() { | |
211 | return this.current != null; | |
212 | } | |
213 | ||
214 | @Override | |
215 | public ELEMENT next() { | |
216 | if (!this.hasNext()) { | |
217 | throw new RuntimeException("La lista está vacía..."); | |
218 | } | |
219 | ELEMENT item = this.current.item; | |
220 | this.current = this.current.prev; | |
221 | return item; | |
222 | } | |
223 | ||
224 | } | |
225 | ||
226 | //endregion | |
227 | ||
228 | } | |
229 |