DSA Day 89: Push Back in Linked List

📅 Date: August 14, 2026

🧠 Mood: The Optimizer ⚡

🔥 Topic: DSA Day 89: Push Back in Linked List

🚄 The Power of the Tail Pointer

On the train back to Thane today, I was thinking about how inefficient standard arrays can be when appending data if they run out of pre-allocated capacity. They have to copy everything to a new, larger block of memory. Linked Lists completely bypass this issue.

Today's syllabus video covered Push Back (inserting a node at the very end of the list). This is where the tail pointer we defined in our manager class a few days ago proves its absolute worth. Without a tail pointer, finding the end of the list would require traversing every single node from the head, resulting in an $O(N)$ time complexity. With the tail pointer, we skip the travel and do it instantly.

---

🔌 Wiring the End of the Chain

The logic for pushing to the back is incredibly straightforward, but just like pushFront, the order of pointer manipulation is critical.

Step 1: The New Node

Create the new node dynamically in heap memory. By default, its next pointer is initialized to NULL, which is perfect since it will be the new end of the list.

Step 2: Connect the Old Tail

Take the current tail of the list and update its next pointer. Instead of pointing to NULL, it must now point to our newly created node.

Step 3: Shift the Tail

Finally, update the class's tail pointer to point at the new node, officially crowning it the new end of the chain.

---

💻 The C++ Implementation

void pushBack(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 current tail to the new node
    tail->next = newNode;

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

Performance Breakdown: Because we maintained a tail pointer, there is no loop traversing the elements. The entire insertion is resolved with three simple pointer updates, yielding a perfect $O(1)$ Time Complexity and $O(1)$ Space Complexity.

---

🎯 Data Loaded

We can now inject data instantly into both the front and the back of our Linked List. However, right now, we are just blindly throwing nodes into the void of memory. Tomorrow, we write the logic to traverse the list and actually print our data to the console.