source: trunk/src/org/expeditee/greenstone/DoublyLinkedList.java@ 1446

Last change on this file since 1446 was 919, checked in by jts21, 10 years ago

Added license headers to all files, added full GPL3 license file, moved license header generator script to dev/bin/scripts
File size: 7.7 KB
Line 
1/**
2 * DoublyLinkedList.java
3 * Copyright (C) 2010 New Zealand Digital Library, http://expeditee.org
4 *
5 * This program is free software: you can redistribute it and/or modify
6 * it under the terms of the GNU General Public License as published by
7 * the Free Software Foundation, either version 3 of the License, or
8 * (at your option) any later version.
9 *
10 * This program is distributed in the hope that it will be useful,
11 * but WITHOUT ANY WARRANTY; without even the implied warranty of
12 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
13 * GNU General Public License for more details.
14 *
15 * You should have received a copy of the GNU General Public License
16 * along with this program. If not, see <http://www.gnu.org/licenses/>.
17 */
18
19package org.expeditee.greenstone;
20
21import java.util.NoSuchElementException;
22
23public class DoublyLinkedList {
24
25 private DLLNode head, last;
26 private int size = 0;
27
28 public void addFirst(Object data) {
29 DLLNode newNode = new DLLNode();
30 newNode.data = data;
31 if(size==0) {
32 head = newNode;
33 last = head;
34 } else {
35 newNode.nextNode = head;
36 head.previousNode = newNode;
37 head = newNode;
38 }
39 size++;
40 }
41
42 public void addLast(Object data) {
43 DLLNode newNode = new DLLNode();
44 newNode.data = data;
45 if(size==0) {
46 head = newNode;
47 } else {
48 last.nextNode = newNode;
49 newNode.previousNode = last;
50 }
51 last = newNode;
52 size++;
53 }
54
55 public void removeFirst() {
56 if(size <= 1) {
57 head = null;
58 last = null;
59 } else {
60 DLLNode oldHead = head;
61 head = oldHead.nextNode;
62 oldHead.nextNode = null;
63 head.previousNode = null;
64 }
65 size--;
66 }
67
68 public void removeLast() {
69 if(size <= 1) {
70 head = null;
71 last = null;
72 } else {
73 last = last.previousNode;
74 last.nextNode.previousNode = null;
75 last.nextNode = null;
76 }
77 size--;
78 }
79
80 public int size() {
81 return size;
82 }
83
84 public void clear() {
85 DLLNode currentNode = last;
86 DLLNode tempNode;
87 while(currentNode != null) {
88 tempNode = currentNode.previousNode;
89 currentNode.nextNode = null;
90 currentNode.previousNode = null;
91 currentNode.data = null;
92 currentNode = tempNode;
93 }
94 last = null;
95 head = null;
96 size = 0;
97 }
98
99 protected class DLLNode {
100 protected DLLNode nextNode, previousNode;
101 protected Object data;
102 }
103
104 public DLLIterator iterator() {
105 return new DLLIterator();
106 }
107
108 public class DLLIterator {
109
110 private DLLNode currentPreviousNode = null;
111 private DLLNode currentNextNode = head;
112
113 public boolean hasNext() {
114 if(currentNextNode == null) {
115 return false;
116 } else {
117 return(currentNextNode != null);
118 }
119 }
120
121 public boolean hasPrevious() {
122 if(currentPreviousNode == null) {
123 return false;
124 } else {
125 return (currentPreviousNode != null);
126 }
127 }
128
129 public Object next() {
130 if(currentNextNode == null) throw new NoSuchElementException("Attempt to retrieve next value from " +
131 "DoublyLinkedList after all values have already been retrieved. Verify hasNext method returns true " +
132 "before calling next method.");
133 Object data = currentNextNode.data;
134 DLLNode tempNode = currentNextNode;
135 currentNextNode = currentNextNode.nextNode;
136 currentPreviousNode = tempNode;
137 return data;
138 }
139
140 public Object previous() {
141 if(currentPreviousNode == null) throw new NoSuchElementException("Attempt to retrieve previous value from " +
142 "head node of DoublyLinkedList. Verify hasPrevious method returns true " +
143 "before calling previous method.");
144 Object data = currentPreviousNode.data;
145 DLLNode tempNode = currentPreviousNode;
146 currentPreviousNode = currentPreviousNode.previousNode;
147 currentNextNode = tempNode;
148 return data;
149 }
150
151 public void resetToBeginning() {
152 currentNextNode = head;
153 currentPreviousNode = null;
154 }
155
156 public void resetToEnd() {
157 currentNextNode = null;
158 currentPreviousNode = last;
159 }
160 }
161
162 // ******************************************************************************************************************************
163 // ***************************************** from here on down is test code *******************************************
164 // ******************************************************************************************************************************
165
166 public static class Test {
167 public static void main(String[] args) {
168 DoublyLinkedList testListOne = new DoublyLinkedList();
169 String testObjectOne = "test object one";
170 testListOne.addFirst(testObjectOne);
171 System.out.println("Size after adding one object by calling addFirst: " + testListOne.size);
172 testListOne.removeFirst();
173 System.out.println("Then called removeFirst and size is: " + testListOne.size);
174
175 testListOne.addLast(testObjectOne);
176 System.out.println("Size after adding one object by calling addLast: " + testListOne.size);
177 testListOne.removeLast();
178 System.out.println("Then called removeLast and size is: " + testListOne.size);
179 testListOne.clear();
180 testListOne.clear();
181
182 testListOne.addFirst(testObjectOne);
183 DLLIterator iterator = testListOne.iterator();
184 System.out.println("hasNext method of iterator after adding one object by calling addFirst: " + iterator.hasNext());
185 System.out.println("hasPrevious method of iterator after adding one object by calling addFirst: " + iterator.hasPrevious());
186 String resultString = (String)iterator.next();
187 System.out.println("result string pulled out by calling next: " + resultString);
188 System.out.println("hasNext method of iterator after calling next: " + iterator.hasNext());
189 System.out.println("hasPrevious method of iterator after calling next: " + iterator.hasPrevious());
190 resultString = (String)iterator.previous();
191 System.out.println("result string pulled out by calling previous: " + resultString);
192 testListOne.clear();
193
194 System.out.println("");
195
196 String testObjectTwo = "test object two";
197 String testObjectThree = "test object three";
198
199 testListOne.addFirst(testObjectTwo);
200 testListOne.addFirst(testObjectOne);
201 iterator.resetToBeginning();
202 while(iterator.hasNext()) System.out.println((String)iterator.next());
203 testListOne.clear();
204
205 System.out.println("");
206
207 testListOne.addLast(testObjectOne);
208 testListOne.addLast(testObjectTwo);
209 iterator.resetToBeginning();
210 while(iterator.hasNext()) System.out.println((String)iterator.next());
211 testListOne.clear();
212
213 System.out.println("");
214
215 testListOne.addFirst(testObjectThree);
216 testListOne.addFirst(testObjectTwo);
217 testListOne.addFirst(testObjectOne);
218 iterator.resetToBeginning();
219 while(iterator.hasNext()) System.out.println((String)iterator.next());
220 testListOne.clear();
221
222 System.out.println("");
223
224 testListOne.addLast(testObjectOne);
225 testListOne.addLast(testObjectTwo);
226 testListOne.addLast(testObjectThree);
227 iterator.resetToBeginning();
228 while(iterator.hasNext()) System.out.println((String)iterator.next());
229 testListOne.clear();
230
231 System.out.println("");
232
233 testListOne.addFirst(testObjectTwo);
234 testListOne.addFirst(testObjectOne);
235 iterator.resetToEnd();
236 while(iterator.hasPrevious()) System.out.println((String)iterator.previous());
237 testListOne.clear();
238
239 System.out.println("");
240
241 testListOne.addFirst(testObjectThree);
242 testListOne.addFirst(testObjectTwo);
243 testListOne.addFirst(testObjectOne);
244 System.out.println("size after adding three objects: " + testListOne.size());
245 iterator.resetToEnd();
246 while(iterator.hasPrevious()) System.out.println((String)iterator.previous());
247 testListOne.clear();
248
249 System.out.println("");
250 }
251 }
252}
Note: See TracBrowser for help on using the repository browser.