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.14 by jsr166, Sun Dec 28 00:55:45 2003 UTC vs.
Revision 1.22 by dl, Wed Mar 23 01:06:26 2005 UTC

#	Line 1 | Line 1
1		/*
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.<p>
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
#	Line 73 | Line 71 | package java.util;
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 154 | Line 152 | public class LinkedList<E>
152		}
153
154		/**
155	<	* Appends the given element to the end of this list.  (Identical in
155	>	* Appends the given element at the end of this list.  (Identical in
156		* function to the <tt>add</tt> method; included only for consistency.)
157		*
158		* @param o the element to be inserted at the end of this list.
#	Line 186 | Line 184 | public class LinkedList<E>
184		}
185
186		/**
187	<	* Appends the specified element to the end of this list.
187	>	* Appends the specified element at the end of this list.
188		*
189		* @param o element to be appended to this list.
190		* @return <tt>true</tt> (as per the general contract of
#	Line 227 | Line 225 | public class LinkedList<E>
225		}
226
227		/**
228	<	* Appends all of the elements in the specified collection to the end of
228	>	* Appends all of the elements in the specified collection at the end of
229		* this list, in the order that they are returned by the specified
230		* collection's iterator.  The behavior of this operation is undefined if
231		* the specified collection is modified while the operation is in
#	Line 306 | 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 445 | Line 443 | public class LinkedList<E>
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.
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() {
#	Line 456 | Line 454 | public class LinkedList<E>
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.
457	>	* @return the head of this list.
458	>	* @throws NoSuchElementException if this list is empty.
459		* @since 1.5
460		*/
461		public E element() {
#	Line 466 | Line 464 | public class LinkedList<E>
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.
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() {
#	Line 477 | Line 475 | public class LinkedList<E>
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.
478	>	* @return the head of this list.
479	>	* @throws NoSuchElementException if this list is empty.
480		* @since 1.5
481		*/
482		public E remove() {
#	Line 497 | Line 495 | public class LinkedList<E>
495		return add(o);
496		}
497
498	+	// Deque operations
499	+	/**
500	+	* Inserts the specified element at 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 at 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 at the front of 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 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 o 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 removeFirstOccurrence(Object o) {
617	+	return remove(o);
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		/**
649		* Returns a list-iterator of the elements in this list (in proper
650		* sequence), starting at the specified position in the list.

Diff Legend

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