Data Structures & Algorithms - Linked List Algorithms

Share with a Friend

What is a Linked List?

A Linked List is a linear data structure in which elements (nodes) are stored non-contiguously in memory. Each node contains:

1. Data (the value stored in the node)
2. Pointer (or reference) to the next node in the sequence

Unlike arrays, linked lists do not require continuous memory allocation, making them more efficient for dynamic memory allocation.

Key Features of Linked Lists

✅ Dynamic Size → Can grow and shrink at runtime.
✅ Efficient Insertions/Deletions → O(1) at the beginning, O(n) at arbitrary positions.
✅ No Wasted Memory → Unlike arrays, no need for a predefined size.
❌ Slow Access Time → O(n) for searching (no direct indexing like arrays).

Types of Linked Lists

1️⃣ Singly Linked List (SLL) → Each node has a single pointer to the next node.
2️⃣ Doubly Linked List (DLL) → Each node has pointers to both previous and next nodes.
3️⃣ Circular Linked List (CLL) → The last node points to the first node (can be singly or doubly).

Linked Lists vs Arrays: A Detailed Comparison

Both Linked Lists and Arrays are linear data structures, but they have fundamental differences in memory management, access speed, and operations.

🔹 1. Key Differences Between Linked Lists and Arrays

🔹 2. When to Use Linked Lists vs Arrays

🔹 3. Example Scenarios

✅ Use Arrays when:

• You need fast random access (e.g., accessing elements via an index).
• You have a fixed size dataset (e.g., storing a list of students' grades).

✅ Use Linked Lists when:

• You need frequent insertions/deletions (e.g., maintaining an undo history).
• Memory availability is uncertain, and dynamic growth is needed.

📌 Types of Linked Lists

A linked list is a dynamic data structure where elements (nodes) are stored non-contiguously in memory. Each node contains:

1. Data → Stores the value.
2. Pointer(s) → Stores the address of the next (or previous) node.

1️⃣ Singly Linked List (SLL)

📝 Characteristics

🖼 Graphical Representation

HEAD → [Data | Next] → [Data | Next] → [Data | NULL]

📌 Example Code

#include <stdio.h>
#include <stdlib.h>

struct Node {
    int data;
    struct Node* next;
};

// Insert at beginning
void insertAtBeginning(struct Node** head, int newData) {
    struct Node* newNode = (struct Node*)malloc(sizeof(struct Node));
    newNode->data = newData;
    newNode->next = *head;
    *head = newNode;
}

// Print linked list
void printList(struct Node* head) {
    while (head) {
        printf("%d -> ", head->data);
        head = head->next;
    }
    printf("NULL\n");
}

int main() {
    struct Node* head = NULL;
    insertAtBeginning(&head, 10);
    insertAtBeginning(&head, 20);
    insertAtBeginning(&head, 30);
    
    printList(head);
    return 0;
}

30 -> 20 -> 10 -> NULL

2️⃣ Doubly Linked List (DLL)

📝 Characteristics

✅ Each node contains data, a pointer to the next node, and a pointer to the previous node.
✅ Traversal can be forward & backward.
✅ Last node’s next pointer is NULL.
✅ More memory usage due to extra pointer.

🖼 Graphical Representation

NULL ← [Prev | Data | Next] ↔ [Prev | Data | Next] ↔ [Prev | Data | NULL]

📌 Example Code

class Node:
    def __init__(self, data):
        self.data = data
        self.next = None
        self.prev = None

class DoublyLinkedList:
    def __init__(self):
        self.head = None

    def insertAtBeginning(self, newData):
        newNode = Node(newData)
        newNode.next = self.head
        if self.head:
            self.head.prev = newNode
        self.head = newNode

    def printList(self):
        temp = self.head
        while temp:
            print(temp.data, end=" <-> ")
            temp = temp.next
        print("NULL")

dll = DoublyLinkedList()
dll.insertAtBeginning(10)
dll.insertAtBeginning(20)
dll.insertAtBeginning(30)
dll.printList()

30 <-> 20 <-> 10 <-> NULL

3️⃣ Circular Linked List (CLL)

📝 Characteristics

✅ In a Singly Circular LL, the last node points back to the first node.
✅ In a Doubly Circular LL, both next and prev pointers form a cycle.
✅ No NULL pointers; traversal can continue infinitely.
✅ Used in round-robin scheduling.

🖼 Graphical Representation

Singly Circular: 
HEAD → [Data | Next] → [Data | Next] → [Data | HEAD] (Circular)

Doubly Circular:
HEAD ↔ [Prev | Data | Next] ↔ [Prev | Data | Next] ↔ [Prev | Data | HEAD]
 

📌 Example Code

#include <iostream>
using namespace std;

class Node {
public:
    int data;
    Node* next;
};

void insertAtEnd(Node*& head, int newData) {
    Node* newNode = new Node();
    newNode->data = newData;
    newNode->next = head;

    if (!head) {
        head = newNode;
        newNode->next = head;
        return;
    }

    Node* temp = head;
    while (temp->next != head) temp = temp->next;
    temp->next = newNode;
}

void printList(Node* head) {
    if (!head) return;
    Node* temp = head;
    do {
        cout << temp->data << " -> ";
        temp = temp->next;
    } while (temp != head);
    cout << "(Back to Head)\n";
}

int main() {
    Node* head = NULL;
    insertAtEnd(head, 10);
    insertAtEnd(head, 20);
    insertAtEnd(head, 30);
    
    printList(head);
    return 0;
}

10 -> 20 -> 30 -> (Back to Head)

📌 Summary

📌 Conclusion

• SLL → Simple & memory-efficient
• DLL → Efficient for backward traversal
• CLL → No NULL values, useful in applications like CPU Scheduling