DSA Day 86: Introduction to Linked Lists

📅 Date: August 11, 2026

🧠 Mood: The Explorer 🧭

🔥 Topic: DSA Day 86: Introduction to Linked Lists

⛓️ Breaking the Contiguous Memory Limit

Up until now in my IT Engineering journey, every data collection I have worked with—whether standard Arrays or dynamic Vectors—relied on contiguous memory. If you want to store 5 integers, the operating system finds a single, unbroken block of memory to fit them all side-by-side.

But what happens when your RAM is fragmented? What if you need to frequently insert elements right in the middle of a massive dataset? Arrays require shifting thousands of elements, giving you a brutal $O(N)$ time complexity. Today, we step into a completely new paradigm to solve this: Linked Lists.

---

🧠 What is a Linked List?

A Linked List is a linear data structure, but unlike arrays, its elements are not stored in contiguous memory locations. Instead, the elements are scattered all over the RAM, connected to each other using pointers.

The Anatomy of a Node

The fundamental building block of a Linked List is called a Node. You can think of a Node as a container that holds exactly two pieces of information:

• Data: The actual value you want to store (an integer, string, object, etc.).
• Next Pointer: The memory address (reference) of the very next Node in the sequence.

The Head and The Tail

To access a Linked List, we only need to know where it starts. This starting node is called the Head. The very last node in the list points to NULL, indicating the end of the chain. This node is known as the Tail.

---

💻 Defining a Node in C++

Because standard C++ does not have a built-in primitive for a Linked List node, we have to create a custom blueprint using a class or struct. Here is the raw architecture:

#include <iostream>
using namespace std;

// Blueprint for a Linked List Node
class Node {
public:
    int data;       // The actual value
    Node* next;     // Pointer to the next node

    // Constructor to initialize a new Node
    Node(int val) {
        data = val;
        next = NULL;
    }
};

---

🎯 The Setup is Complete

Right now, this is just a blueprint. A single node floating in memory isn't a list yet. The real challenge comes next: dynamically allocating memory and linking these nodes together to form a chain.