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.4 by dl, Mon Aug 11 17:44:24 2003 UTC vs.
Revision 1.19 by dl, Tue Mar 1 01:27:15 2005 UTC

#	Line 1 | Line 1
1		/*
2	<	* @(#)LinkedList.java  1.53 03/06/22
2	>	* %W% %E%
3		*
4	<	* Copyright 2003 Sun Microsystems, Inc. All rights reserved.
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;
8	>	package java.util;
9
10		/**
11		* Linked list implementation of the <tt>List</tt> interface.  Implements all
#	Line 14 | Line 14 | package java.util;
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>
17	>	* used as a stack, {@linkplain Queue queue}, or {@linkplain Deque
18	>	* double-ended queue}. <p>
19		*
20	<	* The class implements the <tt>Queue</tt> interface, providing
20	>	* The class implements the <tt>Deque</tt> interface, providing
21		* first-in-first-out queue operations for <tt>add</tt>,
22	<	* <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>
22	>	* <tt>poll</tt>, along with other stack and deque operations.
23		*
24		* All of the operations perform as could be expected for a doubly-linked
25		* list.  Operations that index into the list will traverse the list from
26	<	* the begining or the end, whichever is closer to the specified index.<p>
26	>	* the beginning or the end, whichever is closer to the specified index.<p>
27		*
28		* <b>Note that this implementation is not synchronized.</b> If multiple
29		* threads access a list concurrently, and at least one of the threads
#	Line 62 | Line 60 | package java.util;
60		* Java Collections Framework</a>.
61		*
62		* @author  Josh Bloch
63	<	* @version 1.53, 06/22/03
63	>	* @version %I%, %G%
64		* @see     List
65		* @see     ArrayList
66		* @see     Vector
67		* @see     Collections#synchronizedList(List)
68		* @since 1.2
69	+	* @param <E> the type of elements held in this collection
70		*/
71
72		public class LinkedList<E>
73		extends AbstractSequentialList<E>
74	<	implements List<E>, Queue<E>, Cloneable, java.io.Serializable
74	>	implements List<E>, Deque<E>, Cloneable, java.io.Serializable
75		{
76		private transient Entry<E> header = new Entry<E>(null, null, null);
77		private transient int size = 0;
#	Line 130 | Line 129 | public class LinkedList<E>
129		* @throws    NoSuchElementException if this list is empty.
130		*/
131		public E removeFirst() {
132	<	E first = header.next.element;
134	<	remove(header.next);
135	<	return first;
132	>	return remove(header.next);
133		}
134
135		/**
#	Line 142 | Line 139 | public class LinkedList<E>
139		* @throws    NoSuchElementException if this list is empty.
140		*/
141		public E removeLast() {
142	<	E last = header.previous.element;
146	<	remove(header.previous);
147	<	return last;
142	>	return remove(header.previous);
143		}
144
145		/**
#	Line 288 | Line 283 | public class LinkedList<E>
283		* Removes all of the elements from this list.
284		*/
285		public void clear() {
286	<	modCount++;
286	>	Entry<E> e = header.next;
287	>	while (e != header) {
288	>	Entry<E> next = e.next;
289	>	e.next = e.previous = null;
290	>	e.element = null;
291	>	e = next;
292	>	}
293		header.next = header.previous = header;
294	<	size = 0;
294	>	size = 0;
295	>	modCount++;
296		}
297
298
#	Line 302 | Line 304 | public class LinkedList<E>
304		* @param index index of element to return.
305		* @return the element at the specified position in this list.
306		*
307	<	* @throws IndexOutOfBoundsException if the specified index is is out of
307	>	* @throws IndexOutOfBoundsException if the specified index is out of
308		* range (<tt>index &lt; 0 || index &gt;= size()</tt>).
309		*/
310		public E get(int index) {
#	Line 353 | Line 355 | public class LinkedList<E>
355		*            range (<tt>index &lt; 0 || index &gt;= size()</tt>).
356		*/
357		public E remove(int index) {
358	<	Entry<E> e = entry(index);
357	<	remove(e);
358	<	return e.element;
358	>	return remove(entry(index));
359		}
360
361		/**
#	Line 442 | Line 442 | public class LinkedList<E>
442		// Queue operations.
443
444		/**
445	<	* Retrieves, but does not remove, the head (first element) of this list..
446	<	* @return the head of this queue, or <tt>null</tt> if this queue is empty.
445	>	* Retrieves, but does not remove, the head (first element) of this list.
446	>	* @return the head of this list, or <tt>null</tt> if this list is empty.
447	>	* @since 1.5
448		*/
449		public E peek() {
450		if (size==0)
#	Line 452 | Line 453 | public class LinkedList<E>
453		}
454
455		/**
456	<	* Retrieves, but does not remove, the head (first element) of this list..
457	<	* @return the head of this queue.
458	<	* @throws NoSuchElementException if this queue is empty.
456	>	* Retrieves, but does not remove, the head (first element) of this list.
457	>	* @return the head of this list.
458	>	* @throws NoSuchElementException if this list is empty.
459	>	* @since 1.5
460		*/
461		public E element() {
462		return getFirst();
463		}
464
465		/**
466	<	* Retrieves and removes the head (first element) of this list..
467	<	* @return the head of this queue, or <tt>null</tt> if this queue is empty.
466	>	* Retrieves and removes the head (first element) of this list.
467	>	* @return the head of this list, or <tt>null</tt> if this list is empty.
468	>	* @since 1.5
469		*/
470		public E poll() {
471		if (size==0)
#	Line 471 | Line 474 | public class LinkedList<E>
474		}
475
476		/**
477	<	* Retrieves and removes the head (first element) of this list..
478	<	* @return the head of this queue.
479	<	* @throws NoSuchElementException if this queue is empty.
477	>	* Retrieves and removes the head (first element) of this list.
478	>	* @return the head of this list.
479	>	* @throws NoSuchElementException if this list is empty.
480	>	* @since 1.5
481		*/
482		public E remove() {
483		return removeFirst();
#	Line 485 | Line 489 | public class LinkedList<E>
489		* @param o the element to add.
490		* @return <tt>true</tt> (as per the general contract of
491		* <tt>Queue.offer</tt>)
492	+	* @since 1.5
493	+	*/
494	+	public boolean offer(E o) {
495	+	return add(o);
496	+	}
497	+
498	+	// Deque operations
499	+	/**
500	+	* Inserts the specified element to the front of this list.
501	+	*
502	+	* @param e the element to insert
503	+	* @return <tt>true</tt> (as per the spec for {@link Deque#offerFirst})
504	+	* @since 1.6
505	+	*/
506	+	public boolean offerFirst(E e) {
507	+	addFirst(e);
508	+	return true;
509	+	}
510	+
511	+	/**
512	+	* Inserts the specified element to the end of this list.
513	+	*
514	+	* @param e the element to insert
515	+	* @return <tt>true</tt> (as per the spec for {@link Deque#offerLast})
516	+	* @since 1.6
517	+	*/
518	+	public boolean offerLast(E e) {
519	+	addLast(e);
520	+	return true;
521	+	}
522	+
523	+	/**
524	+	* Retrieves, but does not remove, the first element of this list,
525	+	* returning <tt>null</tt> if this list is empty.
526	+	*
527	+	* @return the first element of this list, or <tt>null</tt> if
528	+	*     this list is empty
529	+	* @since 1.6
530	+	*/
531	+	public E peekFirst() {
532	+	if (size==0)
533	+	return null;
534	+	return getFirst();
535	+	}
536	+
537	+	/**
538	+	* Retrieves, but does not remove, the last element of this list,
539	+	* returning <tt>null</tt> if this list is empty.
540	+	*
541	+	* @return the last element of this list, or <tt>null</tt> if this list
542	+	*     is empty
543	+	* @since 1.6
544	+	*/
545	+	public E peekLast() {
546	+	if (size==0)
547	+	return null;
548	+	return getLast();
549	+	}
550	+
551	+	/**
552	+	* Retrieves and removes the first element of this list, or
553	+	* <tt>null</tt> if this list is empty.
554	+	*
555	+	* @return the first element of this list, or <tt>null</tt> if
556	+	*     this list is empty
557	+	* @since 1.6
558	+	*/
559	+	public E pollFirst() {
560	+	if (size==0)
561	+	return null;
562	+	return removeFirst();
563	+	}
564	+
565	+	/**
566	+	* Retrieves and removes the last element of this list, or
567	+	* <tt>null</tt> if this list is empty.
568	+	*
569	+	* @return the last element of this list, or <tt>null</tt> if
570	+	*     this list is empty
571	+	* @since 1.6
572	+	*/
573	+	public E pollLast() {
574	+	if (size==0)
575	+	return null;
576	+	return removeLast();
577	+	}
578	+
579	+	/**
580	+	* Pushes an element onto the stack represented by this list.  In other
581	+	* words, inserts the element to the front this list.
582	+	*
583	+	* <p>This method is equivalent to {@link #addFirst}.
584	+	*
585	+	* @param e the element to push
586	+	* @since 1.6
587	+	*/
588	+	public void push(E e) {
589	+	addFirst(e);
590	+	}
591	+
592	+	/**
593	+	* Pops an element from the stack represented by this list.  In other
594	+	* words, removes and returns the the first element of this list.
595	+	*
596	+	* <p>This method is equivalent to {@link #removeFirst()}.
597	+	*
598	+	* @return the element at the front of this list (which is the top
599	+	*     of the stack represented by this list)
600	+	* @throws NoSuchElementException if this list is empty
601	+	* @since 1.6
602	+	*/
603	+	public E pop() {
604	+	return removeFirst();
605	+	}
606	+
607	+	/**
608	+	* Removes the first occurrence of the specified element in this
609	+	* list (when traversing the list from head to tail).  If the list
610	+	* does not contain the element, it is unchanged.
611	+	*
612	+	* @param e element to be removed from this list, if present
613	+	* @return <tt>true</tt> if the list contained the specified element
614	+	* @since 1.6
615		*/
616	<	public boolean offer(E x) {
617	<	return add(x);
616	>	public boolean removeFirstOccurrence(Object e) {
617	>	return remove(e);
618	>	}
619	>
620	>	/**
621	>	* Removes the last occurrence of the specified element in this
622	>	* list (when traversing the list from head to tail).  If the list
623	>	* does not contain the element, it is unchanged.
624	>	*
625	>	* @param o element to be removed from this list, if present
626	>	* @return <tt>true</tt> if the list contained the specified element
627	>	* @since 1.6
628	>	*/
629	>	public boolean removeLastOccurrence(Object o) {
630	>	if (o==null) {
631	>	for (Entry e = header.previous; e != header; e = e.previous) {
632	>	if (e.element==null) {
633	>	remove(e);
634	>	return true;
635	>	}
636	>	}
637	>	} else {
638	>	for (Entry e = header.previous; e != header; e = e.previous) {
639	>	if (o.equals(e.element)) {
640	>	remove(e);
641	>	return true;
642	>	}
643	>	}
644	>	}
645	>	return false;
646		}
647
648		/**
#	Line 576 | Line 731 | public class LinkedList<E>
731
732		public void remove() {
733		checkForComodification();
734	+	Entry<E> lastNext = lastReturned.next;
735		try {
736		LinkedList.this.remove(lastReturned);
737		} catch (NoSuchElementException e) {
738		throw new IllegalStateException();
739		}
740		if (next==lastReturned)
741	<	next = lastReturned.next;
741	>	next = lastNext;
742		else
743		nextIndex--;
744		lastReturned = header;
#	Line 631 | Line 787 | public class LinkedList<E>
787		return newEntry;
788		}
789
790	<	private void remove(Entry<E> e) {
790	>	private E remove(Entry<E> e) {
791		if (e == header)
792		throw new NoSuchElementException();
793
794	+	E result = e.element;
795		e.previous.next = e.next;
796		e.next.previous = e.previous;
797	+	e.next = e.previous = null;
798	+	e.element = null;
799		size--;
800		modCount++;
801	+	return result;
802		}
803
804		/**

Diff Legend

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