001package algs13;
002import stdlib.*;
003import java.util.ConcurrentModificationException;
004import java.util.Iterator;
005import java.util.ListIterator;
006import java.util.NoSuchElementException;
007/* ***********************************************************************
008 *  Compilation:  javac LinkedList.java
009 *  Execution:    java LinkedList
010 *
011 *  A list implemented with a doubly linked list. The elements are stored
012 *  (and iterated over) in the same order that they are inserted.
013 *
014 *  % java List
015 *  This
016 *  is
017 *  a
018 *  test.
019 *
020 *  This
021 *  is
022 *  a
023 *  test.
024 *
025 *************************************************************************/
026
027public class LinkedList<T> implements Iterable<T> {
028        private int N;                 // number of elements on list
029        private final Node<T> pre;     // sentinel before first item
030        private final Node<T> post;    // sentinel after last item
031        private long opcount;
032
033        public LinkedList() {
034                pre  = new Node<>();
035                post = new Node<>();
036                pre.next = post;
037                post.prev = pre;
038        }
039
040        // linked list node helper data type
041        private static class Node<T> {
042                public Node() { }
043                public T item;
044                public Node<T> next;
045                public Node<T> prev;
046        }
047
048        public boolean isEmpty()    { return N == 0; }
049        public int size()           { return N;      }
050
051        // add the item to the end of the list
052        public void add(T item) {
053                Node<T> last = post.prev;
054                Node<T> x = new Node<>();
055                x.item = item;
056                x.next = post;
057                x.prev = last;
058                post.prev = x;
059                last.next = x;
060                N++;
061                opcount++;
062        }
063
064        public ListIterator<T> iterator()  { return new LinkedListIterator(); }
065
066        // assumes no calls to add() during iteration
067        private class LinkedListIterator implements ListIterator<T> {
068                private Node<T> current      = pre.next;  // the node that is returned by next()
069                private Node<T> lastAccessed = null;      // the last node to be returned by prev() or next()
070                // reset to null upon intervening remove() or add()
071                private int index = 0;
072                private long oc = opcount;
073                private void ocCheck() { if (opcount != oc) throw new ConcurrentModificationException (); }
074                private void ocInc()   { ocCheck(); opcount++; oc++; }
075
076                public boolean hasNext()      { ocCheck(); return index < N; }
077                public boolean hasPrevious()  { ocCheck(); return index > 0; }
078                public int previousIndex()    { ocCheck(); return index - 1; }
079                public int nextIndex()        { ocCheck(); return index;     }
080
081                public T next() {
082                        ocCheck();
083                        if (!hasNext()) throw new NoSuchElementException();
084                        lastAccessed = current;
085                        T item = current.item;
086                        current = current.next;
087                        index++;
088                        return item;
089                }
090
091                public T previous() {
092                        ocCheck();
093                        if (!hasPrevious()) throw new NoSuchElementException();
094                        current = current.prev;
095                        lastAccessed = current;
096                        T item = current.item;
097                        index--;
098                        return item;
099                }
100
101                // replace the item of the element that was last accessed by next() or previous()
102                // condition: no calls to remove() or add() after last call to next() or previous()
103                public void set(T item) {
104                        ocInc();
105                        if (lastAccessed == null) throw new Error();
106                        lastAccessed.item = item;
107                }
108
109                // remove the element that was last accessed by next() or previous()
110                // condition: no calls to remove() or add() after last call to next() or previous()
111                public void remove() {
112                        ocInc();
113                        if (lastAccessed == null) throw new Error();
114                        Node<T> lastPrev = lastAccessed.prev;
115                        Node<T> lastNext = lastAccessed.next;
116                        lastPrev.next = lastNext;
117                        lastNext.prev = lastPrev;
118                        N--;
119                        if (current == lastAccessed)
120                                current = lastNext;
121                        else
122                                index--;
123                        lastAccessed = null;
124                }
125
126                // add element to list
127                public void add(T item) {
128                        ocInc();
129                        Node<T> first  = current.prev;
130                        Node<T> middle = new Node<>();
131                        Node<T> last   = current;
132                        middle.item = item;
133                        first. next = middle;
134                        middle.next = last;
135                        last.  prev = middle;
136                        middle.prev = first;
137                        N++;
138                        index++;
139                        lastAccessed = null;
140                }
141
142        }
143
144        public String toString () {
145                StringBuilder sb = new StringBuilder ();
146                Iterator<T> it = this.iterator ();
147                if (it.hasNext ())
148                        sb.append (it.next ());
149                while (it.hasNext ()) {
150                        sb.append (" ");
151                        sb.append (it.next ());
152                }
153                return sb.toString ();
154        }
155
156        public static <T> void printForward(String s, LinkedList<Integer> list, ListIterator<T> iterator) {
157                StdOut.println();
158                StdOut.println(s);
159                StdOut.println(list);
160                while (iterator.hasNext())
161                        StdOut.format ("[%d,%d] ", iterator.nextIndex (), iterator.next ());
162                while (iterator.hasPrevious())
163                        StdOut.format ("[%d,%d] ", iterator.previousIndex (), iterator.previous());
164                StdOut.println ();
165        }
166        public static <T> void printBackward(String s, LinkedList<Integer> list, ListIterator<T> iterator) {
167                StdOut.println();
168                StdOut.println(s);
169                StdOut.println(list);
170                while (iterator.hasPrevious())
171                        StdOut.format ("[%d,%d] ", iterator.previousIndex (), iterator.previous());
172                while (iterator.hasNext())
173                        StdOut.format ("[%d,%d] ", iterator.nextIndex (), iterator.next ());
174                StdOut.println ();
175        }
176        // a test client
177        public static void main(String[] args) {
178                LinkedList<Integer> list = new LinkedList<>();
179
180                list.add(93);
181                list.add(48);
182                list.add(94);
183                list.add(4);
184                list.add(48);
185                list.add(94);
186
187                ListIterator<Integer> iterator = list.iterator();
188                printForward ("original", list, iterator);
189
190                // set forwards
191                while (iterator.hasNext()) {
192                        int x = iterator.next();
193                        iterator.set(x + 1);
194                }
195                printBackward ("after set forward", list, iterator);
196
197                // set backwards
198                while (iterator.hasPrevious()) {
199                        int x = iterator.previous();
200                        iterator.set(3 * x);
201                }
202                printForward ("after set backward", list, iterator);
203
204
205                // remove forwards
206                while (iterator.hasNext()) {
207                        int x = iterator.next();
208                        if (x % 2 == 0) iterator.remove();
209                }
210                printBackward ("after remove forward", list, iterator);
211
212                // remove backwards
213                while (iterator.hasPrevious()) {
214                        int x = iterator.previous();
215                        if (x % 5 == 0) iterator.remove();
216                }
217                printForward ("after remove backward", list, iterator);
218
219                // add forwards
220                while (iterator.hasNext()) {
221                        int x = iterator.next();
222                        iterator.add(x + 10);
223                }
224                printBackward ("after add forward", list, iterator);
225
226                // add backwards
227                while (iterator.hasPrevious()) {
228                        int x = iterator.previous();
229                        iterator.add(x - 1);
230                        iterator.previous();
231                }
232                printForward ("after add backward", list, iterator);
233        }
234}
235