• Post Reply Bookmark Topic Watch Topic
  • New Topic
programming forums Java Mobile Certification Databases Caching Books Engineering Micro Controllers OS Languages Paradigms IDEs Build Tools Frameworks Application Servers Open Source This Site Careers Other Pie Elite all forums
this forum made possible by our volunteer staff, including ...
Marshals:
  • Campbell Ritchie
  • Jeanne Boyarsky
  • Ron McLeod
  • Paul Clapham
  • Liutauras Vilda
Sheriffs:
  • paul wheaton
  • Rob Spoor
  • Devaka Cooray
Saloon Keepers:
  • Stephan van Hulst
  • Tim Holloway
  • Carey Brown
  • Frits Walraven
  • Tim Moores
Bartenders:
  • Mikalai Zaikin

Understanding LinkedList

 
Ranch Hand
Posts: 129
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
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 ?
 
Sheriff
Posts: 22787
131
Eclipse IDE Spring Chrome Java Windows
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
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.
 
Ranch Hand
Posts: 5575
Eclipse IDE Windows XP Java
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator

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
 
Marshal
Posts: 79467
379
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
Seetharaman Venkatasamy is correct; a doubly-linked list is a doubly-linked list. You will find some more useful information here.
 
Java Cowboy
Posts: 16084
88
Android Scala IntelliJ IDE Spring Java
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator

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
Ranch Hand
Posts: 129
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
Thank you all for this. It was really useful.
 
Campbell Ritchie
Marshal
Posts: 79467
379
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
A linked list is particularly useful as a Queue; you can easily insert at one end and remove elements from the other end.
 
Ranch Hand
Posts: 1179
Mac OS X Eclipse IDE
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
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
Marshal
Posts: 79467
379
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
Good point, Rene Larsen. If people wrote their own linked lists, etc, they would understand how they work.
 
lowercase baba
Posts: 13091
67
Chrome Java Linux
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator

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
Marshal
Posts: 79467
379
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
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
Ranch Hand
Posts: 1179
Mac OS X Eclipse IDE
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator

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
Ranch Hand
Posts: 1179
Mac OS X Eclipse IDE
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator

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
lowercase baba
Posts: 13091
67
Chrome Java Linux
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
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
Ranch Hand
Posts: 1179
Mac OS X Eclipse IDE
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator

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
Marshal
Posts: 79467
379
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
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
Ranch Hand
Posts: 1179
Mac OS X Eclipse IDE
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator

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
 
I was born with webbed fish toes. This tiny ad is my only friend:
a bit of art, as a gift, the permaculture playing cards
https://gardener-gift.com
reply
    Bookmark Topic Watch Topic
  • New Topic