Logo Questions Linux Laravel Mysql Ubuntu Git Menu
 

Linkedlist implementation in Java doesnot seem like linkedlist as in C++

I was going through the LinkedList and seen the implementation in Java. Back in days when I tried and implemented the linkedlist, it was with pointers and addresses and a lot of hard work. With Java the implementation is easier but still took some doing on my part. What I know of linked list is clear from following diagram,where 1,2,3,4 are nodes of the linkedlist. enter image description here

However In java, the code I came across made me to think of the LinkedList as following diagram.enter image description here

The implementation code of linkedlist in Java is as follows,

class LinkedListNode
{
    LinkedListNode nextNode = null;//consider this member variable
    int data;
    public LinkedListNode(int data)
    {
        this.data = data;
    }
    void appendItemToLinkedList(int newData)
    {
        LinkedListNode end = new LinkedListNode(newData);
        LinkedListNode temp = this;
        while (temp.nextNode != null) { temp = temp.nextNode; }
        temp.nextNode = end;

    }
}

and

public static void main(String[] args) 
    {
        LinkedListNode list = new LinkedListNode(10);
        list.appendItemToLinkedList(20);
        list.appendItemToLinkedList(30);
        list.appendItemToLinkedList(40);
        list.appendItemToLinkedList(50);
        list.appendItemToLinkedList(60);
    }

In the diagram , you can clearly see the node objects are inside the other node objects. Is it really a linked list.Or A parent container holding other container inside it and so on?

like image 269
nobalG Avatar asked Mar 10 '23 02:03

nobalG


2 Answers

The second diagram results from thinking that one list contains another (as it would if the LinkedList type were a primitive type).

The first diagram results when you think about one LinkedList referencing another.

Because LinkedList is a reference type, and not a primitive type, the nextNode field does not store a full LinkedList in-place, but only a reference to one. Therefore, your first diagram is the correct one, even in Java.

See also:

  • This other question, "What's the difference between primitive and reference types?"

  • Java language specification: Chapter 4.1, "Kinds of Types and Values"

like image 133
stakx - no longer contributing Avatar answered Apr 25 '23 07:04

stakx - no longer contributing


The implementations of Linked-List in Java and in C++ are actually pretty similar. The only difference is the natural difference caused by the different language. In both you'll have an entity (class) for LinkedListNode. In both this class will have a field next which will be a reference in Java, or a pointer in C++, to the next node. The insertion method will look the same too. So overall, it's just similar :)

And the diagram that fits this design is of course the first one.

like image 35
SHG Avatar answered Apr 25 '23 07:04

SHG