LINK LIST IN JAVA WITHOUT COLLECTION FRAMEWORK

[mohan gavande]

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]

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]

Below is the program for creating and printing linkedlist without using java collection framework

class TestLinkedList 
{
public static void main(String[] args) 
{

int[] data = { 10,20,30,15,40,66};
Object[][] linkedList = new Object[1][2];
createLinkedList(data,linkedList);
printLinkedList(linkedList);

}

public static void createLinkedList(int []data,Object[][] linkedList)
{
Object node[][] = null;
Object newnode[][] = null;
node=new Object[1][2];
linkedList[0][1]=node;
for(int i=0;i<data.length;i++)
{
node[0][0]=new Integer(data[i]);
newnode=new Object[1][2];
node[0][1]=newnode;
node=newnode;

}
node =null;
newnode = null;
    }


public static void printLinkedList(Object[][] linkedList)
{

Object node[][] = null;
node=linkedList;
node =(Object [][]) node[0][1];
while(node[0][1]!= null)
{
System.out.print("  "+node[0][0]+" --->" );
node=(Object [][]) node[0][1];

}
System.out.print("null" );

}
}

[JAM -- edited to have [CODE] and [/CODE] tags]
[ December 14, 2004: Message edited by: Joel McNary ]

[Joel McNary]

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]

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]

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]

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]

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]

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]

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

class Link {
  Link next;
  Object data;
  // Also methods, of course
}

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]

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]

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:

Object foo=new Object();

, the VM allocates the needed memory for your object automatically...

[Dhar Desai]

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]

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]

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]

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]

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]

I do also apologize for my fast judgement, this list really not bounded. But the implementation is quite unusual...

[mohan gavande]

Thanks to everybody I now clearly understand how the link list creates