Understanding LinkedList

[Praveen Sharma]

As I understand, java.util.LinkedList class is a doubly linked list. I have two questions in this regard :

1. What is the advantage of a doubly linked list implementation ?
2. What is the underlying data structure used for java.util.LinkedList ?

[Rob Spoor]

In a doubly linked list you can also go backwards, not just forward.

In regards to your second question, in your JDK folder there is a file called src.zip. Inside you will find the source code for most of the API. Unpack it, go to sub folder java\util, and open LinkedList.java.

[Seetharaman Venkatasamy]

Praveen Sharma wrote:2. What is the underlying data structure used for java.util.LinkedList ?

Unlike ArrayList[which uses Array datastrucute, contiguous memory allocation],LinkedList itself is a datastructure. in Java LinkedList implementated as doubly-linkedlist

[Campbell Ritchie]

Seetharaman Venkatasamy is correct; a doubly-linked list is a doubly-linked list. You will find some more useful information here.

[Jesper de Jong]

Praveen Sharma wrote:As I understand, java.util.LinkedList class is a doubly linked list. I have two questions in this regard :

1. What is the advantage of a doubly linked list implementation ?
2. What is the underlying data structure used for java.util.LinkedList ?

The most important difference between the implementations of interface List is that they have different performance characteristics. For example: Accessing an element by index is efficient (O(1)) for an ArrayList, but inefficient (O(n)) for a LinkedList. Inserting an element in the middle of the list is inefficient for an ArrayList, but efficient for a LinkedList.

Whether you should use an ArrayList or a LinkedList depends on what your program does: if it needs to lookup elements by index a lot, an ArrayList is the right choice, and if it needs to insert elements in the list a lot a LinkedList is the right choice.

The API documentation of the different implementations explains it in more detail.

[Praveen Sharma]

Thank you all for this. It was really useful.

[Campbell Ritchie]

A linked list is particularly useful as a Queue; you can easily insert at one end and remove elements from the other end.

[Rene Larsen]

I remember coding a Doubly Linked List back in the early days when I learned Java - and with this Doubly Linked List I made, is it possible to insert in sorted order, and remove stored object from there ID.
I know it was kind of 'not' dynamically made, but it gave me a lot of insight in the functionality of a Doubly Linked List.

Funny little project

[Campbell Ritchie]

Good point, Rene Larsen. If people wrote their own linked lists, etc, they would understand how they work.

[fred rosenberger]

Campbell Ritchie wrote:Good point, Rene Larsen. If people wrote their own linked lists, etc, they would understand how they work.

Catch-22. How can you write one if you don't know how it is supposed to work?

[Campbell Ritchie]

You can always find an example on Google to copy. Or in many of the books; Deitel and Deitel for example shows one how to build a linked list.

[Rene Larsen]

fred rosenberger wrote:

Campbell Ritchie wrote:Good point, Rene Larsen. If people wrote their own linked lists, etc, they would understand how they work.

Catch-22. How can you write one if you don't know how it is supposed to work?

You need to know about the basic behind a Doubly Linked List (e.g. http://en.wikipedia.org/wiki/Doubly-linked_list) - about Nodes are connected to each other by a next and a previous link - then you code how to store a new Node in sorted order, move the links when you insert/delete/move a Node etc.

When you have coded the logic, then you know in detail how a Doubly Linked List works.

[Rene Larsen]

Campbell Ritchie wrote:You can always find an example on Google to copy. Or in many of the books; Deitel and Deitel for example shows one how to build a linked list.

Yeah, I think I have seen the C++ code from their book, where pointers are used.

[fred rosenberger]

and copying code isn't writing it yourself, is it?

(really, i'm just being a pest today...don't take my arguments too seriously)

[Rene Larsen]

fred rosenberger wrote:and copying code isn't writing it yourself, is it?

(really, i'm just being a pest today...don't take my arguments too seriously)

No it is kind of cheating

I can only speak for my self - the C++ book from Deitel and Deitel where the coding of a Linked List (not Doubly Linked) were, was first read much later, because a coworker of mine had bought the "C++ How to Program" book, and he showed it to me.

For the Wikipedia descriptions, this information was not available at that time - I just found some basic descriptions on the web, about what Linked List and Doubly Linked List were.

[Campbell Ritchie]

I don't think copying such code is cheating. No more than copying letters printed in a book onto paper with a pencil when learning to write is cheating. Passing it off as one's own code would be cheating, however.

[Rene Larsen]

Campbell Ritchie wrote:I don't think copying such code is cheating. No more than copying letters printed in a book onto paper with a pencil when learning to write is cheating. Passing it off as one's own code would be cheating, however.

I also meant that it is kind of cheating your self