LinkedList Implementation question

[H.]

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?

 

[Casey Hawthorne]

Why not a "deque"?

 

[Karl Uppiano]

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/

 

[Lew]

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

 

[Mike Schilling]

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

 

[Muntasir Azam Khan]

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.