Linked List in Data Structures

Introduction

Suppose you are tracking cars entering a parking lot. Since the number of cars keeps changing, arrays (which are fixed in size) won't be efficient.
That’s where Linked Lists come in handy. They are dynamic, memory-efficient, and allow easy insertion/deletion.

---

Q) What is a Linked List?

A Linked List is a linear data structure where elements are stored in nodes, and each node points to the next node.

Each node contains:

• data: actual value

• next: pointer to next node

—>Visual Representation

[0 | *] → [1| *] → [2| *] → NULL
 ↑                      ↑
head                  tail

---

⚙️ Differences from Arrays

---

—> Memory Usage

Linked Lists require more space due to pointers but offer dynamic memory benefits.

---

—>Node Structure in C++

class node {
public:
    int data;
    node *next;

    node() {
        next = NULL;
    }
};

---

—>LinkedList Class

class LinkedList {
    node *head;

public:
    LinkedList() {
        head = NULL;
    }

    void print() {
        if(head == NULL)
            cout << "List is Empty";
        else {
            node *temp = head;
            while(temp != NULL) {
                cout << temp->data << " -> ";
                temp = temp->next;
            }
        }
    }

---

—> Insertion Operations

—>1. Insert at Start

void insert_at_beg(int value) {
    node *temp = new node();
    temp->data = value;
    temp->next = head;
    head = temp;
}

Dry Run:
Before: NULL → Insert 10 → After: [10 | NULL]

---

📍 2. Insert at Specific Position

void insert_at_position(int value, int position) {
    node *temp = new node();
    temp->data = value;

    if(position == 1) {
        temp->next = head;
        head = temp;
    } else {
        node *t = head;
        while((position - 2) != 0 && t->next != NULL) {
            t = t->next;
            position--;
        }

        temp->next = t->next;
        t->next = temp;
    }
}

Dry Run:
Before: 10 -> 20 -> 30 → Insert 15 at pos 2 → After: 10 -> 15 -> 20 -> 30

---

—>3. Insert at End

void insert_at_end(int value) {
    node *temp = new node();
    temp->data = value;

    if(head == NULL) {
        head = temp;
    } else {
        node *t = head;
        while(t->next != NULL)
            t = t->next;
        t->next = temp;
    }
}

Dry Run:
Before: 10 -> 20 → Insert 30 → After: 10 -> 20 -> 30

---

—> Deletion Operations

→ 1. Delete at Start

void delete_at_beg() {
    if(head == NULL)
        cout << "Deletion not possible";
    else {
        node *temp = head;
        head = head->next;
        delete temp;
    }
}

Dry Run:
Before: 10 -> 20 → After deleting head: 20

—> 2. Delete at Position

void delete_at_position(int pos) {
    if(head == NULL)
        cout << "Not possible";
    else if(pos == 1) {
        node *t = head;
        head = head->next;
        delete t;
    } else {
        node *t = head;
        while((pos - 2) != 0 && t->next != NULL) {
            t = t->next;
            pos--;
        }

        node *temp = t->next;
        t->next = temp->next;
        delete temp;
    }
}

Dry Run:
Before: 10 -> 15 -> 20 → Delete at pos 2 → After: 10 -> 20

---

—>3. Delete at End

void delete_at_end() {
    if(head == NULL)
        cout << "List is empty";
    else if(head->next == NULL) {
        delete head;
        head = NULL;
    } else {
        node *t = head;
        while(t->next->next != NULL)
            t = t->next;

        delete t->next;
        t->next = NULL;
    }
}

Dry Run:
Before: 10 -> 20 -> 30 → After deleting last: 10 -> 20

---

—> Main Function Demo

int main() {
    LinkedList ll;
    ll.insert_at_beg(10);
    ll.insert_at_beg(20);
    ll.insert_at_beg(30);
    ll.insert_at_beg(40);
    ll.insert_at_beg(100);

    ll.insert_at_end(15);
    ll.insert_at_position(50, 5);

    ll.delete_at_beg();
    ll.delete_at_end();
    ll.delete_at_position(3);

    ll.print(); // Output: 40 -> 30 -> 50 -> 20 ->
    return 0;
}

---

—> Types of Linked Lists

---

—> Applications of Linked Lists

• Used in Stacks and Queues

• Undo/Redo features in text editors

• Music playlists, image viewers

• Web browser history navigation

• Dynamic memory management

---

—> Conclusion

Linked Lists are one of the fundamental data structures that offer dynamic memory allocation and efficient insertion and deletion. They are especially useful when the size of the data is unknown or changes frequently during runtime. Although they require more memory due to pointer storage and lack direct access to elements (unlike arrays), their flexibility makes them ideal for many real-world applications like memory management, operating systems, and complex data modeling. By mastering Linked Lists, you take a big step forward in your understanding of Data Structures and Algorithms.