LinkedList Implementation question

Discussion in 'Java' started by H., Apr 2, 2007.

  1. H.

    H. Guest

    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?
    H., Apr 2, 2007
    #1
    1. Advertising

  2. Why not a "deque"?
    --
    Regards,
    Casey
    Casey Hawthorne, Apr 2, 2007
    #2
    1. Advertising

  3. H.

    Karl Uppiano Guest

    "H." <> wrote in message
    news:...
    >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, Apr 2, 2007
    #3
  4. H.

    Lew Guest

    Karl Uppiano wrote:
    > "H." <> wrote in message
    > news:...
    >> 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
    Lew, Apr 2, 2007
    #4
  5. 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).
    Mike Schilling, Apr 2, 2007
    #5
  6. On Apr 2, 11:55 am, "Mike Schilling" <>
    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.
    Muntasir Azam Khan, Apr 2, 2007
    #6
    1. Advertising

Want to reply to this thread or ask your own question?

It takes just 2 minutes to sign up (and it's free!). Just click the sign up button to choose a username and then you can ask your own questions on the forum.
Similar Threads
  1. Tohru Kao
    Replies:
    3
    Views:
    420
    Neil Masson
    Jul 14, 2003
  2. Tohru Kao
    Replies:
    1
    Views:
    380
    Chris
    Jul 8, 2003
  3. Edward H. Fabrega

    Question About LinkedList

    Edward H. Fabrega, Sep 22, 2004, in forum: Java
    Replies:
    9
    Views:
    453
    Edward H. Fabrega
    Sep 30, 2004
  4. Sharp
    Replies:
    4
    Views:
    14,238
    tennenrishin
    Jul 5, 2011
  5. R
    Replies:
    2
    Views:
    3,535
    Tony Morris
    May 17, 2005
Loading...

Share This Page