7

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?

Luchian Grigore
  • 253,575
  • 64
  • 457
  • 625
mak04
  • 73
  • 1
  • 5
  • Read this, and see if it sufficiently addresses your question: http://stackoverflow.com/questions/7480783/pointers-in-java – Dilum Ranatunga Aug 24 '12 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. –  Aug 24 '12 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 Aug 24 '12 at 18:58
  • I haven't done java in years, cheerfully withdrawn! – asawyer Aug 24 '12 at 19:01
  • 1
    @asawyer I haven't done Java *ever* ;) –  Aug 24 '12 at 19:02
  • @delnan all mutable values in python (lists, sets, etc.) are passed by reference. – Dirk Holsopple Aug 24 '12 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 http://stackoverflow.com/a/986145/395760 –  Aug 24 '12 at 19:03

7 Answers7

29

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.

Dirk Holsopple
  • 8,731
  • 1
  • 24
  • 37
  • 2
    +1 I love that explanation for references. It is so quick, easy and accurate, aside from being obvious for C veterans and giving others a reason to learn that aspect of programming. –  Aug 24 '12 at 18:57
5

With other languages, you deal with references which are closely related to pointers.

Daniel A. White
  • 187,200
  • 47
  • 362
  • 445
2

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;
  }
Jake Long
  • 706
  • 3
  • 7
  • 17
  • The last sentence is unfortunate. If we take it as face value, i.e. "`Node` is a value type", it implies your second definition of `Node` is invalid because it is on infinite size. References are not addresses indeed, but they *are* indirections. –  Aug 24 '12 at 19:01
  • I just noticed that your second example is invalid even ignoring the now removed explanation. (If it's supposed to be C++ that is.) –  Aug 24 '12 at 19:13
  • It was simply supposed to be a visualization in pseudocode. The Struct just came from his background in C++ – Jake Long Aug 24 '12 at 19:16
1

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.

Thomas Matthews
  • 56,849
  • 17
  • 98
  • 154
  • 1
    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. –  Aug 24 '12 at 19:12
  • 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. – Thomas Matthews Aug 25 '12 at 01:56
0

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)

La bla bla
  • 8,558
  • 13
  • 60
  • 109
0

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.

jimf
  • 4,527
  • 1
  • 16
  • 21
0

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.

Luis Perez
  • 27,650
  • 10
  • 79
  • 80