KickJava   Java API By Example, From Geeks To Geeks.

Java > Open Source Codes > java > util > LinkedList


1 /*
2  * @(#)LinkedList.java 1.61 04/02/19
3  *
4  * Copyright 2004 Sun Microsystems, Inc. All rights reserved.
5  * SUN PROPRIETARY/CONFIDENTIAL. Use is subject to license terms.
6  */

7
8 package java.util;
9
10 /**
11  * Linked list implementation of the <tt>List</tt> interface. Implements all
12  * optional list operations, and permits all elements (including
13  * <tt>null</tt>). In addition to implementing the <tt>List</tt> interface,
14  * the <tt>LinkedList</tt> class provides uniformly named methods to
15  * <tt>get</tt>, <tt>remove</tt> and <tt>insert</tt> an element at the
16  * beginning and end of the list. These operations allow linked lists to be
17  * used as a stack, queue, or double-ended queue (deque).<p>
18  *
19  * The class implements the <tt>Queue</tt> interface, providing
20  * first-in-first-out queue operations for <tt>add</tt>,
21  * <tt>poll</tt>, etc. Other stack and deque operations could be
22  * easily recast in terms of the standard list operations. They're
23  * included here primarily for convenience, though they may run
24  * slightly faster than the equivalent List operations.<p>
25  *
26  * All of the operations perform as could be expected for a doubly-linked
27  * list. Operations that index into the list will traverse the list from
28  * the beginning or the end, whichever is closer to the specified index.<p>
29  *
30  * <b>Note that this implementation is not synchronized.</b> If multiple
31  * threads access a list concurrently, and at least one of the threads
32  * modifies the list structurally, it <i>must</i> be synchronized
33  * externally. (A structural modification is any operation that adds or
34  * deletes one or more elements; merely setting the value of an element is not
35  * a structural modification.) This is typically accomplished by
36  * synchronizing on some object that naturally encapsulates the list. If no
37  * such object exists, the list should be "wrapped" using the
38  * Collections.synchronizedList method. This is best done at creation time,
39  * to prevent accidental unsynchronized access to the list: <pre>
40  * List list = Collections.synchronizedList(new LinkedList(...));
41  * </pre><p>
42  *
43  * The iterators returned by the this class's <tt>iterator</tt> and
44  * <tt>listIterator</tt> methods are <i>fail-fast</i>: if the list is
45  * structurally modified at any time after the iterator is created, in any way
46  * except through the Iterator's own <tt>remove</tt> or <tt>add</tt> methods,
47  * the iterator will throw a <tt>ConcurrentModificationException</tt>. Thus,
48  * in the face of concurrent modification, the iterator fails quickly and
49  * cleanly, rather than risking arbitrary, non-deterministic behavior at an
50  * undetermined time in the future.
51  *
52  * <p>Note that the fail-fast behavior of an iterator cannot be guaranteed
53  * as it is, generally speaking, impossible to make any hard guarantees in the
54  * presence of unsynchronized concurrent modification. Fail-fast iterators
55  * throw <tt>ConcurrentModificationException</tt> on a best-effort basis.
56  * Therefore, it would be wrong to write a program that depended on this
57  * exception for its correctness: <i>the fail-fast behavior of iterators
58  * should be used only to detect bugs.</i><p>
59  *
60  * This class is a member of the
61  * <a HREF="{@docRoot}/../guide/collections/index.html">
62  * Java Collections Framework</a>.
63  *
64  * @author Josh Bloch
65  * @version 1.61, 02/19/04
66  * @see List
67  * @see ArrayList
68  * @see Vector
69  * @see Collections#synchronizedList(List)
70  * @since 1.2
71  * @param <E> the type of elements held in this collection
72  */

