Understanding Linked Lists in Java | Data Structure

Linked lists are a fundamental data structure in computer science, offering a dynamic way to store and manage collections of elements. Unlike arrays, linked lists provide efficient insertion and deletion operations, making them a versatile choice for many applications. In this blog post, we’ll explore what linked lists are, their structure, and how to implement and use them in Java.

What is a Linked List?

A linked list is a linear data structure where elements, known as nodes, are stored in a sequence. Each node contains two parts:

Data: The value stored in the node.
Next: A reference (or link) to the next node in the sequence.

The first node in the list is called the head, and the last node points to null, indicating the end of the list.

Types of Linked Lists

Singly Linked List: Each node points to the next node.
Doubly Linked List: Each node points to both the next and the previous node.
Circular Linked List: The last node points back to the first node, forming a circle.

Why Use Linked Lists?

Linked lists offer several advantages:

Dynamic Size: They can grow and shrink as needed, unlike arrays with a fixed size.
Efficient Insertions/Deletions: Adding or removing elements from a linked list is faster than with an array, especially for large datasets.

However, linked lists also have drawbacks, such as higher memory usage and slower access times compared to arrays.

Implementing a Singly Linked List in Java

Let’s start with the basic implementation of a singly linked list in Java.

Node Class

The Node class represents each element in the linked list.

				
					public class Node {
    int data;
    Node next;

    public Node(int data) {
        this.data = data;
        this.next = null;
    }
}

LinkedList Class

The LinkedList class manages the nodes and provides methods to manipulate the list.

				
					public class LinkedList {
    private Node head;

    // Add a new node at the end of the list
    public void add(int data) {
        Node newNode = new Node(data);
        if (head == null) {
            head = newNode;
        } else {
            Node current = head;
            while (current.next != null) {
                current = current.next;
            }
            current.next = newNode;
        }
    }

    // Print all elements in the list
    public void printList() {
        Node current = head;
        while (current != null) {
            System.out.print(current.data + " ");
            current = current.next;
        }
        System.out.println();
    }

    // Delete a node by value
    public void delete(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;
        }
    }
}

Using the LinkedList Class

Here’s how you can use the LinkedList class to create and manipulate a linked list.

				
					public class Main {
    public static void main(String[] args) {
        LinkedList list = new LinkedList();
        list.add(1);
        list.add(2);
        list.add(3);
        list.printList(); // Output: 1 2 3

        list.delete(2);
        list.printList(); // Output: 1 3

        list.add(4);
        list.printList(); // Output: 1 3 4
    }
}

Real-Life Applications of Linked Lists

Linked lists are used in various applications, including:

Implementing Data Structures: Linked lists are the basis for several other data structures, such as stacks, queues, and graphs.
Memory Management: Operating systems use linked lists to manage free and used memory blocks.
Dynamic Data Handling: Applications that require frequent insertions and deletions, such as a music playlist or a browser’s history, benefit from linked lists.

Conclusion

Linked lists are a powerful data structure that provides flexibility and efficiency for certain operations. Understanding how to implement and use linked lists in Java is essential for any developer. Whether you’re working on complex data structures or simple dynamic lists, linked lists offer a robust solution for managing collections of data.