Linked List in Java
Subject: Data Structures and Algorithms · Language: Java · Level: intermediate · 6 min read
Build linked list logic using Node class, head reference, insertion, traversal, and Java LinkedList idea.
A linked list is a linear data structure made of nodes. Each node stores data and a reference to the next node. Together, these references form a chain.
Unlike arrays, linked list nodes are not required to be stored side by side in memory. Every node knows where the next node is located through its `next` reference. Linked lists are important in DSA because they teach how references work. They are also the base idea behind stacks, queues, adjacency lists, and many custom data structures.
Array vs Linked List
An array stores elements in continuous memory and allows fast access by index. A linked list does not provide direct index access because we must start from the head and move node by node. However, linked lists can make insertion and deletion easier when we already have the correct node reference. This is why linked lists are useful for learning dynamic memory-style structures.
Types of Linked List
A singly linked list is the basic type of linked list. Each node stores data and one `next` reference, which points to the next node. Traversal normally moves in one direction from head to last node.
A doubly linked list stores two references in each node: `prev` and `next`. Because of this, we can move both backward and forward. It needs extra memory, but deletion can be easier when the node reference is already available.
A circular linked list connects the last node back to the first node instead of ending with `null`. Circular linked lists are useful in round-robin scheduling, repeated turns, and problems where movement should continue in a cycle. Beginners should first master singly linked list because it teaches the core idea of nodes and references. After that, doubly and circular linked lists become easier to understand.
Node Class
In Java, a node is usually represented using a class. A node has two parts: data and reference to the next node.
```java
class Node {
int data;
Node next;
Node(int data) {
this.data = data;
this.next = null;
}
}
``` `data` stores the value. `next` stores the reference of the next node. If `next` is `null`, it means there is no node after the current node.
Head Reference
`head` stores the first node of the linked list. If `head` is `null`, the list is empty. The head is important because traversal starts from it. If we lose the head reference, we lose access to the whole list.
When inserting at the beginning, the new node becomes the new head. When inserting at the end, we move to the last node and connect the new node there.
Tail Reference
`tail` is an optional reference that stores the last node of the linked list. A linked list can work without a tail, but keeping a tail can make insertion at the end faster. If only `head` is available, inserting at the end requires traversal from the first node to the last node. If `tail` is maintained correctly, the new node can be connected directly after the current tail.
Inserting at the Beginning
To insert a node at the beginning, first point the new node to the current head, then update head to the new node.
```java
Node newNode = new Node(5);
newNode.next = head;
head = newNode;
```
This operation is fast because we do not need to travel through the whole list.
Inserting at the End
To insert at the end, we start from head and move until we reach the last node. The last node is the node whose `next` is `null`. After finding the last node, we connect it to the new node.
```java
Node current = head;
while (current.next != null) {
current = current.next;
}
current.next = new Node(40);
```
Deleting a Node
Deleting a node means changing references so that the unwanted node is skipped by the list. To delete the first node, move `head` to `head.next`. To delete a middle node, find the node before it and connect that previous node to the node after it.
```java
head = head.next;
```
In linked lists, deletion does not mean shifting all elements like an array. The main work is to update references carefully so the remaining nodes stay connected.
Traversal
Traversal means moving from the head node to the last node one by one. We use a temporary reference, commonly named `current`, so that the original `head` is not lost. The statement `current = current.next` moves the reference from the current node to the next node.
```java
public class Main {
static class Node {
int data;
Node next;
Node(int data) {
this.data = data;
}
} static void printList(Node head) {
Node current = head;
while (current != null) {
System.out.print(current.data + " -> ");
current = current.next;
}
System.out.println("null");
} public static void main(String[] args) {
Node head = new Node(10);
head.next = new Node(20);
head.next.next = new Node(30);
printList(head);
}
}
``` This program manually creates three nodes and connects them. The `printList` method starts from `head` and prints every node until `current` becomes `null`.
Common Linked List Operations
- Traversal: visit every node one by one
- Insertion: add a new node at the beginning, end, or middle
- Deletion: remove a node by changing references
- Searching: check whether a value exists in any node
- Reversal: change links so the list direction becomes opposite
In linked list problems, most work is done by carefully changing references. A small reference mistake can disconnect part of the list, so the order of steps matters.
Java LinkedList Collection
Java also provides `LinkedList` in `java.util`. It is useful in real code because it already implements many list and queue operations. However, for DSA learning, first understand how nodes and references work internally. Interview questions often ask you to build or modify linked lists manually, not only use the built-in collection.
Practice Question
Create a linked list with three nodes and print the sum of all node values. Then add one node at the beginning and print the updated list.