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

Question

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.

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

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?

I believe you are thinking about this incorrectly. A Java linked list, under the hood, likey uses pointers much in the same way C does. — Tim Biegeleisen, May 12 '17 at 07:25
you are working with references. the `LinkedListNode` holds a reference to the next `LinkedListNode` node, not its value. — Andrew Tobilko, May 12 '17 at 07:26
Java, C and C++ are different languages. `LinkedListNode` is a reference type in Java, so each node stores a reference to the next (which works similarly to how a pointer would work in C or C++) — UnholySheep, May 12 '17 at 07:26
The concept of a linked list is: *a node references its neighbor*. This concept is the same in Java, C++ or any other language. — Timothy Truckle, May 12 '17 at 07:29
Seems you need to reread the Java guide to learn what a *reference* is. It is very similar to a C pointer; it is just implicit. — Andreas, May 12 '17 at 07:30

score 6 · Accepted Answer · edited May 23 '17 at 10:31

6

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"

edited May 23 '17 at 10:31

Community

1
1

answered May 12 '17 at 07:28

stakx - no longer contributing

83,039
20
168
268

1

Because of OP comparing C/C++ against Java, minor refinement: Java does not differentiate between objects/values and pointers to objects (which Java references actually are) *explicitly*, but does so *implicitly* (transparently) depending on to the underlying type (see link provided). – Aconcagua May 12 '17 at 07:40

SHG · Answer 2 · 2017-05-12T07:50:27.107

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.

score 0 · Answer 3 · answered May 12 '17 at 07:43

0

LinkedList in Java is implemented as a double LikedList thus it's not a primitive type as is the case in C++. FYI - From Stock's (Doctor Deprecator) talk in JavaOne 2016, java plans to drop support for LinkedLists, Vectors and some other data structure for unique reasons. Hence the confusion and the technical difference that might exist.

answered May 12 '17 at 07:43

Samuel Owino

747
1
12
24

1

The OP is talking about manual implementation of Linked-List, in Java comparing to C++. Not about Java's ready-to-use linked-list. – SHG May 12 '17 at 07:47
Also a `std::list` is not a "primitive" type (C++ doesn't use that terminology either), it's a template class. In C++ classes are user-defined types (just like in Java, except in Java all classes are reference types while C++ does not have this requirement) – UnholySheep May 12 '17 at 07:53
I agree, you are right only my suggestion would be not to be alarmed about the underlying definition of LinkedList in java since the plans to drop support and encourage use of other data structures in the Collections Framework in java – Samuel Owino May 12 '17 at 07:58

Himanshu Panchal · Answer 4 · 2020-02-17T12:10:25.897

Linked list in C++ above

THE MAIN DIFFERENCE IS THAT IN JAVA, THE HEAD IS NOT JUST A POINTER(without data) pointing to the first element. Even head has both data and the pointer to second element(ONLY EXCEPT THE CASE WHERE LIST IS EMPTY). In short every element in the linked list in java has 2 pointers and data, except head which has a pointer to next element and its data. I am not sure about the last element though.

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

4 Answers4