73
74 public class LinkedList<E>
75     extends AbstractSequentialList JavaDoc<E>
76     implements List JavaDoc<E>, Queue JavaDoc<E>, Cloneable JavaDoc, java.io.Serializable JavaDoc
77 {
78     private transient Entry<E> header = new Entry<E>(null, null, null);
79     private transient int size = 0;
80
81     /**
82      * Constructs an empty list.
83      */

84     public LinkedList() {
85         header.next = header.previous = header;
86     }
87
88     /**
89      * Constructs a list containing the elements of the specified
90      * collection, in the order they are returned by the collection's
91      * iterator.
92      *
93      * @param c the collection whose elements are to be placed into this list.
94      * @throws NullPointerException if the specified collection is null.
95      */

96      public LinkedList(Collection JavaDoc<? extends E> c) {
97      this();
98      addAll(c);
99      }
100
101     /**
102      * Returns the first element in this list.
103      *
104      * @return the first element in this list.
105      * @throws NoSuchElementException if this list is empty.
106      */

107     public E getFirst() {
108     if (size==0)
109         throw new NoSuchElementException JavaDoc();
110
111     return header.next.element;
112     }
113
114     /**
115      * Returns the last element in this list.
116      *
117      * @return the last element in this list.
118      * @throws NoSuchElementException if this list is empty.
119      */

120     public E getLast() {
121     if (size==0)
122         throw new NoSuchElementException JavaDoc();
123
124     return header.previous.element;
125     }
126
127     /**
128      * Removes and returns the first element from this list.
129      *
130      * @return the first element from this list.
131      * @throws NoSuchElementException if this list is empty.
132      */

133     public E removeFirst() {
134     return remove(header.next);
135     }
136
137     /**
138      * Removes and returns the last element from this list.
139      *
140      * @return the last element from this list.
141      * @throws NoSuchElementException if this list is empty.
142      */

143     public E removeLast() {
144     return remove(header.previous);
145     }
146
147     /**
148      * Inserts the given element at the beginning of this list.
149      *
150      * @param o the element to be inserted at the beginning of this list.
151      */

152     public void addFirst(E o) {
153     addBefore(o, header.next);
154     }
155
156     /**
157      * Appends the given element to the end of this list. (Identical in
158      * function to the <tt>add</tt> method; included only for consistency.)
159      *
160      * @param o the element to be inserted at the end of this list.
161      */

162     public void addLast(E o) {
163     addBefore(o, header);
164     }
165
166     /**
167      * Returns <tt>true</tt> if this list contains the specified element.
168      * More formally, returns <tt>true</tt> if and only if this list contains
169      * at least one element <tt>e</tt> such that <tt>(o==null ? e==null
170      * : o.equals(e))</tt>.
171      *
172      * @param o element whose presence in this list is to be tested.
173      * @return <tt>true</tt> if this list contains the specified element.
174      */

175     public boolean contains(Object JavaDoc o) {
176         return indexOf(o) != -1;
177     }
178
179     /**
180      * Returns the number of elements in this list.
181      *
182      * @return the number of elements in this list.
183      */

184     public int size() {
185     return size;
186     }
187
188     /**
189      * Appends the specified element to the end of this list.
190      *
191      * @param o element to be appended to this list.
192      * @return <tt>true</tt> (as per the general contract of
193      * <tt>Collection.add</tt>).
194      */

195     public boolean add(E o) {
196     addBefore(o, header);
197         return true;
198     }
199
200     /**
201      * Removes the first occurrence of the specified element in this list. If
202      * the list does not contain the element, it is unchanged. More formally,
203      * removes the element with the lowest index <tt>i</tt> such that
204      * <tt>(o==null ? get(i)==null : o.equals(get(i)))</tt> (if such an
205      * element exists).
206      *
207      * @param o element to be removed from this list, if present.
208      * @return <tt>true</tt> if the list contained the specified element.
209      */

210     public boolean remove(Object JavaDoc o) {
211         if (o==null) {
212             for (Entry<E> e = header.next; e != header; e = e.next) {
213                 if (e.element==null) {
214                     remove(e);
215                     return true;
216                 }
217             }
218         } else {
219             for (Entry<E> e = header.next; e != header; e = e.next) {
220                 if (o.equals(e.element)) {
221                     remove(e);
222                     return true;
223                 }
224             }
225         }
226         return false;
227     }
228
229     /**
230      * Appends all of the elements in the specified collection to the end of
231      * this list, in the order that they are returned by the specified
232      * collection's iterator. The behavior of this operation is undefined if
233      * the specified collection is modified while the operation is in
234      * progress. (This implies that the behavior of this call is undefined if
235      * the specified Collection is this list, and this list is nonempty.)
236      *
237      * @param c the elements to be inserted into this list.
238      * @return <tt>true</tt> if this list changed as a result of the call.
239      * @throws NullPointerException if the specified collection is null.
240      */

241     public boolean addAll(Collection JavaDoc<? extends E> c) {
242         return addAll(size, c);
243     }
244
245     /**
246      * Inserts all of the elements in the specified collection into this
247      * list, starting at the specified position. Shifts the element
248      * currently at that position (if any) and any subsequent elements to
249      * the right (increases their indices). The new elements will appear
250      * in the list in the order that they are returned by the
251      * specified collection's iterator.
252      *
253      * @param index index at which to insert first element
254      * from the specified collection.
255      * @param c elements to be inserted into this list.
256      * @return <tt>true</tt> if this list changed as a result of the call.
257      * @throws IndexOutOfBoundsException if the specified index is out of
258      * range (<tt>index &lt; 0 || index &gt; size()</tt>).
259      * @throws NullPointerException if the specified collection is null.
260      */

261     public boolean addAll(int index, Collection JavaDoc<? extends E> c) {
262         if (index < 0 || index > size)
263             throw new IndexOutOfBoundsException JavaDoc("Index: "+index+
264                                                 ", Size: "+size);
265         Object JavaDoc[] a = c.toArray();
266         int numNew = a.length;
267         if (numNew==0)
268             return false;
269     modCount++;
270
271         Entry<E> successor = (index==size ? header : entry(index));
272         Entry<E> predecessor = successor.previous;
273     for (int i=0; i<numNew; i++) {
274             Entry<E> e = new Entry<E>((E)a[i], successor, predecessor);
275             predecessor.next = e;
276             predecessor = e;
277         }
278         successor.previous = predecessor;
279
280         size += numNew;
281         return true;
282     }
283
284     /**
285      * Removes all of the elements from this list.
286      */

287     public void clear() {
288         Entry<E> e = header.next;
289         while (e != header) {
290             Entry<E> next = e.next;
291             e.next = e.previous = null;
292             e.element = null;
293             e = next;
294         }
295         header.next = header.previous = header;
296         size = 0;
297     modCount++;
298     }
299
300
301     // Positional Access Operations
302

303     /**
304      * Returns the element at the specified position in this list.
305      *
306      * @param index index of element to return.
307      * @return the element at the specified position in this list.
308      *
309      * @throws IndexOutOfBoundsException if the specified index is out of
310      * range (<tt>index &lt; 0 || index &gt;= size()</tt>).
311      */

312     public E get(int index) {
313         return entry(index).element;
314     }
315
316     /**
317      * Replaces the element at the specified position in this list with the
318      * specified element.
319      *
320      * @param index index of element to replace.
321      * @param element element to be stored at the specified position.
322      * @return the element previously at the specified position.
323      * @throws IndexOutOfBoundsException if the specified index is out of
324      * range (<tt>index &lt; 0 || index &gt;= size()</tt>).
325      */

326     public E set(int index, E element) {
327         Entry<E> e = entry(index);
328         E oldVal = e.element;
329         e.element = element;
330         return oldVal;
331     }
332
333     /**
334      * Inserts the specified element at the specified position in this list.
335      * Shifts the element currently at that position (if any) and any
336      * subsequent elements to the right (adds one to their indices).
337      *
338      * @param index index at which the specified element is to be inserted.
339      * @param element element to be inserted.
340      *
341      * @throws IndexOutOfBoundsException if the specified index is out of
342      * range (<tt>index &lt; 0 || index &gt; size()</tt>).
343      */

344     public void add(int index, E element) {
345         addBefore(element, (index==size ? header : entry(index)));
346     }
347
348     /**
349      * Removes the element at the specified position in this list. Shifts any
350      * subsequent elements to the left (subtracts one from their indices).
351      * Returns the element that was removed from the list.
352      *
353      * @param index the index of the element to removed.
354      * @return the element previously at the specified position.
355      *
356      * @throws IndexOutOfBoundsException if the specified index is out of
357      * range (<tt>index &lt; 0 || index &gt;= size()</tt>).
358      */

359     public E remove(int index) {
360         return remove(entry(index));
361     }
362
363     /**
364      * Return the indexed entry.
365      */

366     private Entry<E> entry(int index) {
367         if (index < 0 || index >= size)
368             throw new IndexOutOfBoundsException JavaDoc("Index: "+index+
369                                                 ", Size: "+size);
370         Entry<E> e = header;
371         if (index < (size >> 1)) {
372             for (int i = 0; i <= index; i++)
373                 e = e.next;
374         } else {
375             for (int i = size; i > index; i--)
376                 e = e.previous;
377         }
378         return e;
379     }
380
381
382     // Search Operations
383

384     /**
385      * Returns the index in this list of the first occurrence of the
386      * specified element, or -1 if the List does not contain this
387      * element. More formally, returns the lowest index i such that
388      * <tt>(o==null ? get(i)==null : o.equals(get(i)))</tt>, or -1 if
389      * there is no such index.
390      *
391      * @param o element to search for.
392      * @return the index in this list of the first occurrence of the
393      * specified element, or -1 if the list does not contain this
394      * element.
395      */

396     public int indexOf(Object JavaDoc o) {
397         int index = 0;
398         if (o==null) {
399             for (Entry e = header.next; e != header; e = e.next) {
400                 if (e.element==null)
401                     return index;
402                 index++;
403             }
404         } else {
405             for (Entry e = header.next; e != header; e = e.next) {
406                 if (o.equals(e.element))
407                     return index;
408                 index++;
409             }
410         }
411         return -1;
412     }
413
414     /**
415      * Returns the index in this list of the last occurrence of the
416      * specified element, or -1 if the list does not contain this
417      * element. More formally, returns the highest index i such that
418      * <tt>(o==null ? get(i)==null : o.equals(get(i)))</tt>, or -1 if
419      * there is no such index.
420      *
421      * @param o element to search for.
422      * @return the index in this list of the last occurrence of the
423      * specified element, or -1 if the list does not contain this
424      * element.
425      */

426     public int lastIndexOf(Object JavaDoc o) {
427         int index = size;
428         if (o==null) {
429             for (Entry e = header.previous; e != header; e = e.previous) {
430                 index--;
431                 if (e.element==null)
432                     return index;
433             }
434         } else {
435             for (Entry e = header.previous; e != header; e = e.previous) {
436                 index--;
437                 if (o.equals(e.element))
438                     return index;
439             }
440         }
441         return -1;
442     }
443
444     // Queue operations.
445

446     /**
447      * Retrieves, but does not remove, the head (first element) of this list.
448      * @return the head of this queue, or <tt>null</tt> if this queue is empty.
449      * @since 1.5
450      */

451     public E peek() {
452         if (size==0)
453             return null;
454         return getFirst();
455     }
456
457     /**
458      * Retrieves, but does not remove, the head (first element) of this list.
459      * @return the head of this queue.
460      * @throws NoSuchElementException if this queue is empty.
461      * @since 1.5
462      */

463     public E element() {
464         return getFirst();
465     }
466
467     /**
468      * Retrieves and removes the head (first element) of this list.
469      * @return the head of this queue, or <tt>null</tt> if this queue is empty.
470      * @since 1.5
471      */

472     public E poll() {
473         if (size==0)
474             return null;
475         return removeFirst();
476     }
477
478     /**
479      * Retrieves and removes the head (first element) of this list.
480      * @return the head of this queue.
481      * @throws NoSuchElementException if this queue is empty.
482      * @since 1.5
483      */

484     public E remove() {
485         return removeFirst();
486     }
487
488     /**
489      * Adds the specified element as the tail (last element) of this list.
490      *
491      * @param o the element to add.
492      * @return <tt>true</tt> (as per the general contract of
493      * <tt>Queue.offer</tt>)
494      * @since 1.5
495      */

496     public boolean offer(E o) {
497         return add(o);
498     }
499
500     /**
501      * Returns a list-iterator of the elements in this list (in proper
502      * sequence), starting at the specified position in the list.
503      * Obeys the general contract of <tt>List.listIterator(int)</tt>.<p>
504      *
505      * The list-iterator is <i>fail-fast</i>: if the list is structurally
506      * modified at any time after the Iterator is created, in any way except
507      * through the list-iterator's own <tt>remove</tt> or <tt>add</tt>
508      * methods, the list-iterator will throw a
509      * <tt>ConcurrentModificationException</tt>. Thus, in the face of
510      * concurrent modification, the iterator fails quickly and cleanly, rather
511      * than risking arbitrary, non-deterministic behavior at an undetermined
512      * time in the future.
513      *
514      * @param index index of first element to be returned from the
515      * list-iterator (by a call to <tt>next</tt>).
516      * @return a ListIterator of the elements in this list (in proper
517      * sequence), starting at the specified position in the list.
518      * @throws IndexOutOfBoundsException if index is out of range
519      * (<tt>index &lt; 0 || index &gt; size()</tt>).
520      * @see List#listIterator(int)
521      */

522     public ListIterator JavaDoc<E> listIterator(int index) {
523     return new ListItr(index);
524     }
525
526     private class ListItr implements ListIterator JavaDoc<E> {
527     private Entry<E> lastReturned = header;
528     private Entry<E> next;
529     private int nextIndex;
530     private int expectedModCount = modCount;
531
532     ListItr(int index) {
533         if (index < 0 || index > size)
534         throw new IndexOutOfBoundsException JavaDoc("Index: "+index+
535                             ", Size: "+size);
536         if (index < (size >> 1)) {
537         next = header.next;
538         for (nextIndex=0; nextIndex<index; nextIndex++)
539             next = next.next;
540         } else {
541         next = header;
542         for (nextIndex=size; nextIndex>index; nextIndex--)
543             next = next.previous;
544         }
545     }
546
547     public boolean hasNext() {
548         return nextIndex != size;
549     }
550
551     public E next() {
552         checkForComodification();
553         if (nextIndex == size)
554         throw new NoSuchElementException JavaDoc();
555
556         lastReturned = next;
557         next = next.next;
558         nextIndex++;
559         return lastReturned.element;
560     }
561
562     public boolean hasPrevious() {
563         return nextIndex != 0;
564     }
565
566     public E previous() {
567         if (nextIndex == 0)
568         throw new NoSuchElementException JavaDoc();
569
570         lastReturned = next = next.previous;
571         nextIndex--;
572         checkForComodification();
573         return lastReturned.element;
574     }
575
576     public int nextIndex() {
577         return nextIndex;
578     }
579
580     public int previousIndex() {
581         return nextIndex-1;
582     }
583
584     public void remove() {
585             checkForComodification();
586             Entry<E> lastNext = lastReturned.next;
587             try {
588                 LinkedList.this.remove(lastReturned);
589             } catch (NoSuchElementException JavaDoc e) {
590                 throw new IllegalStateException JavaDoc();
591             }
592         if (next==lastReturned)
593                 next = lastNext;
594             else
595         nextIndex--;
596         lastReturned = header;
597         expectedModCount++;
598     }
599
600     public void set(E o) {
601         if (lastReturned == header)
602         throw new IllegalStateException JavaDoc();
603         checkForComodification();
604         lastReturned.element = o;
605     }
606
607     public void add(E o) {
608         checkForComodification();
609         lastReturned = header;
610         addBefore(o, next);
611         nextIndex++;
612         expectedModCount++;
613     }
614
615     final void checkForComodification() {
616         if (modCount != expectedModCount)
617         throw new ConcurrentModificationException JavaDoc();
618     }
619     }
620
621     private static class Entry<E> {
622     E element;
623     Entry<E> next;
624     Entry<E> previous;
625
626     Entry(E element, Entry<E> next, Entry<E> previous) {
627         this.element = element;
628         this.next = next;
629         this.previous = previous;
630     }
631     }
632
633     private Entry<E> addBefore(E o, Entry<E> e) {
634     Entry<E> newEntry = new Entry<E>(o, e, e.previous);
635     newEntry.previous.next = newEntry;
636     newEntry.next.previous = newEntry;
637     size++;
638     modCount++;
639     return newEntry;
640     }
641
642     private E remove(Entry<E> e) {
643     if (e == header)
644         throw new NoSuchElementException JavaDoc();
645
646         E result = e.element;
647     e.previous.next = e.next;
648     e.next.previous = e.previous;
649         e.next = e.previous = null;
650         e.element = null;
651     size--;
652     modCount++;
653         return result;
654     }
655
656     /**
657      * Returns a shallow copy of this <tt>LinkedList</tt>. (The elements
658      * themselves are not cloned.)
659      *
660      * @return a shallow copy of this <tt>LinkedList</tt> instance.
661      */

662     public Object JavaDoc clone() {
663         LinkedList JavaDoc<E> clone = null;
664     try {
665         clone = (LinkedList JavaDoc<E>) super.clone();
666     } catch (CloneNotSupportedException JavaDoc e) {
667         throw new InternalError JavaDoc();
668     }
669
670         // Put clone into "virgin" state
671
clone.header = new Entry<E>(null, null, null);
672         clone.header.next = clone.header.previous = clone.header;
673         clone.size = 0;
674         clone.modCount = 0;
675
676         // Initialize clone with our elements
677
for (Entry<E> e = header.next; e != header; e = e.next)
678             clone.add(e.element);
679
680         return clone;
681     }
682
683     /**
684      * Returns an array containing all of the elements in this list
685      * in the correct order.
686      *
687      * @return an array containing all of the elements in this list
688      * in the correct order.
689      */

690     public Object JavaDoc[] toArray() {
691     Object JavaDoc[] result = new Object JavaDoc[size];
692         int i = 0;
693         for (Entry<E> e = header.next; e != header; e = e.next)
694             result[i++] = e.element;
695     return result;
696     }
697
698     /**
699      * Returns an array containing all of the elements in this list in
700      * the correct order; the runtime type of the returned array is that of
701      * the specified array. If the list fits in the specified array, it
702      * is returned therein. Otherwise, a new array is allocated with the
703      * runtime type of the specified array and the size of this list.<p>
704      *
705      * If the list fits in the specified array with room to spare
706      * (i.e., the array has more elements than the list),
707      * the element in the array immediately following the end of the
708      * collection is set to null. This is useful in determining the length
709      * of the list <i>only</i> if the caller knows that the list
710      * does not contain any null elements.
711      *
712      * @param a the array into which the elements of the list are to
713      * be stored, if it is big enough; otherwise, a new array of the
714      * same runtime type is allocated for this purpose.
715      * @return an array containing the elements of the list.
716      * @throws ArrayStoreException if the runtime type of a is not a
717      * supertype of the runtime type of every element in this list.
718      * @throws NullPointerException if the specified array is null.
719      */

720     public <T> T[] toArray(T[] a) {
721         if (a.length < size)
722             a = (T[])java.lang.reflect.Array.newInstance(
723                                 a.getClass().getComponentType(), size);
724         int i = 0;
725     Object JavaDoc[] result = a;
726         for (Entry<E> e = header.next; e != header; e = e.next)
727             result[i++] = e.element;
728
729         if (a.length > size)
730             a[size] = null;
731
732         return a;
733     }
734
735     private static final long serialVersionUID = 876323262645176354L;
736
737     /**
738      * Save the state of this <tt>LinkedList</tt> instance to a stream (that
739      * is, serialize it).
740      *
741      * @serialData The size of the list (the number of elements it
742      * contains) is emitted (int), followed by all of its
743      * elements (each an Object) in the proper order.
744      */

745     private void writeObject(java.io.ObjectOutputStream JavaDoc s)
746         throws java.io.IOException JavaDoc {
747     // Write out any hidden serialization magic
748
s.defaultWriteObject();
749
750         // Write out size
751
s.writeInt(size);
752
753     // Write out all elements in the proper order.
754
for (Entry e = header.next; e != header; e = e.next)
755             s.writeObject(e.element);
756     }
757
758     /**
759      * Reconstitute this <tt>LinkedList</tt> instance from a stream (that is
760      * deserialize it).
761      */

762     private void readObject(java.io.ObjectInputStream JavaDoc s)
763         throws java.io.IOException JavaDoc, ClassNotFoundException JavaDoc {
764     // Read in any hidden serialization magic
765
s.defaultReadObject();
766
767         // Read in size
768
int size = s.readInt();
769
770         // Initialize header
771
header = new Entry<E>(null, null, null);
772         header.next = header.previous = header;
773
774     // Read in all elements in the proper order.
775
for (int i=0; i<size; i++)
776             addBefore((E)s.readObject(), header);
777     }
778 }
779
Popular Tags