001: import java.util.NoSuchElementException;
002: 
003: /**
004:    A linked list is a sequence of nodes with efficient
005:    element insertion and removal. This class 
006:    contains a subset of the methods of the standard
007:    java.util.LinkedList class.
008: */
009: public class LinkedList
010: {  
011:    /** 
012:       Constructs an empty linked list.
013:    */
014:    public LinkedList()
015:    {  
016:       first = null;
017:    }
018:    
019:    /**
020:       Returns the first element in the linked list.
021:       @return the first element in the linked list
022:    */
023:    public Object getFirst()
024:    {  
025:       if (first == null) 
026:          throw new NoSuchElementException();
027:       return first.data;
028:    }
029: 
030:    /**
031:       Removes the first element in the linked list.
032:       @return the removed element
033:    */
034:    public Object removeFirst()
035:    {  
036:       if (first == null) 
037:          throw new NoSuchElementException();
038:       Object element = first.data;
039:       first = first.next;
040:       return element;
041:    }
042: 
043:    /**
044:       Adds an element to the front of the linked list.
045:       @param element the element to add
046:    */
047:    public void addFirst(Object element)
048:    {  
049:       Node newNode = new Node();
050:       newNode.data = element;
051:       newNode.next = first;
052:       first = newNode;
053:    }
054:    
055:    /**
056:       Returns an iterator for iterating through this list.
057:       @return an iterator for iterating through this list
058:    */
059:    public ListIterator listIterator()
060:    {  
061:       return new LinkedListIterator();
062:    }
063:    
064:    private Node first;
065:    
066:    private class Node
067:    {  
068:       public Object data;
069:       public Node next;
070:    }
071: 
072:    private class LinkedListIterator implements ListIterator
073:    {  
074:       /**
075:          Constructs an iterator that points to the front
076:          of the linked list.
077:       */
078:       public LinkedListIterator()
079:       {  
080:          position = null;
081:          previous = null;
082:       }
083:       
084:       /**
085:          Moves the iterator past the next element.
086:          @return the traversed element
087:       */
088:       public Object next()
089:       {  
090:          if (!hasNext())
091:             throw new NoSuchElementException();
092:          previous = position; // Remember for remove
093: 
094:          if (position == null)
095:             position = first;
096:          else
097:             position = position.next;
098: 
099:          return position.data;
100:       }
101:       
102:       /**
103:          Tests if there is an element after the iterator 
104:          position.
105:          @return true if there is an element after the iterator 
106:          position
107:       */
108:       public boolean hasNext()
109:       {  
110:          if (position == null)
111:             return first != null;
112:          else
113:             return position.next != null;
114:       }
115:       
116:       /**
117:          Adds an element before the iterator position
118:          and moves the iterator past the inserted element.
119:          @param element the element to add
120:       */
121:       public void add(Object element)
122:       {  
123:          if (position == null)
124:          {
125:             addFirst(element);
126:             position = first;
127:          }
128:          else
129:          {  
130:             Node newNode = new Node();
131:             newNode.data = element;
132:             newNode.next = position.next;
133:             position.next = newNode;
134:             position = newNode;
135:          }
136:          previous = position;
137:       }
138:       
139:       /**
140:          Removes the last traversed element. This method may
141:          only be called after a call to the next() method.
142:       */
143:       public void remove()
144:       {  
145:          if (previous == position)
146:             throw new IllegalStateException();
147: 
148:          if (position == first)
149:          {
150:             removeFirst();
151:          }
152:          else 
153:          {  
154:             previous.next = position.next;
155:          }
156:          position = previous;
157:       }
158: 
159:       /**
160:          Sets the last traversed element to a different 
161:          value. 
162:          @param element the element to set
163:       */
164:       public void set(Object element)
165:       {
166:          if (position == null)
167:             throw new NoSuchElementException();
168:          position.data = element;
169:       }
170:             
171:       private Node position;
172:       private Node previous;
173:    }
174: }