A Linked List is a linear data structure where elements, called nodes, are stored in memory in a non-contiguous manner. Each node contains two parts: data and a reference (or link) to the next node in the sequence.
Linked lists provide dynamic memory allocation and are useful for managing data that changes in size frequently.
Types of Linked Lists
There are several types of linked lists, each with its own properties:
Singly Linked List: Each node points to the next node in the list, and the last node points to null. It can only be traversed forward.
|
1 |
Head -> [10|next] -> [20|next] -> [30|null] |
Doubly Linked List: Each node has two references: one pointing to the next node and another pointing to the previous node. Supports both forward and backward traversal.
|
1 |
null <- [10|prev|next] <-> [20|prev|next] <-> [30|prev|null] |
Circular Linked List: The last node points back to the first node, forming a circle. Can be Singly Circular (only next pointer) or Doubly Circular (both prev & next).
|
1 |
[10|next] -> [20|next] -> [30|next] -↺ |
Declaration & Initialization
Singly Linked List
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 |
class Node { int data; Node next; Node(int data) { this.data = data; this.next = null; } } class LinkedList { Node head; LinkedList() { head = null; } } |
Doubly Linked List
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 |
class Node { int data; Node next; Node prev; Node(int data) { this.data = data; this.next = null; this.prev = null; } } class DoublyLinkedList { Node head; DoublyLinkedList() { head = null; } } |
Circular Linked List
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 |
class Node { int data; Node next; Node(int data) { this.data = data; this.next = null; } } class CircularLinkedList { Node head; CircularLinkedList() { head = null; } // Method to create a circular linked list with one node public void createCircularList(int data) { Node newNode = new Node(data); head = newNode; newNode.next = head; // Points to itself } } |
Basic Operations
Insertion: Adding a node to the linked list can be done at the beginning, end, or in the middle of the list.
|
1 2 3 4 5 6 |
// Insert at the beginning public void insertAtBeginning(int data) { Node newNode = new Node(data); newNode.next = head; head = newNode; } |
Deletion: Removing a node can be done by updating the references (or pointers) to bypass the node.
|
1 2 3 4 5 6 |
// Delete from the beginning public void deleteFromBeginning() { if (head != null) { head = head.next; } } |
Traversal: Going through each node and printing its data.
|
1 2 3 4 5 6 7 |
public void traverse() { Node current = head; while (current != null) { System.out.print(current.data + " "); current = current.next; } } |
Java’s Built-in LinkedList Class
Instead of implementing a custom linked list, Java provides a LinkedList class in the java.util package.
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 |
import java.util.LinkedList; public class Main { public static void main(String[] args) { LinkedList<Integer> list = new LinkedList<>(); // Adding elements list.add(10); list.add(20); list.add(30); // Printing the list System.out.println(list); // Output: [10, 20, 30] // Removing elements list.remove(1); // Removes the element at index 1 (20) System.out.println(list); // Output: [10, 30] // Accessing elements System.out.println(list.get(0)); // Output: 10 } } |
Advantages & Disadvantages
| Advantages | Disadvantages |
|---|---|
| Dynamic Size: Memory is allocated as needed. | Memory Overhead: Extra space for storing references (next/prev). |
| Efficient Insertions/Deletions: Inserting or deleting nodes is fast, especially at the beginning. | Access Time: Slower access to elements, as we have to traverse from the head. |
| Easy to Grow/Shrink: Size can change without reallocation or shifting elements. | Complexity: Requires careful memory management due to the use of pointers. |
Real-World Examples
- Music Playlist: In a music player app, songs in a playlist can be implemented as a linked list, where each node contains song details and the reference to the next song.
- Navigation Systems: A linked list can be used to represent waypoints or stages in a route, allowing dynamic updates as new waypoints are added or removed.
- Undo/Redo Functionality: In text editors or graphic design software, linked lists can store previous actions, enabling efficient undo/redo functionality.
