wood burning stoves 2.0*
The moose likes Beginning Java and the fly likes LINK LIST IN JAVA WITHOUT COLLECTION FRAMEWORK Big Moose Saloon
  Search | Java FAQ | Recent Topics | Flagged Topics | Hot Topics | Zero Replies
Register / Login
JavaRanch » Java Forums » Java » Beginning Java
Bookmark "LINK LIST IN JAVA WITHOUT COLLECTION FRAMEWORK" Watch "LINK LIST IN JAVA WITHOUT COLLECTION FRAMEWORK" New topic
Author

LINK LIST IN JAVA WITHOUT COLLECTION FRAMEWORK

mohan gavande
Ranch Hand

Joined: Oct 07, 2004
Posts: 39
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

Joined: Jul 08, 2003
Posts: 24183
    
  34

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.


[Jess in Action][AskingGoodQuestions]
sarada konda
Greenhorn

Joined: Dec 10, 2004
Posts: 7
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

Joined: Aug 20, 2001
Posts: 1817

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 ]

Piscis Babelis est parvus, flavus, et hiridicus, et est probabiliter insolitissima raritas in toto mundo.
Joel McNary
Bartender

Joined: Aug 20, 2001
Posts: 1817

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

Joined: Jul 08, 2003
Posts: 24183
    
  34

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

Joined: Dec 06, 2001
Posts: 3061
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


Java API Documentation
The Java Tutorial
mohan gavande
Ranch Hand

Joined: Oct 07, 2004
Posts: 39
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

Joined: Dec 16, 2004
Posts: 12
What do you mean by memory allocation ? Are you thinking of something like C-Style malloc()? This would not be necessary in Java...


inside every large program there is a small program struggling to get out...
Ernest Friedman-Hill
author and iconoclast
Marshal

Joined: Jul 08, 2003
Posts: 24183
    
  34

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

Joined: Oct 07, 2004
Posts: 39
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

Joined: Dec 16, 2004
Posts: 12
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

Joined: Nov 01, 2004
Posts: 11
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

Joined: Dec 16, 2004
Posts: 12
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

Joined: Aug 20, 2001
Posts: 1817

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

Joined: Jul 08, 2003
Posts: 24183
    
  34

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

Joined: Aug 07, 2003
Posts: 1646
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

Joined: Dec 16, 2004
Posts: 12
I do also apologize for my fast judgement, this list really not bounded. But the implementation is quite unusual...
mohan gavande
Ranch Hand

Joined: Oct 07, 2004
Posts: 39
Thanks to everybody I now clearly understand how the link list creates
 
jQuery in Action, 2nd edition
 
subject: LINK LIST IN JAVA WITHOUT COLLECTION FRAMEWORK
 
Similar Threads
How do I get an object in an arraylist of certain value without loping it
Tricky questions in collection?
Collections Framework
Any Link Between ArrayList and HashMap
Data structure text