public class StringLinkedListWithIterator2 implements Iterator
1:
2: import java.util.*;
3:
4: public class StringLinkedListWithIterator2 implements Iterator
5: {
6: private ListNode head;
7: private ListNode current;
8: private ListNode previous; //follows current
9: private ListNode twoBack; //follows previous
10: private boolean removeSinceNext;//true if removed has been
11: //called since the last invocation of next.
12: //Also true if next has not been called at all.
13:
14: public StringLinkedListWithIterator2( )
15: {
16: head = null;
17: current = null;
18: previous = null;
19: twoBack = null;
20: removeSinceNext = true;
21: }
22:
23: /**
24: Returns the next element (String) in the list.
25: Throws a NoSuchElementException if there is
26: no next element to return. You should invoke
27: resetIteration before the first invocation of next( ).
28: */
29: public Object next( )
30: {
31: if (current != null)
32: {
33: twoBack = previous;
34: previous = current;
35: current = current.link;
36: removeSinceNext = false;
37: return (previous.data);
38: }
39: else
40: {
41: throw new NoSuchElementException( );
42: }
43: }
44:
45: /**
46: Removes the last element that was returned by next.
47: Throws an IllegalStateException if the next method has
48: not yet been called or if the remove method has already
49: been called after the last call to the next method.
50: */
51: public void remove( )
52: {
53: if ((previous != null) && (twoBack != null)
54: && (!removeSinceNext))
55: {//remove node at previous
56: twoBack.link = previous.link;
57: previous = twoBack;
58: removeSinceNext = true;
59: //twoBack not updated until next invocation of next( )
60: }
61: else if( (previous != null) && (twoBack == null)
62: && (!removeSinceNext))
63: {//previous at head node and current
64: //at head node after deletion
65: head = current;
66: previous = null;
67: twoBack = null;
68: removeSinceNext = true;
69: }
70: else
71: {
72: throw new IllegalStateException( );
73: }
74: }
75:
76: /**
77: Returns true if there is at least one more element
78: for next to return. Otherwise, returns false.
79: */
80: public boolean hasNext( )
81: {
82: return (current != null);
83: }
84:
85: public void resetIteration( )
86: {
87: current = head;
88: previous = null;
89: twoBack = null;
90: removeSinceNext = true;
91: }
92:
93:
94: public String getDataAtCurrent( )
95: throws LinkedListException
96: {
97: if (current != null)
98: return (current.data);
99: else
100: throw new LinkedListException(
101: "Getting data when current is not at any node.");
102: }
103:
104: public void resetDataAtCurrent(String newData)
105: throws LinkedListException
106: {
107: if (current != null)
108: current.data = newData;
109: else
110: throw new LinkedListException(
111: "Setting data when current is not at any node.");
112: }
113:
114: /**
115: Inserts node with newData after the current node. The current
116: node is the same after invocation as it is before invocation.
117: Should not be used with an empty list. Should not be
118: used when the current node has iterated past the entire list.
119: */
120: public void insertNodeAfterCurrent(String newData)
121: throws LinkedListException
122: {
123: ListNode newNode = new ListNode( );
124: newNode.data = newData;
125: if (current != null)
126: {
127: newNode.link = current.link;
128: current.link = newNode;
129: }
130: else if (head != null)
131: {
132: throw new LinkedListException(
133: "Inserting when iterator is past all"
134: + " nodes or uninitialized iterator.");
135: }
136: else
137: {
138: throw new LinkedListException(
139: "Using insertNodeAfterCurrent with empty list.");
140: }
141: }
142:
143: /**
144: Deletes current node. After the invocation,
145: the current node is the node after the
146: deleted node, or null if there is no next node.
147: */
148: public void deleteCurrentNode( ) throws LinkedListException
149: {
150: if ((current != null) && (previous != null))
151: {
152: previous.link = current.link;
153: current = current.link;
154: }
155: else if( (current != null) && (previous == null))
156: {//At head node
157: head = current.link;
158: current = head;
159: }
160: else //current == null
161: {
162: throw new LinkedListException(
163: "Deleting with uninitialized current"
164: + " or an empty list.");
165: }
166: }
167:
168:
169: /**
170: Returns the number of nodes in the list.
171: */
172: public int length( )
173: {
174: int count = 0;
175: ListNode position = head;
176: while (position != null)
177: {
178: count++;
179: position = position.link;
180: }
181: return count;
182: }
183:
184: public void addANodeToStart(String addData)
185: {
186: head = new ListNode(addData, head);
187: if (current == head.link && current != null)
188: //if current is at old start node
189: previous = head;
190: }
191:
192: public boolean onList(String target)
193: {
194: return (Find(target) != null);
195: }
196:
197: /**
198: Returns a reference to the first node containing the target
199: data. If target is not in the list, null is returned.
200: */
201: private ListNode Find(String target)
202: {
203: ListNode position;
204: position = head;
205: String dataAtPosition;
206: while (position != null)
207: {
208: dataAtPosition = position.data;
209: if (dataAtPosition.equals(target))
210: return position;
211: position = position.link;
212: }
213: //target was not found
214: return null;
215: }
216:
217: public void showList( )
218: {
219: ListNode position;
220: position = head;
221: while (position != null)
222: {
223: System.out.println(position.data);
224: position = position.link;
225: }
226: }
227:
228: public String[] arrayCopy( )
229: {
230: String[] a = new String[length( )];
231:
232: ListNode position;
233: position = head;
234: int i = 0;
235: while (position != null)
236: {
237: a[i] = position.data;
238: i++;
239: position = position.link;
240: }
241:
242: return a;
243: }
244:
245:
246:
247: private class ListNode
248: {
249: private String data;
250: private ListNode link;
251: public ListNode( )
252: {
253: link = null;
254: data = null;
255: }
256: public ListNode(String newData, ListNode linkValue)
257: {
258: data = newData;
259: link = linkValue;
260: }
261: }
262: }