Introduction: Singly Linked Lists are fundamental data structures widely used in programming and problem-solving. Unlike arrays, linked lists do not have a fixed size, allowing for dynamic data management. In this blog post, we’ll explore the concept of a singly linked list, its applications, and walk through a step-by-step Java implementation. To learn more about linked lists, click here.
What is a Singly Linked List?
A singly linked list is a data structure composed of nodes, where each node contains:
- Data: The element stored in the node.
- Next: A pointer to the next node in the list.
Unlike doubly linked lists, singly linked lists only allow traversal in one direction—from the head to the end.
Why Use a Singly Linked List?
- Dynamic Size: Nodes can be added or removed easily, making it ideal for scenarios where the number of elements varies.
- Efficient Insertion/Deletion: Unlike arrays, which require shifting elements, linked lists allow efficient insertion and deletion without rearranging other elements.
Singly Linked List Implementation in Java
Step 1: Defining the Node Class
Each node in the linked list contains data and a reference to the next node. Here’s how the Node class is defined:
class Node {
int data;
Node next;
public Node(int data) {
this.data = data;
this.next = null;
}
}Step 2: Creating the Linked List Class
The LinkedList class will manage the nodes, including operations like insertion, deletion, and traversal.
class LinkedList {
Node head;
public LinkedList() {
this.head = null;
}
}Step 3: Inserting Nodes
Let’s implement methods to add elements to the list. We’ll cover insertion at the end and at the beginning.
- Insert at the Beginning:
public void insertAtBeginning(int data) {
Node newNode = new Node(data);
newNode.next = head;
head = newNode;
}- Insert at the End:
public void insertAtEnd(int data) {
Node newNode = new Node(data);
if (head == null) {
head = newNode;
return;
}
Node current = head;
while (current.next != null) {
current = current.next;
}
current.next = newNode;
}Step 4: Deleting Nodes
To delete nodes, let’s create methods for removing the first node and node with specific data.
- Delete at the Beginning
public void deleteAtBeginning() {
if (head != null) {
head = head.next;
}
}- Delete by Value
public void deleteByValue(int data) {
if (head == null) return;
if (head.data == data) {
head = head.next;
return;
}
Node current = head;
while (current.next != null && current.next.data != data) {
current = current.next;
}
if (current.next != null) {
current.next = current.next.next;
}
}Step 5: Traversing the List
Traversal involves iterating through the list to access each element.
public void display() {
Node current = head;
while (current != null) {
System.out.print(current.data + " -> ");
current = current.next;
}
System.out.println("null");
}Example: Using the Singly Linked List in Java
public class Main {
public static void main(String[] args) {
LinkedList list = new LinkedList();
list.insertAtBeginning(10);
list.insertAtEnd(20);
list.insertAtEnd(30);
System.out.println("List after insertions:");
list.display();
list.deleteByValue(20);
System.out.println("List after deleting 20:");
list.display();
list.deleteAtBeginning();
System.out.println("List after deleting at the beginning:");
list.display();
}
}Output:
List after insertions:
10 -> 20 -> 30 -> null
List after deleting 20:
10 -> 30 -> null
List after deleting at the beginning:
30 -> nullComplete Java Program for Singly Linked List
Here’s the full Java program combining the Node, LinkedList, and Main classes:
class Node {
int data;
Node next;
public Node(int data) {
this.data = data;
this.next = null;
}
}
class LinkedList {
Node head;
public LinkedList() {
this.head = null;
}
public void insertAtBeginning(int data) {
Node newNode = new Node(data);
newNode.next = head;
head = newNode;
}
public void insertAtEnd(int data) {
Node newNode = new Node(data);
if (head == null) {
head = newNode;
return;
}
Node current = head;
while (current.next != null) {
current = current.next;
}
current.next = newNode;
}
public void deleteAtBeginning() {
if (head != null) {
head = head.next;
}
}
public void deleteByValue(int data) {
if (head == null) return;
if (head.data == data) {
head = head.next;
return;
}
Node current = head;
while (current.next != null && current.next.data != data) {
current = current.next;
}
if (current.next != null) {
current.next = current.next.next;
}
}
public void display() {
Node current = head;
while (current != null) {
System.out.print(current.data + " -> ");
current = current.next;
}
System.out.println("null");
}
}
public class Main {
public static void main(String[] args) {
LinkedList list = new LinkedList();
list.insertAtBeginning(10);
list.insertAtEnd(20);
list.insertAtEnd(30);
System.out.println("List after insertions:");
list.display();
list.deleteByValue(20);
System.out.println("List after deleting 20:");
list.display();
list.deleteAtBeginning();
System.out.println("List after deleting at the beginning:");
list.display();
}
}
Output:
List after insertions:
10 -> 20 -> 30 -> null
List after deleting 20:
10 -> 30 -> null
List after deleting at the beginning:
30 -> null
Conclusion
Conclusion
In this guide, we implemented a simple singly linked list in Java. We learned about adding and removing nodes, as well as traversing the list. Singly linked lists are great for understanding basic data structure principles, and mastering them will set a strong foundation for more complex structures and algorithms. Experiment with this code and try implementing additional features like searching for an element or counting nodes!