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

Diff Legend

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