1 import java.util.NoSuchElementException;
2
3 /**
4 A linked list is a sequence of nodes with efficient
5 element insertion and removal. This class
6 contains a subset of the methods of the standard
7 java.util.LinkedList class.
8 */
9 public class LinkedList
10 {
11 private Node first;
12
13 /**
14 Constructs an empty linked list.
15 */
16 public LinkedList()
17 {
18 first = null;
19 }
20
21 /**
22 Returns the first element in the linked list.
23 @return the first element in the linked list
24 */
25 public Object getFirst()
26 {
27 if (first == null) { throw new NoSuchElementException(); }
28 return first.data;
29 }
30
31 /**
32 Removes the first element in the linked list.
33 @return the removed element
34 */
35 public Object removeFirst()
36 {
37 if (first == null) { throw new NoSuchElementException(); }
38 Object element = first.data;
39 first = first.next;
40 return element;
41 }
42
43 /**
44 Adds an element to the front of the linked list.
45 @param element the element to add
46 */
47 public void addFirst(Object element)
48 {
49 Node newNode = new Node();
50 newNode.data = element;
51 newNode.next = first;
52 first = newNode;
53 }
54
55 /**
56 Returns an iterator for iterating through this list.
57 @return an iterator for iterating through this list
58 */
59 public ListIterator listIterator()
60 {
61 return new LinkedListIterator();
62 }
63
64 class Node
65 {
66 public Object data;
67 public Node next;
68 }
69
70 class LinkedListIterator implements ListIterator
71 {
72 private Node position;
73 private Node previous;
74 private boolean isAfterNext;
75
76 /**
77 Constructs an iterator that points to the front
78 of the linked list.
79 */
80 public LinkedListIterator()
81 {
82 position = null;
83 previous = null;
84 isAfterNext = false;
85 }
86
87 /**
88 Moves the iterator past the next element.
89 @return the traversed element
90 */
91 public Object next()
92 {
93 if (!hasNext()) { throw new NoSuchElementException(); }
94 previous = position; // Remember for remove
95 isAfterNext = true;
96
97 if (position == null)
98 {
99 position = first;
100 }
101 else
102 {
103 position = position.next;
104 }
105
106 return position.data;
107 }
108
109 /**
110 Tests if there is an element after the iterator position.
111 @return true if there is an element after the iterator position
112 */
113 public boolean hasNext()
114 {
115 if (position == null)
116 {
117 return first != null;
118 }
119 else
120 {
121 return position.next != null;
122 }
123 }
124
125 /**
126 Adds an element before the iterator position
127 and moves the iterator past the inserted element.
128 @param element the element to add
129 */
130 public void add(Object element)
131 {
132 if (position == null)
133 {
134 addFirst(element);
135 position = first;
136 }
137 else
138 {
139 Node newNode = new Node();
140 newNode.data = element;
141 newNode.next = position.next;
142 position.next = newNode;
143 position = newNode;
144 }
145
146 isAfterNext = false;
147 }
148
149 /**
150 Removes the last traversed element. This method may
151 only be called after a call to the next() method.
152 */
153 public void remove()
154 {
155 if (!isAfterNext) { throw new IllegalStateException(); }
156
157 if (position == first)
158 {
159 removeFirst();
160 }
161 else
162 {
163 previous.next = position.next;
164 }
165 position = previous;
166 isAfterNext = false;
167 }
168
169 /**
170 Sets the last traversed element to a different value.
171 @param element the element to set
172 */
173 public void set(Object element)
174 {
175 if (!isAfterNext) { throw new IllegalStateException(); }
176 position.data = element;
177 }
178 }
179 }