🚀 Mastering Linked Lists in C++: A Beginner's Guide

When we think of storing data, arrays often come to mind. But what if we want dynamic memory allocation-memory that can grow or shrink at runtime? That’s where Linked Lists shine! Unlike arrays, linked lists use pointers and dynamic memory to create flexible, efficient structures.

📌 What is a Linked List?

A Linked List is a linear data structure where elements (called nodes) are linked using pointers. Each node contains data and a pointer to the next node. Unlike arrays, they don't require contiguous memory blocks.

🛠️ Real-Life Use Cases:

• Implementation of stacks, queues, and graphs.

• Efficient memory management in games and real-time systems.

• Undo/redo functionality in text editors.

🔗 Singly Linked List

A Singly Linked List (SLL) is the simplest form. Each node points only to the next node. The last node points to NULL, signaling the end.

🧱 Structure of a Node

In C++, we use a class or struct to define a node.

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

    Node()
    {
        next = NULL;
    }
};

• data stores the value.

• next is a pointer to the next node in the list.

➕ Insertion Operations

We can insert a node at:

1. Beginning:

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

2. End:

    void insert_at_end(int value)
        {
            if (head == NULL)
            {
                insert_at_beg(value);
            }
            else
            {
                Node *temp = new Node();
                temp->data = value;
   
                Node *itr = head;
   
                while (itr->next != NULL)
                {
                    itr = itr->next;
                }
   
                itr->next = temp;
            }
        }
   

3. Middle (at a given position):

    void insert_in_mid(int value, int position)
        {
            int pos = 1;
   
            if (head == NULL || position == pos)
            {
                insert_at_beg(value);
            }
   
            else
            {
                Node *temp = new Node();
                temp->data = value;
   
                Node *itr = head;
   
                while (pos < position - 1)
                {
                    if (itr->next != NULL)
                    {
                        itr = itr->next;
                        pos++;
                    }
                    else
                    {
                        insert_at_end(value);
                        return;
                    }
                }
   
                temp->next = itr->next;
                itr->next = temp;
            }
        }
   

🗑️ Deletion Operations

We can delete nodes from:

1. Beginning:

        void delete_at_beg() {
            if(head == NULL) {
                cout << "Empty List" << endl;
                return;
            }
   
            Node *temp = head;
   
            head = head -> next;
   
            delete temp;
        }
   

2. End:

        void delete_at_end() {
            if(head == NULL) {
                cout << "Empty List" << endl;
            }
            else if(head -> next == NULL) {
                delete head;
            }
            else {
                Node *temp = head;
   
                while(temp -> next -> next != NULL) {
                    temp = temp->next;
                }
   
                delete temp -> next;
   
                temp->next = NULL;
            }
        }
   

3. Middle (specific position):

    void delete_at_position(int position) {
            if(head == NULL) {
                cout << "Empyt List" << endl;
            }
            else if(position == 1) {
                delete_at_beg();
            }
            else {
                Node *itr = head;
   
                while(position - 2 != 0 && itr -> next != NULL) {
                    itr = itr->next;
                    position--;
                }
   
                Node *temp = itr->next;
   
                itr->next = temp->next;
   
                delete temp;
            }
        }
   

👀 Displaying the Linked List

Let’s print all the nodes one by one:

void print()
    {
        if (head == NULL)
        {
            cout << "List is empty" << endl;
        }
        else
        {
            Node *temp = head;

            while (temp != NULL)
            {
                cout << temp->data;
                if (temp->next != NULL)
                {
                    cout << " -> ";
                }
                temp = temp->next;
            }
        }
    }

🧠 Conclusion

Linked Lists are a fundamental yet powerful concept in data structures. Once you master SLLs, diving into doubly and circular linked lists becomes much easier.

If you're preparing for coding interviews or DSA contests, mastering operations like insertion and deletion is a must.

Want more deep dives on DSA? Follow me for regular updates!