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

Last change on this file since 312 was 312, checked in by ra33, 16 years ago

Added search agents for HCI bib tec
File size: 6.9 KB
Line 
1package org.expeditee.greenstone;
2
3import java.util.NoSuchElementException;
4
5public class DoublyLinkedList {
6
7 private DLLNode head, last;
8 private int size = 0;
9
10 public void addFirst(Object data) {
11 DLLNode newNode = new DLLNode();
12 newNode.data = data;
13 if(size==0) {
14 head = newNode;
15 last = head;
16 } else {
17 newNode.nextNode = head;
18 head.previousNode = newNode;
19 head = newNode;
20 }
21 size++;
22 }
23
24 public void addLast(Object data) {
25 DLLNode newNode = new DLLNode();
26 newNode.data = data;
27 if(size==0) {
28 head = newNode;
29 } else {
30 last.nextNode = newNode;
31 newNode.previousNode = last;
32 }
33 last = newNode;
34 size++;
35 }
36
37 public void removeFirst() {
38 if(size <= 1) {
39 head = null;
40 last = null;
41 } else {
42 DLLNode oldHead = head;
43 head = oldHead.nextNode;
44 oldHead.nextNode = null;
45 head.previousNode = null;
46 }
47 size--;
48 }
49
50 public void removeLast() {
51 if(size <= 1) {
52 head = null;
53 last = null;
54 } else {
55 last = last.previousNode;
56 last.nextNode.previousNode = null;
57 last.nextNode = null;
58 }
59 size--;
60 }
61
62 public int size() {
63 return size;
64 }
65
66 public void clear() {
67 DLLNode currentNode = last;
68 DLLNode tempNode;
69 while(currentNode != null) {
70 tempNode = currentNode.previousNode;
71 currentNode.nextNode = null;
72 currentNode.previousNode = null;
73 currentNode.data = null;
74 currentNode = tempNode;
75 }
76 last = null;
77 head = null;
78 size = 0;
79 }
80
81 protected class DLLNode {
82 protected DLLNode nextNode, previousNode;
83 protected Object data;
84 }
85
86 public DLLIterator iterator() {
87 return new DLLIterator();
88 }
89
90 public class DLLIterator {
91
92 private DLLNode currentPreviousNode = null;
93 private DLLNode currentNextNode = head;
94
95 public boolean hasNext() {
96 if(currentNextNode == null) {
97 return false;
98 } else {
99 return(currentNextNode != null);
100 }
101 }
102
103 public boolean hasPrevious() {
104 if(currentPreviousNode == null) {
105 return false;
106 } else {
107 return (currentPreviousNode != null);
108 }
109 }
110
111 public Object next() {
112 if(currentNextNode == null) throw new NoSuchElementException("Attempt to retrieve next value from " +
113 "DoublyLinkedList after all values have already been retrieved. Verify hasNext method returns true " +
114 "before calling next method.");
115 Object data = currentNextNode.data;
116 DLLNode tempNode = currentNextNode;
117 currentNextNode = currentNextNode.nextNode;
118 currentPreviousNode = tempNode;
119 return data;
120 }
121
122 public Object previous() {
123 if(currentPreviousNode == null) throw new NoSuchElementException("Attempt to retrieve previous value from " +
124 "head node of DoublyLinkedList. Verify hasPrevious method returns true " +
125 "before calling previous method.");
126 Object data = currentPreviousNode.data;
127 DLLNode tempNode = currentPreviousNode;
128 currentPreviousNode = currentPreviousNode.previousNode;
129 currentNextNode = tempNode;
130 return data;
131 }
132
133 public void resetToBeginning() {
134 currentNextNode = head;
135 currentPreviousNode = null;
136 }
137
138 public void resetToEnd() {
139 currentNextNode = null;
140 currentPreviousNode = last;
141 }
142 }
143
144 // ******************************************************************************************************************************
145 // ***************************************** from here on down is test code *******************************************
146 // ******************************************************************************************************************************
147
148 public static class Test {
149 public static void main(String[] args) {
150 DoublyLinkedList testListOne = new DoublyLinkedList();
151 String testObjectOne = "test object one";
152 testListOne.addFirst(testObjectOne);
153 System.out.println("Size after adding one object by calling addFirst: " + testListOne.size);
154 testListOne.removeFirst();
155 System.out.println("Then called removeFirst and size is: " + testListOne.size);
156
157 testListOne.addLast(testObjectOne);
158 System.out.println("Size after adding one object by calling addLast: " + testListOne.size);
159 testListOne.removeLast();
160 System.out.println("Then called removeLast and size is: " + testListOne.size);
161 testListOne.clear();
162 testListOne.clear();
163
164 testListOne.addFirst(testObjectOne);
165 DLLIterator iterator = testListOne.iterator();
166 System.out.println("hasNext method of iterator after adding one object by calling addFirst: " + iterator.hasNext());
167 System.out.println("hasPrevious method of iterator after adding one object by calling addFirst: " + iterator.hasPrevious());
168 String resultString = (String)iterator.next();
169 System.out.println("result string pulled out by calling next: " + resultString);
170 System.out.println("hasNext method of iterator after calling next: " + iterator.hasNext());
171 System.out.println("hasPrevious method of iterator after calling next: " + iterator.hasPrevious());
172 resultString = (String)iterator.previous();
173 System.out.println("result string pulled out by calling previous: " + resultString);
174 testListOne.clear();
175
176 System.out.println("");
177
178 String testObjectTwo = "test object two";
179 String testObjectThree = "test object three";
180
181 testListOne.addFirst(testObjectTwo);
182 testListOne.addFirst(testObjectOne);
183 iterator.resetToBeginning();
184 while(iterator.hasNext()) System.out.println((String)iterator.next());
185 testListOne.clear();
186
187 System.out.println("");
188
189 testListOne.addLast(testObjectOne);
190 testListOne.addLast(testObjectTwo);
191 iterator.resetToBeginning();
192 while(iterator.hasNext()) System.out.println((String)iterator.next());
193 testListOne.clear();
194
195 System.out.println("");
196
197 testListOne.addFirst(testObjectThree);
198 testListOne.addFirst(testObjectTwo);
199 testListOne.addFirst(testObjectOne);
200 iterator.resetToBeginning();
201 while(iterator.hasNext()) System.out.println((String)iterator.next());
202 testListOne.clear();
203
204 System.out.println("");
205
206 testListOne.addLast(testObjectOne);
207 testListOne.addLast(testObjectTwo);
208 testListOne.addLast(testObjectThree);
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(testObjectTwo);
216 testListOne.addFirst(testObjectOne);
217 iterator.resetToEnd();
218 while(iterator.hasPrevious()) System.out.println((String)iterator.previous());
219 testListOne.clear();
220
221 System.out.println("");
222
223 testListOne.addFirst(testObjectThree);
224 testListOne.addFirst(testObjectTwo);
225 testListOne.addFirst(testObjectOne);
226 System.out.println("size after adding three objects: " + testListOne.size());
227 iterator.resetToEnd();
228 while(iterator.hasPrevious()) System.out.println((String)iterator.previous());
229 testListOne.clear();
230
231 System.out.println("");
232 }
233 }
234}
Note: See TracBrowser for help on using the repository browser.