«

I know that Java implements their LinkedLists as a doubly-linked
list. Is there any documentation, though, which states whether only a
head sentinel is used, or both head and tail sentinels.

I'm planning on using the LinkedList as a Queue that will have
potentially thousands of items, and a tail sentinel in the doubly-
linked list would ensure that addLast() has constant performance
instead of theta(n) performance; this would have major time
implications.

Anyone know?

Why not a "deque"?
--
Regards,
Casey

"H." <> wrote in message
news: oups.com...
>I know that Java implements their LinkedLists as a doubly-linked
> list. Is there any documentation, though, which states whether only a
> head sentinel is used, or both head and tail sentinels.
>
> I'm planning on using the LinkedList as a Queue that will have
> potentially thousands of items, and a tail sentinel in the doubly-
> linked list would ensure that addLast() has constant performance
> instead of theta(n) performance; this would have major time
> implications.
>
> Anyone know?

I could go download the source and find out, but I'll let you do that.
http://download.java.net/jdk6/

Karl Uppiano wrote:
> "H." <> wrote in message
> news: oups.com...
>> I know that Java implements their LinkedLists as a doubly-linked
>> list. Is there any documentation, though, which states whether only a
>> head sentinel is used, or both head and tail sentinels.
>>
>> I'm planning on using the LinkedList as a Queue that will have
>> potentially thousands of items, and a tail sentinel in the doubly-
>> linked list would ensure that addLast() has constant performance
>> instead of theta(n) performance; this would have major time
>> implications.
>>
>> Anyone know?
>
> I could go download the source and find out, but I'll let you do that.
> http://download.java.net/jdk6/

I tried reading the API docs and found this:

> All of the operations perform as could be expected for a doubly-linked list. Operations that index into the list will traverse the list from the beginning or the end, whichever is closer to the specified index.

Which says some things to me:
- "as could be expected" is vague and dismissive and falls short of what I
expect from Sun;
- the implementation knows where both the beginning (head) and end (tail) of
the list are - whether it does so with sentinels (I'm guessing not) or
pointers to the head and tail (I'm guessing so) doesn't seem too terribly
relevant to me;
and
- operations that index into the list perform O(n) with the length of the list.

If your worry is that performance of methods like addLast(e) or getLast()
might suck, I'd feel safe in betting that LinkedList addresses your concern.
It seems to be one of Sun's main candidates for the Deque interface poster
implementation, the other is ArrayDeque. That latter's documentation is more
specific about its runtime performance.

You could always run some timing tests if you want to be certain.

-- Lew

H. wrote:
> I know that Java implements their LinkedLists as a doubly-linked
> list. Is there any documentation, though, which states whether only a
> head sentinel is used, or both head and tail sentinels.

IIRC, there's a single listhead that points to both first and last mebers of
the list. At any rate, access to the end of the list is O(1).

On Apr 2, 11:55 am, "Mike Schilling" <mscottschill...@hotmail.com>
wrote:
> H. wrote:
> > I know that Java implements their LinkedLists as a doubly-linked
> > list. Is there any documentation, though, which states whether only a
> > head sentinel is used, or both head and tail sentinels.
>
> IIRC, there's a single listhead that points to both first and last mebers of
> the list. At any rate, access to the end of the list is O(1).


I agree. Just look up LinkedList.java and you will see. Both addFirst
and addLast are O(1). I think you are safe with plain old LinkedList.