0

A basic implementation of linked list in java is:

class Node{
   int element;
   Node next;
 ......
}

What I do not understand is how does an object of the class declared within the class itself is able to store the address of another data member. Doesn't declaring Node next enable next itself to have an element part and then again a next. This would happen indefinitely, right? So, how does it work?

Uncaught Exception
  • 2,149
  • 18
  • 25
VisnuGanth
  • 71
  • 1
  • 9
  • Node predefined java class which contain data and link . refer this link to get linkedList example there you will get clear about this. http://www.mycstutorials.com/articles/data_structures/linkedlists – Abdul Rizwan Sep 25 '16 at 07:56
  • @AbdulRizwan: Pls remove the above link as mycstutorials has been permanently shut down. It would be great if you can write from memory what you wanted the OP to read from the link. – Uncaught Exception Dec 25 '17 at 06:52

2 Answers2

1

Doesn't declaring Node next enable next itself to have an element part and then again a next. This would happen indefinitely, right?

Thus is the power of this data structure. You add to it indefinitely without having to resize like in a static array.

If you are wondering, how you would end the list? Set Node next to be null and viola! You have your end node.

Node within a Node? I may be wrong, but Java is able to reference a class instance within the same class because every object is basically a pointer which it knows the size of.

C++ equivalent

class A {
    A *a;
}
donkon
  • 909
  • 9
  • 23
  • 1
    I think his issue was rather misinterpreting `Node next` as recursively embedding Node within itself, similar to C/C++, rather than declaring a reference to another Node object. – Smith_61 Sep 25 '16 at 05:39
  • Updated, and another similar discussion http://stackoverflow.com/questions/4941629/why-cant-we-declare-object-of-a-class-inside-the-same-class – donkon Sep 25 '16 at 05:47
1

In Java:

1) when we declare a variable of a class type, only a reference is created i.e. memory is not allocated for the object. To allocate memory to an object, we use new().

2) when assigning one object to another, only the reference gets assigned. It does NOT copy member variables.

So, in Linked Lists, we link two nodes by assigning the reference of the following node to the current node's "next" field. Though unrelated, but I guess it's important to realise that when compared to an array, a linked list does need extra memory to store pointer variables.

Uncaught Exception
  • 2,149
  • 18
  • 25