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.
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.
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.
author and iconoclast
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.
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.
Joined: Oct 07, 2004
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.....
Joined: Dec 16, 2004
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...
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 as a node, it would be simpler to use Object, 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.
Joined: Dec 16, 2004
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...
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).
author and iconoclast
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.