LinkedList.java.html

  1  import java.util.NoSuchElementException;
  2  
  3  /**
  4     An implementation of a doubly linked list.
  5  */
  6  public class LinkedList
  7  {  
  8     private Node first;
  9     private Node last;
 10     
 11     /** 
 12        Constructs an empty linked list.
 13     */
 14     public LinkedList()
 15     {  
 16        first = null;
 17        last = null;
 18     }
 19     
 20     /**
 21        Returns the first element in the linked list.
 22        @return the first element in the linked list
 23     */
 24     public Object getFirst()
 25     {  
 26        if (first == null) { throw new NoSuchElementException(); }
 27        return first.data;
 28     }
 29  
 30     /**
 31        Removes the first element in the linked list.
 32        @return the removed element
 33     */
 34     public Object removeFirst()
 35     {  
 36        if (first == null) { throw new NoSuchElementException(); }
 37        Object element = first.data;
 38        first = first.next;
 39        if (first == null) { last = null; } // List is now empty
 40        else { first.previous = null; }
 41        return element;
 42     }
 43  
 44     /**
 45        Adds an element to the front of the linked list.
 46        @param element the element to add
 47     */
 48     public void addFirst(Object element)
 49     {  
 50        Node newNode = new Node();
 51        newNode.data = element;
 52        newNode.next = first;
 53        newNode.previous = null;
 54        if (first == null) { last = newNode; }
 55        else { first.previous = newNode; }
 56        first = newNode;
 57     }
 58     
 59     /**
 60        Returns the last element in the linked list.
 61        @return the last element in the linked list
 62     */
 63     public Object getLast()
 64     {  
 65        if (last == null) { throw new NoSuchElementException(); }
 66        return last.data;
 67     }
 68  
 69     /**
 70        Removes the last element in the linked list.
 71        @return the removed element
 72     */
 73     public Object removeLast()
 74     {  
 75        if (last == null) { throw new NoSuchElementException(); }
 76        Object element = last.data;
 77        last = last.previous;
 78        if (last == null) { first = null; } // List is now empty
 79        else { last.next = null; }
 80        return element;
 81     }
 82  
 83     /**
 84        Adds an element to the back of the linked list.
 85        @param element the element to add
 86     */
 87     public void addLast(Object element)
 88     {  
 89        Node newNode = new Node();
 90        newNode.data = element;
 91        newNode.next = null;
 92        newNode.previous = last;
 93        if (last == null) { first = newNode; }
 94        else { last.next = newNode; }
 95        last = newNode;
 96     }
 97     
 98     /**
 99        Returns an iterator for iterating through this list.
100        @return an iterator for iterating through this list
101     */
102     public ListIterator listIterator()
103     {  
104        return new LinkedListIterator();
105     }
106     
107     class Node
108     {  
109        public Object data;
110        public Node next;
111        public Node previous;
112     }
113  
114     class LinkedListIterator implements ListIterator
115     {  
116        private Node position;
117        private boolean isAfterNext;
118        private boolean isAfterPrevious;
119  
120        /**
121           Constructs an iterator that points to the front
122           of the linked list.
123        */
124        public LinkedListIterator()
125        {  
126           position = null;
127           isAfterNext = false;
128           isAfterPrevious = false;
129        }
130        
131        /**
132           Moves the iterator past the next element.
133           @return the traversed element
134        */
135        public Object next()
136        {  
137           if (!hasNext()) { throw new NoSuchElementException(); }
138           isAfterNext = true;
139           isAfterPrevious = false;
140  
141           if (position == null)
142           {
143              position = first;
144           }
145           else
146           {
147              position = position.next;
148           }
149  
150           return position.data;
151        }
152        
153        /**
154           Tests if there is an element after the iterator position.
155           @return true if there is an element after the iterator position
156        */
157        public boolean hasNext()
158        {  
159           if (position == null)
160           {
161              return first != null;
162           }
163           else
164           {
165              return position.next != null;
166           }
167        }
168  
169        /**
170           Moves the iterator before the previous element.
171           @return the traversed element
172        */
173        public Object previous()
174        {  
175           if (!hasPrevious()) { throw new NoSuchElementException(); }
176           isAfterNext = false;
177           isAfterPrevious = true;
178  
179           Object result = position.data;
180           position = position.previous;
181           return result;
182        }
183        
184        /**
185           Tests if there is an element before the iterator position.
186           @return true if there is an element before the iterator position
187        */
188        public boolean hasPrevious()
189        {  
190           return position != null;
191        }
192        
193        /**
194           Adds an element before the iterator position
195           and moves the iterator past the inserted element.
196           @param element the element to add
197        */
198        public void add(Object element)
199        {  
200           if (position == null)
201           {
202              addFirst(element);
203              position = first;
204           }
205           else if (position == last)
206           {
207              addLast(element);
208              position = last;
209           }
210           else
211           {  
212              Node newNode = new Node();
213              newNode.data = element;
214              newNode.next = position.next;
215              newNode.next.previous = newNode;
216              position.next = newNode;
217              newNode.previous = position;
218              position = newNode;
219           }
220  
221           isAfterNext = false;
222           isAfterPrevious = false;
223        }
224        
225        /**
226           Removes the last traversed element. This method may
227           only be called after a call to the next() method.
228        */
229        public void remove()
230        {  
231           Node positionToRemove = lastPosition();
232  
233           if (positionToRemove == first)
234           {
235              removeFirst();
236           }
237           else if (positionToRemove == last)
238           {
239              removeLast();
240           }
241           else
242           {
243              positionToRemove.previous.next = positionToRemove.next;
244              positionToRemove.next.previous = positionToRemove.previous;
245           }
246  
247           if (isAfterNext) 
248           { 
249              position = position.previous;
250           }
251  
252           isAfterNext = false;
253           isAfterPrevious = false;
254        }
255  
256        /**
257           Sets the last traversed element to a different value. 
258           @param element the element to set
259        */
260        public void set(Object element)
261        {
262           Node positionToSet = lastPosition();
263           positionToSet.data = element; 
264        }
265  
266        /**
267           Returns the last node traversed by this iterator, or
268           throws an IllegalStateException if there wasn't an immediately
269           preceding call to next or previous.
270           @return the last traversed node
271        */
272        private Node lastPosition()
273        {
274           if (isAfterNext) 
275           { 
276              return position; 
277           }
278           else if (isAfterPrevious) 
279           {
280              if (position == null)
281              {
282                 return first;
283              }
284              else
285              {
286                 return position.next;
287              }
288           }
289           else { throw new IllegalStateException(); }
290        }      
291     }
292  }