DSA Day 88: Push Front in Linked List

📅 Date: August 13, 2026

🧠 Mood: The Memory Allocator 💾

🔥 Topic: DSA Day 88: Push Front in Linked List

🔗 The First Link in the Chain

Sitting in the TCET labs today, it was time to finally breathe life into the LinkedList manager class we built yesterday. An empty list is just a couple of null pointers. To actually store data, we need to dynamically allocate memory and wire it up.

The first operation on the syllabus is Push Front—inserting a brand new node at the very beginning of the list. In a standard Array, pushing to the front is an absolute nightmare. You have to shift every single existing element one step to the right, resulting in a brutal $O(N)$ time complexity. But in a Linked List, because we are just swapping pointers around, it happens instantly.

---

⚙️ The 3-Step Wiring Process

Pointer manipulation in C++ is unforgiving. If you do these steps out of order, you will overwrite your head pointer and permanently lose access to the rest of your data in memory (a severe memory leak).

Step 1: Create the Node

First, use the new keyword to dynamically allocate memory on the heap for the new node.
Node* newNode = new Node(val);

Step 2: Secure the Chain

Before touching the head pointer, make the newNode->next point to the current head. This ensures the new node is securely holding onto the existing list.

Step 3: Update the Head

Now that the list is secure, safely update the main head pointer to point at your newly created node.

---

💻 The C++ Implementation

void pushFront(int val) {
    // 1. Dynamically allocate new node
    Node* newNode = new Node(val);

    // Edge Case: If the list is completely empty
    if (head == NULL) {
        head = tail = newNode;
        return;
    }

    // 2. Link the new node to the current head
    newNode->next = head;

    // 3. Shift the head pointer to the new node
    head = newNode;
}

Performance Breakdown: Because there are no loops and we are strictly reassigning pointers, this entire function executes in $O(1)$ Constant Time and requires $O(1)$ Auxiliary Space. This is the exact reason Linked Lists exist.

---

🎯 One Side Down

We can now inject data instantly into the front of the list. The next logical step is to utilize that tail pointer we set up to push data to the back of the list just as efficiently.