• Post Reply
  • Bookmark Topic Watch Topic
  • New Topic

LINK LIST IN JAVA WITHOUT COLLECTION FRAMEWORK

 
mohan gavande
Ranch Hand
Posts: 39
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
I have one query regarding JAVA Data Structure. If Java support data structure then how it make link list without using collection framework.
Plase Reply this mail.

Thanking in Advance.......

 
Ernest Friedman-Hill
author and iconoclast
Marshal
Pie
Posts: 24212
35
Chrome Eclipse IDE Mac OS X
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Not sure what you're asking, exactly. Do you have a homework assignment to write a linked list class? If so, start by making a list of the fundamental operations a linked list type should have, and then create a class with methods to represent those operations.
 
sarada konda
Greenhorn
Posts: 7
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Below is the program for creating and printing linkedlist without using java collection framework



[JAM -- edited to have [CODE] and [/CODE] tags]
[ December 14, 2004: Message edited by: Joel McNary ]
 
Joel McNary
Bartender
Posts: 1840
Eclipse IDE Java Ruby
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Not to be critical...[critic's comments removed]. I'm not sure what I'd call that data structure, but I wouldn't call it a linked list. It looks more like it's a pseudo-linked list, where it is limited by the size of the array.

Generally, a linked list consists of two classes: the list class and the node class. The node has a reference to the Object that the node is "holding" and to the next node in the list (and to the previous node, if it's a doubly-linked list). The list contains a reference to the first node in the list, the number of elements in the list (usually), and has all of the standard "list" methods: add, get, remove, size, etc. If you're being really slick, the list can also maintain a reference to the last node in the list and one to the "current" node. Maintaing a reference to the "current" node makes iterating through the list much more efficient. (And it can even make random-access somewhat more efficient, too, as you can calculate the shortest path to the requested element from the start, current, and end nodes.)
[ December 14, 2004: Message edited by: Joel McNary ]
 
Joel McNary
Bartender
Posts: 1840
Eclipse IDE Java Ruby
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
OK, upon further review, I think that that data structure does qualify as a linked list -- however, it does demonstrate why you should create classes instead of just using arrays of values. Proper naming of items would clarify items and make the code much more readable.
 
Ernest Friedman-Hill
author and iconoclast
Marshal
Pie
Posts: 24212
35
Chrome Eclipse IDE Mac OS X
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
This is the way people used to write linked lists in FORTRAN. As Joel says (nicely), it's not a good example of Java style -- don't copy it.
 
Layne Lund
Ranch Hand
Posts: 3061
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
So I think we are back to Ernest's original comment: can you please clarify your question? What exactly are you trying to do? Is this a homework assignment? If so, can you post the requirements for it? Also, what have you done so far on your own? Posting any code you've written and explaining how it does (or does not) work correctly will help a lot in helping us help you.

Keep Coding!

Layne
 
mohan gavande
Ranch Hand
Posts: 39
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Hi Agains Thanks for replaying.
But I am confused about your comments please specify how
memory allocation is working in this program??

& Also if as per Ernest Friedman-Hill told that this is not perfect
then Please specify which program is perfect. Please reply example with
how memory allocation is working for that program

Thanks Once Again....


 
Thomas Manthey
Greenhorn
Posts: 12
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
What do you mean by memory allocation ? Are you thinking of something like C-Style malloc()? This would not be necessary in Java...
 
Ernest Friedman-Hill
author and iconoclast
Marshal
Pie
Posts: 24212
35
Chrome Eclipse IDE Mac OS X
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Originally posted by mohan gavande:
Please specify which program is perfect.


In a "perfect" (or at least, typical) Java linked-list implementation, each link is an instance of a "Link" class, something like



Each Link contains a reference to another Link object. No arrays are used or needed.

But in the rather unusual program proposed above, there's a big array that holds a bunch of littler arrays, and the littler arrays hold references to each other, and there's lots of casting and other ugliness. Also, by using a big array, this program places a limit on the size of the linked list; one nice feature of a "real" Java linked list is that its size is unbounded.

Make sense?
 
mohan gavande
Ranch Hand
Posts: 39
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Thank You Ernest Friedman-Hill .
I will test that code & reply here if any difficulty found.
But I still not clear how memory is alocated for this opration
Is it allocated like C, C++ or else way
Try to think on my question.....
 
Thomas Manthey
Greenhorn
Posts: 12
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Hello Mohan,

it�s like I said in my above post: you do not need to allocate memory manually. If you call something like this: , the VM allocates the needed memory for your object automatically...
 
Dhar Desai
Greenhorn
Posts: 11
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Actually, I don't think the Saroda's linked list is bounded. The node is a multi-dimensional array with one row and two columns. The first cell contains the data and the second cell contains a reference to the next node.

Instead of using Object[1][2] as a node, it would be simpler to use Object[2], which is essentially the same thing.

It would be even simpler to use a class with two instance variables, one for the data and the other for the next node, as suggested by another poster.
 
Thomas Manthey
Greenhorn
Posts: 12
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
If it is an array, then it is bounded. Array in Java are semi-dynamic, ie their size is set at runtime and then immutable. A linked list can always change its size...
 
Joel McNary
Bartender
Posts: 1840
Eclipse IDE Java Ruby
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
The posted code is not bounded -- that's the confusion that caused my original comment that said that it wasn't really a LinkedList. However, I looked closer and saw that it was unbounded -- although there was no need for the 2D-array (note that array[>1] is never accessed).

For the second dimension, the first position in the array contains the reference to the data element at that position. The second position contains a reference to the next node.

There's no big array. The first element created doen't contain all the nodes; it is rather the first node of the list.

As I think we agree, not a true OO-implementation of a Linked List, but it does qualify for membership in that class of data structure. (An OO implementation would be as Ernest and I described above).
 
Ernest Friedman-Hill
author and iconoclast
Marshal
Pie
Posts: 24212
35
Chrome Eclipse IDE Mac OS X
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Yes, sorry, I glanced too quickly at the original code. It's not really a classic FORTRAN-style linked-list. It's more like the sort of "I'm so clever I can write my own memory manager in FORTRAN" linked list that appears often in scientific computing libraries.

There's no need to use an Object array to simulate a Link object -- it's better in every way to create a real Link class.
 
David Harkness
Ranch Hand
Posts: 1646
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Originally posted by Ernest Friedman-Hill:
There's no need to use an Object array to simulate a Link object -- it's better in every way to create a real Link class.
Tsk tsk! As everyone knows, all generalizations are bad.
 
Thomas Manthey
Greenhorn
Posts: 12
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
I do also apologize for my fast judgement, this list really not bounded. But the implementation is quite unusual...
 
mohan gavande
Ranch Hand
Posts: 39
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Thanks to everybody I now clearly understand how the link list creates
 
  • Post Reply
  • Bookmark Topic Watch Topic
  • New Topic