A linked list is a dynamic data structure in which each element (node) contains two parts: data and a reference to the next node in the sequence. In Java, although we have a built-in LinkedList class, it’s useful to understand how to manually implement a linked list to strengthen your grasp of data structures and algorithms. In this post, we'll walk through the implementation of a singly linked list in Java.
By the end of this tutorial, you will understand:
- The structure of a singly linked list
- How to create a linked list from scratch
- How to add, display, and remove elements
1. Understanding the Linked List Structure
A singly linked list consists of nodes where each node has two fields:
- data: The value of the node.
- next: A reference to the next node in the list.
Example of a Node class:
class Node {
int data;
Node next;
// Constructor to initialize the node
public Node(int data) {
this.data = data;
this.next = null; // Next pointer is initially null
}
}
Here, the Node class has:
datato hold the value of the node.nextto point to the next node (ornullif it’s the last node).
2. Creating a Linked List
To create a linked list, we need a class LinkedList that holds a reference to the head node (the first node in the list).
Example:
class LinkedList {
private Node head;
// Constructor to initialize an empty list
public LinkedList() {
head = null;
}
// Function to check if the list is empty
public boolean isEmpty() {
return head == null;
}
}
Here, the LinkedList class has:
- A reference to the
headnode. - A method
isEmpty()to check if the list is empty.
3. Inserting Nodes into the Linked List
There are two common ways to insert a node into a singly linked list:
- At the beginning: The new node becomes the head of the list.
- At the end: The new node is added after the last node.
a) Inserting at the Beginning
public void insertAtBeginning(int value) {
Node newNode = new Node(value);
newNode.next = head; // New node points to the current head
head = newNode; // Update head to the new node
}
Here:
- We create a new node.
- Set its
nextpointer to the current head. - Update the head pointer to point to the new node.
b) Inserting at the End
public void insertAtEnd(int value) {
Node newNode = new Node(value);
if (head == null) {
head = newNode;
return;
}
Node temp = head;
while (temp.next != null) {
temp = temp.next;
}
temp.next = newNode;
}
In this method:
- We create a new node and, if the list is empty, make it the head.
- Otherwise, we traverse the list to find the last node and update its
nextpointer to the new node.
4. Displaying the Linked List
To display the elements of the linked list, we traverse from the head node to the last node, printing the value of each node.
Example:
public void displayList() {
if (head == null) {
System.out.println("List is empty");
return;
}
Node temp = head;
while (temp != null) {
System.out.print(temp.data + " -> ");
temp = temp.next;
}
System.out.println("null");
}
This function:
- Starts at the head and prints each node’s
datafield. - Stops when
tempbecomesnull, indicating the end of the list.
5. Deleting a Node
Removing nodes from the list can involve:
- Deleting the first node (head).
- Deleting a node with a specific value.
a) Deleting the First Node (Head)
public void deleteFirstNode() {
if (head == null) {
System.out.println("List is empty");
return;
}
head = head.next; // Update head to the next node
}
This method:
- Checks if the list is empty.
- Updates the head to point to the next node, effectively removing the first node.
b) Deleting a Node by Value
public void deleteNode(int value) {
if (head == null) {
System.out.println("List is empty");
return;
}
if (head.data == value) {
head = head.next; // Delete head node if it matches the value
return;
}
Node temp = head;
Node prev = null;
while (temp != null && temp.data != value) {
prev = temp;
temp = temp.next;
}
if (temp == null) {
System.out.println("Value not found");
return;
}
prev.next = temp.next; // Unlink the node from the list
}
In this method:
- We check if the node to delete is the head.
- If not, we search for the node and update the
nextpointer of the previous node to skip the target node.
6. Complete Example
Here’s the complete implementation of a basic linked list in Java, including node insertion, display, and deletion.
public class LinkedList {
private Node head;
class Node {
int data;
Node next;
Node(int value) {
data = value;
next = null;
}
}
public LinkedList() {
head = null;
}
public void insertAtBeginning(int value) {
Node newNode = new Node(value);
newNode.next = head;
head = newNode;
}
public void insertAtEnd(int value) {
Node newNode = new Node(value);
if (head == null) {
head = newNode;
return;
}
Node temp = head;
while (temp.next != null) {
temp = temp.next;
}
temp.next = newNode;
}
public void displayList() {
if (head == null) {
System.out.println("List is empty");
return;
}
Node temp = head;
while (temp != null) {
System.out.print(temp.data + " -> ");
temp = temp.next;
}
System.out.println("null");
}
public void deleteFirstNode() {
if (head == null) {
System.out.println("List is empty");
return;
}
head = head.next;
}
public void deleteNode(int value) {
if (head == null) {
System.out.println("List is empty");
return;
}
if (head.data == value) {
head = head.next;
return;
}
Node temp = head;
Node prev = null;
while (temp != null && temp.data != value) {
prev = temp;
temp = temp.next;
}
if (temp == null) {
System.out.println("Value not found");
return;
}
prev.next = temp.next;
}
public static void main(String[] args) {
LinkedList list = new LinkedList();
list.insertAtEnd(10);
list.insertAtEnd(20);
list.insertAtEnd(30);
System.out.print("Initial list: ");
list.displayList();
list.deleteFirstNode();
System.out.print("After deleting first node: ");
list.displayList();
list.deleteNode(20);
System.out.print("After deleting node with value 20: ");
list.displayList();
}
}
Conclusion
In this tutorial, you've learned how to manually implement a basic singly linked list in Java. You've covered how to add nodes, display the list, and delete nodes. Linked lists form the basis for more complex data structures like stacks and queues, and understanding how to implement them will enhance your skills in algorithms and data structures.