It is easy to implement linked list in c++ where you have pointers. But how are they implemented in other languages (like java,python,etc). I don't want to use built-in class(which are supported in JAVA) for linked-list but what i want is how to replace pointers to create linked-list?
-
Read this, and see if it sufficiently addresses your question: stackoverflow.com/questions/7480783/pointers-in-javaDilum Ranatunga– Dilum Ranatunga2012-08-24 18:56:01 +00:00Commented Aug 24, 2012 at 18:56
-
2@asawyer Nothing is passed by reference in Python and Java. Neither in many other languages that use references in the same sense.user395760– user3957602012-08-24 18:56:38 +00:00Commented Aug 24, 2012 at 18:56
-
1@asawyer: agree with delnan. Java is pass by value. Always. That value may be a reference, but a value is what is passed.Hovercraft Full Of Eels– Hovercraft Full Of Eels2012-08-24 18:58:57 +00:00Commented Aug 24, 2012 at 18:58
-
1@asawyer I haven't done Java ever ;)user395760– user3957602012-08-24 19:02:19 +00:00Commented Aug 24, 2012 at 19:02
-
3@DirkHolsopple They are not. All values (mutable and immutable -- stop making a distinction up folks) are reference types, but parameter passing is never pass by reference (edit: confusing typo). Both are technical terms with very specific, and distinct, meaning. Also see stackoverflow.com/a/986145/395760user395760– user3957602012-08-24 19:03:59 +00:00Commented Aug 24, 2012 at 19:03
|
Show 2 more comments
8 Answers
They are implemented using references which are essentially (excluding syntax) pointers that you can't do pointer arithmetic with (in some languages they also can't be null). In many languages, references are the default way of using variables, unlike C++ where the default is by-value.
With other languages, you deal with references which are closely related to pointers.
Comments
Instead of pointers that point to a block of memory, references are used, as stated before. So like you would have in C++
Struct Node {
Node *last;
Node *next;
}
it would look like this:
Struct Node {
Node last;
Node next;
}
3 Comments
Jake Long
It was simply supposed to be a visualization in pseudocode. The Struct just came from his background in C++
A good data structures class will show you that a linked list can be implemented in any language using arrays, such as FORTRAN.
Instead of using pointers, you would use some other means to locate the next link. With arrays, instead of a pointer you would use an index to the next element.
Thus you could implement a linked list in a random-access file by using the file position instead of pointers.
answered Aug 24, 2012 at 19:09
Thomas Matthews
58.1k18 gold badges106 silver badges165 bronze badges
2 Comments
I'm not sure if this counts as linked list. It definitely has different characteristics from the pointer-based implementation, in that it is more limited. Apart from that, this is entirely beside the point because you can build "regular" linked lists (and all other data structures relying on indirection) with references.
Thomas Matthews
It is a list, and it is linked. It doesn't use pointers to link the nodes. It is a different implementation of a linked list. I was taught this in my Data Structures class at the University.
When you write your own class, say class node, and have each node hold a field to the next node, You actually hold a reference to that next node (or null if it's the last one)
Comments
You may find a good answer in this book - http://www.amazon.com/Introduction-Algorithms-Thomas-H-Cormen/dp/0262033844 - I'll summarize what I recall for you.
Basically you'll have two arrays of equal size (hopefully larger than n where n=number of elements you want to store). We'll call them Array A and Array B.
Array A[i] holds the data value. Array B[i] holds the 'next' value 'k' such that A[i]->next = A[k].
Hopefully this helps.
Remember the concept of a linked list is that you can get from one element to another. How you do it can be very different.
In C++ for example you mentioned you can use pointers. Which said another way would be that you use the objects memory address.
But that's just one way. If all your objects were referenced from an array, then you would be able to reference an object by it's index on that array. So each element in your linked list would have a integer specifying the index of the object it's connected to.
To give you another example. If you had a dictionary where you associated objects with strings. Then you could use strings to reference each other.
The core concept to linked lists is not pointers, it's that the elements in the list are responsible to keep track of the element it's connected to.
Comments
DISCLAIMER : this is my assumption. I might be wrong. If I am wrong, please correct me
Example Program (Primitive Data Type)
Creating a new space for int and store a value (int a = 5)
(int b = a) this code represents the (int b) as a new space and the value of (int a) is passed.
Example Program (User Define Data Type)
Creating a new space for class (Solution obj= new Solution();)
In this code, the (Solution = DataType), (obj = variable), (Solution()=default constructor)
The new keyword helps to create new space for a default constructor (which means the default constructor contains the class member of datatypes and methods) The way to create a new space for class (only by using the new keyword)
Solution obj = new Solution();
Solution ref = obj;
See the difference between Class and Primitive Data Type. The new space was not created for the Solution ref class, because we didn't use the new keyword and constructor. So the ref just hold the obj references, but in Primitive Data Type (int b) we don't need a new keyword to create a space.
