LinkedList Implementation question

Thread view:

H. - 02 Apr 2007 04:00 GMT

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?

Reply to this Message

Casey Hawthorne - 02 Apr 2007 05:22 GMT

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

Reply to this Message

Karl Uppiano - 02 Apr 2007 05:31 GMT

>I know that Java implements their LinkedLists as a doubly-linked
> list. Is there any documentation, though, which states whether only a
[quoted text clipped - 7 lines]
>
> Anyone know?

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

Reply to this Message

Lew - 02 Apr 2007 05:42 GMT

>> I know that Java implements their LinkedLists as a doubly-linked
>> list. Is there any documentation, though, which states whether only a
[quoted text clipped - 10 lines]
> 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

Reply to this Message

Mike Schilling - 02 Apr 2007 06:55 GMT

> 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).

Reply to this Message

Muntasir Azam Khan - 02 Apr 2007 16:40 GMT

On Apr 2, 11:55 am, "Mike Schilling" <mscottschill...@hotmail.com>
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.

Reply to this Message

LinkedList Implementation question

Free Magazines