4

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?

7
  • 4
    What is the question? Commented May 12, 2017 at 7:24
  • 1
    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. Commented May 12, 2017 at 7:25
  • 2
    Does a Java linked list have a tootsie roll at the center? Commented May 12, 2017 at 7:26
  • you are working with references. the LinkedListNode holds a reference to the next LinkedListNode node, not its value. Commented May 12, 2017 at 7:26
  • 2
    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++) Commented May 12, 2017 at 7:26

4 Answers 4

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:

Sign up to request clarification or add additional context in comments.

1 Comment

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).
1

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.

Comments

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.

3 Comments

The OP is talking about​ manual implementation of Linked-List, in Java comparing to C++. Not about Java's ready-to-use linked-list.
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)
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
0

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.

Comments

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.