Sign up ×

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?

share|improve this question
Read this, and see if it sufficiently addresses your question: – Dilum Ranatunga Aug 24 '12 at 18:56
@asawyer Nothing is passed by reference in Python and Java. Neither in many other languages that use references in the same sense. – delnan Aug 24 '12 at 18:56
@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
@asawyer I haven't done Java ever ;) – delnan Aug 24 '12 at 19:02
@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 – delnan Aug 24 '12 at 19:03

6 Answers 6

up vote 23 down vote accepted

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.

share|improve this answer
+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. – delnan Aug 24 '12 at 18:57

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

share|improve this answer

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;
share|improve this answer
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. – delnan 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.) – delnan 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

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)

share|improve this answer

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.

share|improve this answer
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. – delnan 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 1:56

You may find a good answer in this book - - 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.

share|improve this answer
See my comment on Thomas Matthew's answer. – delnan Aug 24 '12 at 19:14

Your Answer


