Velocity Reviews - Computer Hardware Reviews

Velocity Reviews > Newsgroups > Programming > Java > LinkedList Implementation question

Reply
Thread Tools

LinkedList Implementation question

 
 
H.
Guest
Posts: n/a
 
      04-02-2007
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 With Quote
 
 
 
 
Casey Hawthorne
Guest
Posts: n/a
 
      04-02-2007
Why not a "deque"?
--
Regards,
Casey
 
Reply With Quote
 
 
 
 
Karl Uppiano
Guest
Posts: n/a
 
      04-02-2007

"H." <(E-Mail Removed)> wrote in message
news:(E-Mail Removed) 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/


 
Reply With Quote
 
Lew
Guest
Posts: n/a
 
      04-02-2007
Karl Uppiano wrote:
> "H." <(E-Mail Removed)> wrote in message
> news:(E-Mail Removed) 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
 
Reply With Quote
 
Mike Schilling
Guest
Posts: n/a
 
      04-02-2007
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).


 
Reply With Quote
 
Muntasir Azam Khan
Guest
Posts: n/a
 
      04-02-2007
On Apr 2, 11:55 am, "Mike Schilling" <(E-Mail Removed)>
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.

 
Reply With Quote
 
 
 
Reply

Thread Tools

Posting Rules
You may not post new threads
You may not post replies
You may not post attachments
You may not edit your posts

BB code is On
Smilies are On
[IMG] code is On
HTML code is Off
Trackbacks are On
Pingbacks are On
Refbacks are Off


Similar Threads
Thread Thread Starter Forum Replies Last Post
Does Java 1.5 have circular linkedlist implementation? Sharp Java 4 07-05-2011 08:00 PM
generic LinkedList and warnings - newbie question R Java 2 05-17-2005 09:24 PM
Question About LinkedList Edward H. Fabrega Java 9 09-30-2004 09:17 PM
LinkedList NullPointerException occurs after switched from IBM JVM 1.4.0 to 1.4.1 Tohru Kao Java 3 07-14-2003 08:12 AM
LinkedList NullPointerException occurs after switched from IBM JVM 1.4.0 to 1.4.1 Tohru Kao Java 1 07-08-2003 09:09 AM



Advertisments