LinkedList.java.html

  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  }