ViewVC Help

View File | Revision Log | Show Annotations | Download File | Root Listing

root/jsr166/jsr166/src/main/java/util/LinkedList.java

Comparing jsr166/src/main/java/util/LinkedList.java (file contents):
Revision 1.43 by jsr166, Tue Jan 10 21:32:09 2006 UTC vs.
Revision 1.48 by jsr166, Sun May 18 23:47:56 2008 UTC

#	Line 1 | Line 1
1		/*
2	<	* %W% %E%
2	>	* Copyright 1997-2006 Sun Microsystems, Inc.  All Rights Reserved.
3	>	* DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER.
4		*
5	<	* Copyright 2006 Sun Microsystems, Inc. All rights reserved.
6	<	* SUN PROPRIETARY/CONFIDENTIAL. Use is subject to license terms.
5	>	* This code is free software; you can redistribute it and/or modify it
6	>	* under the terms of the GNU General Public License version 2 only, as
7	>	* published by the Free Software Foundation.  Sun designates this
8	>	* particular file as subject to the "Classpath" exception as provided
9	>	* by Sun in the LICENSE file that accompanied this code.
10	>	*
11	>	* This code is distributed in the hope that it will be useful, but WITHOUT
12	>	* ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
13	>	* FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License
14	>	* version 2 for more details (a copy is included in the LICENSE file that
15	>	* accompanied this code).
16	>	*
17	>	* You should have received a copy of the GNU General Public License version
18	>	* 2 along with this work; if not, write to the Free Software Foundation,
19	>	* Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA.
20	>	*
21	>	* Please contact Sun Microsystems, Inc., 4150 Network Circle, Santa Clara,
22	>	* CA 95054 USA or visit www.sun.com if you need additional information or
23	>	* have any questions.
24		*/
25
26		package java.util;
9	–	import java.util.*; // for javadoc (till 6280605 is fixed)
27
28		/**
29		* Linked list implementation of the <tt>List</tt> interface.  Implements all
#	Line 60 | Line 77 | import java.util.*; // for javadoc (till
77		* should be used only to detect bugs.</i>
78		*
79		* <p>This class is a member of the
80	<	* <a href="{@docRoot}/../guide/collections/index.html">
80	>	* <a href="{@docRoot}/../technotes/guides/collections/index.html">
81		* Java Collections Framework</a>.
82		*
83		* @author  Josh Bloch
84		* @version %I%, %G%
85	<	* @see     List
86	<	* @see     ArrayList
87	<	* @see     Vector
85	>	* @see     List
86	>	* @see     ArrayList
87	>	* @see     Vector
88		* @since 1.2
89		* @param <E> the type of elements held in this collection
90		*/
#	Line 95 | Line 112 | public class LinkedList<E>
112		* @throws NullPointerException if the specified collection is null
113		*/
114		public LinkedList(Collection<? extends E> c) {
115	<	this();
116	<	addAll(c);
115	>	this();
116	>	addAll(c);
117		}
118
119		/**
#	Line 106 | Line 123 | public class LinkedList<E>
123		* @throws NoSuchElementException if this list is empty
124		*/
125		public E getFirst() {
126	<	if (size==0)
127	<	throw new NoSuchElementException();
126	>	if (size==0)
127	>	throw new NoSuchElementException();
128
129	<	return header.next.element;
129	>	return header.next.element;
130		}
131
132		/**
#	Line 119 | Line 136 | public class LinkedList<E>
136		* @throws NoSuchElementException if this list is empty
137		*/
138		public E getLast()  {
139	<	if (size==0)
140	<	throw new NoSuchElementException();
139	>	if (size==0)
140	>	throw new NoSuchElementException();
141
142	<	return header.previous.element;
142	>	return header.previous.element;
143		}
144
145		/**
#	Line 132 | Line 149 | public class LinkedList<E>
149		* @throws NoSuchElementException if this list is empty
150		*/
151		public E removeFirst() {
152	<	return remove(header.next);
152	>	return remove(header.next);
153		}
154
155		/**
#	Line 142 | Line 159 | public class LinkedList<E>
159		* @throws NoSuchElementException if this list is empty
160		*/
161		public E removeLast() {
162	<	return remove(header.previous);
162	>	return remove(header.previous);
163		}
164
165		/**
#	Line 151 | Line 168 | public class LinkedList<E>
168		* @param e the element to add
169		*/
170		public void addFirst(E e) {
171	<	addBefore(e, header.next);
171	>	addBefore(e, header.next);
172		}
173
174		/**
#	Line 162 | Line 179 | public class LinkedList<E>
179		* @param e the element to add
180		*/
181		public void addLast(E e) {
182	<	addBefore(e, header);
182	>	addBefore(e, header);
183		}
184
185		/**
#	Line 184 | Line 201 | public class LinkedList<E>
201		* @return the number of elements in this list
202		*/
203		public int size() {
204	<	return size;
204	>	return size;
205		}
206
207		/**
#	Line 196 | Line 213 | public class LinkedList<E>
213		* @return <tt>true</tt> (as specified by {@link Collection#add})
214		*/
215		public boolean add(E e) {
216	<	addBefore(e, header);
216	>	addBefore(e, header);
217		return true;
218		}
219
#	Line 271 | Line 288 | public class LinkedList<E>
288		int numNew = a.length;
289		if (numNew==0)
290		return false;
291	<	modCount++;
291	>	modCount++;
292
293		Entry<E> successor = (index==size ? header : entry(index));
294		Entry<E> predecessor = successor.previous;
295	<	for (int i=0; i<numNew; i++) {
295	>	for (int i=0; i<numNew; i++) {
296		Entry<E> e = new Entry<E>((E)a[i], successor, predecessor);
297		predecessor.next = e;
298		predecessor = e;
#	Line 299 | Line 316 | public class LinkedList<E>
316		}
317		header.next = header.previous = header;
318		size = 0;
319	<	modCount++;
319	>	modCount++;
320		}
321
322
#	Line 665 | Line 682 | public class LinkedList<E>
682		* @see List#listIterator(int)
683		*/
684		public ListIterator<E> listIterator(int index) {
685	<	return new ListItr(index);
685	>	return new ListItr(index);
686		}
687
688		private class ListItr implements ListIterator<E> {
689	<	private Entry<E> lastReturned = header;
690	<	private Entry<E> next;
691	<	private int nextIndex;
692	<	private int expectedModCount = modCount;
693	<
694	<	ListItr(int index) {
695	<	if (index < 0 || index > size)
696	<	throw new IndexOutOfBoundsException("Index: "+index+
697	<	", Size: "+size);
698	<	if (index < (size >> 1)) {
699	<	next = header.next;
700	<	for (nextIndex=0; nextIndex<index; nextIndex++)
701	<	next = next.next;
702	<	} else {
703	<	next = header;
704	<	for (nextIndex=size; nextIndex>index; nextIndex--)
705	<	next = next.previous;
706	<	}
707	<	}
691	<
692	<	public boolean hasNext() {
693	<	return nextIndex != size;
694	<	}
695	<
696	<	public E next() {
697	<	checkForComodification();
698	<	if (nextIndex == size)
699	<	throw new NoSuchElementException();
700	<
701	<	lastReturned = next;
702	<	next = next.next;
703	<	nextIndex++;
704	<	return lastReturned.element;
705	<	}
706	<
707	<	public boolean hasPrevious() {
708	<	return nextIndex != 0;
709	<	}
710	<
711	<	public E previous() {
712	<	if (nextIndex == 0)
713	<	throw new NoSuchElementException();
714	<
715	<	lastReturned = next = next.previous;
716	<	nextIndex--;
717	<	checkForComodification();
718	<	return lastReturned.element;
719	<	}
720	<
721	<	public int nextIndex() {
722	<	return nextIndex;
723	<	}
724	<
725	<	public int previousIndex() {
726	<	return nextIndex-1;
727	<	}
689	>	private Entry<E> lastReturned = header;
690	>	private Entry<E> next;
691	>	private int nextIndex;
692	>	private int expectedModCount = modCount;
693	>
694	>	ListItr(int index) {
695	>	if (index < 0 || index > size)
696	>	throw new IndexOutOfBoundsException("Index: "+index+
697	>	", Size: "+size);
698	>	if (index < (size >> 1)) {
699	>	next = header.next;
700	>	for (nextIndex=0; nextIndex<index; nextIndex++)
701	>	next = next.next;
702	>	} else {
703	>	next = header;
704	>	for (nextIndex=size; nextIndex>index; nextIndex--)
705	>	next = next.previous;
706	>	}
707	>	}
708
709	<	public void remove() {
709	>	public boolean hasNext() {
710	>	return nextIndex != size;
711	>	}
712	>
713	>	public E next() {
714	>	checkForComodification();
715	>	if (nextIndex == size)
716	>	throw new NoSuchElementException();
717	>
718	>	lastReturned = next;
719	>	next = next.next;
720	>	nextIndex++;
721	>	return lastReturned.element;
722	>	}
723	>
724	>	public boolean hasPrevious() {
725	>	return nextIndex != 0;
726	>	}
727	>
728	>	public E previous() {
729	>	if (nextIndex == 0)
730	>	throw new NoSuchElementException();
731	>
732	>	lastReturned = next = next.previous;
733	>	nextIndex--;
734	>	checkForComodification();
735	>	return lastReturned.element;
736	>	}
737	>
738	>	public int nextIndex() {
739	>	return nextIndex;
740	>	}
741	>
742	>	public int previousIndex() {
743	>	return nextIndex-1;
744	>	}
745	>
746	>	public void remove() {
747		checkForComodification();
748		Entry<E> lastNext = lastReturned.next;
749		try {
#	Line 734 | Line 751 | public class LinkedList<E>
751		} catch (NoSuchElementException e) {
752		throw new IllegalStateException();
753		}
754	<	if (next==lastReturned)
754	>	if (next==lastReturned)
755		next = lastNext;
756		else
757	<	nextIndex--;
758	<	lastReturned = header;
759	<	expectedModCount++;
760	<	}
761	<
762	<	public void set(E e) {
763	<	if (lastReturned == header)
764	<	throw new IllegalStateException();
765	<	checkForComodification();
766	<	lastReturned.element = e;
767	<	}
768	<
769	<	public void add(E e) {
770	<	checkForComodification();
771	<	lastReturned = header;
772	<	addBefore(e, next);
773	<	nextIndex++;
774	<	expectedModCount++;
775	<	}
776	<
777	<	final void checkForComodification() {
778	<	if (modCount != expectedModCount)
779	<	throw new ConcurrentModificationException();
780	<	}
757	>	nextIndex--;
758	>	lastReturned = header;
759	>	expectedModCount++;
760	>	}
761	>
762	>	public void set(E e) {
763	>	if (lastReturned == header)
764	>	throw new IllegalStateException();
765	>	checkForComodification();
766	>	lastReturned.element = e;
767	>	}
768	>
769	>	public void add(E e) {
770	>	checkForComodification();
771	>	lastReturned = header;
772	>	addBefore(e, next);
773	>	nextIndex++;
774	>	expectedModCount++;
775	>	}
776	>
777	>	final void checkForComodification() {
778	>	if (modCount != expectedModCount)
779	>	throw new ConcurrentModificationException();
780	>	}
781		}
782
783		private static class Entry<E> {
784	<	E element;
785	<	Entry<E> next;
786	<	Entry<E> previous;
787	<
788	<	Entry(E element, Entry<E> next, Entry<E> previous) {
789	<	this.element = element;
790	<	this.next = next;
791	<	this.previous = previous;
792	<	}
784	>	E element;
785	>	Entry<E> next;
786	>	Entry<E> previous;
787	>
788	>	Entry(E element, Entry<E> next, Entry<E> previous) {
789	>	this.element = element;
790	>	this.next = next;
791	>	this.previous = previous;
792	>	}
793		}
794
795		private Entry<E> addBefore(E e, Entry<E> entry) {
796	<	Entry<E> newEntry = new Entry<E>(e, entry, entry.previous);
797	<	newEntry.previous.next = newEntry;
798	<	newEntry.next.previous = newEntry;
799	<	size++;
800	<	modCount++;
801	<	return newEntry;
796	>	Entry<E> newEntry = new Entry<E>(e, entry, entry.previous);
797	>	newEntry.previous.next = newEntry;
798	>	newEntry.next.previous = newEntry;
799	>	size++;
800	>	modCount++;
801	>	return newEntry;
802		}
803
804		private E remove(Entry<E> e) {
805	<	if (e == header)
806	<	throw new NoSuchElementException();
805	>	if (e == header)
806	>	throw new NoSuchElementException();
807
808		E result = e.element;
809	<	e.previous.next = e.next;
810	<	e.next.previous = e.previous;
809	>	e.previous.next = e.next;
810	>	e.next.previous = e.previous;
811		e.next = e.previous = null;
812		e.element = null;
813	<	size--;
814	<	modCount++;
813	>	size--;
814	>	modCount++;
815		return result;
816		}
817
#	Line 808 | Line 825 | public class LinkedList<E>
825		/** Adapter to provide descending iterators via ListItr.previous */
826		private class DescendingIterator implements Iterator {
827		final ListItr itr = new ListItr(size());
828	<	public boolean hasNext() {
829	<	return itr.hasPrevious();
830	<	}
831	<	public E next() {
828	>	public boolean hasNext() {
829	>	return itr.hasPrevious();
830	>	}
831	>	public E next() {
832		return itr.previous();
833		}
834	<	public void remove() {
834	>	public void remove() {
835		itr.remove();
836		}
837		}
#	Line 827 | Line 844 | public class LinkedList<E>
844		*/
845		public Object clone() {
846		LinkedList<E> clone = null;
847	<	try {
848	<	clone = (LinkedList<E>) super.clone();
849	<	} catch (CloneNotSupportedException e) {
850	<	throw new InternalError();
851	<	}
847	>	try {
848	>	clone = (LinkedList<E>) super.clone();
849	>	} catch (CloneNotSupportedException e) {
850	>	throw new InternalError();
851	>	}
852
853		// Put clone into "virgin" state
854		clone.header = new Entry<E>(null, null, null);
#	Line 861 | Line 878 | public class LinkedList<E>
878		*         in proper sequence
879		*/
880		public Object[] toArray() {
881	<	Object[] result = new Object[size];
881	>	Object[] result = new Object[size];
882		int i = 0;
883		for (Entry<E> e = header.next; e != header; e = e.next)
884		result[i++] = e.element;
885	<	return result;
885	>	return result;
886		}
887
888		/**
#	Line 911 | Line 928 | public class LinkedList<E>
928		a = (T[])java.lang.reflect.Array.newInstance(
929		a.getClass().getComponentType(), size);
930		int i = 0;
931	<	Object[] result = a;
931	>	Object[] result = a;
932		for (Entry<E> e = header.next; e != header; e = e.next)
933		result[i++] = e.element;
934
#	Line 933 | Line 950 | public class LinkedList<E>
950		*/
951		private void writeObject(java.io.ObjectOutputStream s)
952		throws java.io.IOException {
953	<	// Write out any hidden serialization magic
954	<	s.defaultWriteObject();
953	>	// Write out any hidden serialization magic
954	>	s.defaultWriteObject();
955
956		// Write out size
957		s.writeInt(size);
958
959	<	// Write out all elements in the proper order.
959	>	// Write out all elements in the proper order.
960		for (Entry e = header.next; e != header; e = e.next)
961		s.writeObject(e.element);
962		}
#	Line 950 | Line 967 | public class LinkedList<E>
967		*/
968		private void readObject(java.io.ObjectInputStream s)
969		throws java.io.IOException, ClassNotFoundException {
970	<	// Read in any hidden serialization magic
971	<	s.defaultReadObject();
970	>	// Read in any hidden serialization magic
971	>	s.defaultReadObject();
972
973		// Read in size
974		int size = s.readInt();
#	Line 960 | Line 977 | public class LinkedList<E>
977		header = new Entry<E>(null, null, null);
978		header.next = header.previous = header;
979
980	<	// Read in all elements in the proper order.
981	<	for (int i=0; i<size; i++)
980	>	// Read in all elements in the proper order.
981	>	for (int i=0; i<size; i++)
982		addBefore((E)s.readObject(), header);
983		}
984		}

Diff Legend

–	Removed lines
+	Added lines
<	Changed lines
>	Changed lines