If you are asking whether (and why) you need to create Node instances to use a java.util.LinkedList, the answer is: No you don't. The list itself takes care of that.
(Note that the Node class that you linked to is not a linked list node. It actually denotes a node in an DOM. The actual Node class used internally by java.util.LinkedList is a private class.)
If you were asking why linked lists in general require a Node type, the answer is that they don't.
The other way of creating a linked list (that doesn't involve a Node type) is to directly chain the elements of a list to each other. This has a couple of consequences:
This requires the element class itself to have a
nextfield (and possibly aprevfield) for chaining the elements.It means that a given element instance can only be a member of one list at a time, and can't be a member of the same list twice.
Together, these mean that the nodeless approach is incompatible with the standard java.util.List API.
The nodeless approach is also bad from the OO design perspective:
- By the adding
nextandprevfields to the element type, you are breaking down abstraction boundaries and the separation of concerns. - The element instance now knows about the list that the element is part of.
- The list abstraction only works for certain types of element, and has to take account of which list an element is a member of.
These things are liable to make the nodeless list abstraction harder to use ... and less reusable. (Though in limited circumstances, it may still be a good solution.)
Answer from Stephen C on Stack OverflowUnderstanding Singly Linked Lists (JAVA)
linked list - Why do I need the Node class in Java for LinkedList? - Stack Overflow
Can someone ELI5? Linked Lists in Java.
Understanding the linked list front node.
Hey guys I'm having trouble understanding Linked Lists. I have tried to follow along with multiple tutorials but everyone has done this in slightly different ways leading only to more confusion on my end. This is the first data structure I have manually had to build and I'm having trouble understanding exactly how it works.
I know there are two parts to every Node. The Node stores some kind of value, then points to the next node and connects them. I understand conceptually what is happening, but the code to make this happen is confusing to me. Would appreciate any help I could get.
From the code below my questions are:
-
What value does head.next now hold after it has been assigned to nodeB ? (or does it just reference?)
-
Or does it just connect Node Objects?
-
How does .next connect these two Node Objects exactly?
class Node
{
int data; // data to store in Node
Node next; // automatically set to null
Node(int givenData) // constructor
{
this.data = givenData;
}
}
public class NodeTest {
public static void main(String[] args)
{
Node head = new Node(6);
Node nodeB = new Node(3);
Node nodeC = new Node(69);
head.next = nodeB;
nodeB.next = nodeC;
}
// Node counting Method kind of irrelevant to questions, but maybe helpful to giving more of an explaination.
static int countNodes(Node head)
{
int count = 1;
Node current = head;
while(current.next != null)
{
current = current.next;
count += 1;
}
return count;
}
}If you are asking whether (and why) you need to create Node instances to use a java.util.LinkedList, the answer is: No you don't. The list itself takes care of that.
(Note that the Node class that you linked to is not a linked list node. It actually denotes a node in an DOM. The actual Node class used internally by java.util.LinkedList is a private class.)
If you were asking why linked lists in general require a Node type, the answer is that they don't.
The other way of creating a linked list (that doesn't involve a Node type) is to directly chain the elements of a list to each other. This has a couple of consequences:
This requires the element class itself to have a
nextfield (and possibly aprevfield) for chaining the elements.It means that a given element instance can only be a member of one list at a time, and can't be a member of the same list twice.
Together, these mean that the nodeless approach is incompatible with the standard java.util.List API.
The nodeless approach is also bad from the OO design perspective:
- By the adding
nextandprevfields to the element type, you are breaking down abstraction boundaries and the separation of concerns. - The element instance now knows about the list that the element is part of.
- The list abstraction only works for certain types of element, and has to take account of which list an element is a member of.
These things are liable to make the nodeless list abstraction harder to use ... and less reusable. (Though in limited circumstances, it may still be a good solution.)
You donโt technically necessarily need a node class, but the design with a node class is the good design. The design without one is the poor design.
This answer is slightly opinionated, but based on what we should all have learned in the first or at least the second year of programming, so consensus-based.
Say that we have a list of students. Itโs now the natural responsibility of each Student object to have (โknowโ) the studentโs contact information, courses enrolled in, grades taken, etc. It is not the natural responsibility of a Student object to know that it is part of a linked list, not to mention whether that list is singly or doubly linked. For this responsibility we have the Node class.
The design with the Node class has the further potential advantage that you can design and code a generic linked list and use it to instantiate a list of students, a list of teachers, a list of courses, etc. Stephen C in the other answer mentions further advantages.
Historical background: Where I learned data structures around 1980, we would fit each student record with a next pointer. (We learned singly linked lists. Doubly linked lists were only mentioned in passing.) What is nowadays considered the poor design. I had hoped that it had long gone out of use.
Performance (skip this paragraph until you really need it :-) : The poor design with next and previous references within the business objects like Student will typically perform slightly better. So if you are in a situation where performance is a Very Real Issue, you may consider it. It is no low-hanging fruit since it pollutes your design, so it will probably come near the bottom of your list of measures to take for better performance.