Core Concept Mastery • DSA Module
A linked list is a linear data structure where elements (nodes) are stored in non-contiguous memory. Each node contains data and a pointer to the next node — like a scavenger hunt where each clue leads to the next. A node is the fundamental building block: a container with two pockets — data and a pointer.
Imagine a scavenger hunt: 'Go to the oak tree' → 'Look under the rock' → 'Check the mailbox'. Each clue (node) has two parts: the instruction (data) and where to go next (pointer). You can't jump to clue 3 without following clue 2. That's sequential access.
Imagine a Scavenger Hunt.
"Go to the big oak tree." → "Look under the rock." → "Check the mailbox." → ❌ (End)
You don't know where the 3rd item is until you find the 2nd one!
Think of a Node like a Backpack.
1struct Node {2int data; // Pocket 13struct Node* next; // Pocket 2 (The Map)4};56// Getting memory from the Heap (Ram)7struct Node* newNode = (struct Node*)malloc(sizeof(struct Node));
The Scavenger Hunt Analogy
Each clue (node) has two parts: the instruction (data) and where to go next (pointer). You don't know where clue 3 is until you reach clue 2.
The Node: Two-Pocket Design
Think of a node like a backpack with two pockets:
Non-Contiguous Memory
Unlike arrays (houses on a street), nodes can live anywhere in memory. The pointer is the only link. No need for a huge empty block — use scattered free space.
Memory Allocation
Nodes live in the heap (dynamic memory). Unlike arrays, you don't reserve space upfront. Each node is created on-demand with malloc (C) or new (C++/Java).
The NULL Sentinel
The last node's pointer is NULL — this is your stop sign. When traversing, checking temp != NULL prevents crashes and marks the end of the list.
Size Calculation
Node size = sizeof(data) + sizeof(pointer). On a 64-bit system, a pointer is 8 bytes. So a node storing an int (4 bytes) takes 12 bytes total — 4 for data, 8 for the pointer.
The Trade-off
You gain: easy insert/delete at head (O(1)). You lose: random access. To reach node 5, you must traverse 1→2→3→4→5.
Linked lists power undo/redo stacks, browser history, and playlists. When you need frequent insertions/deletions without shifting elements, arrays struggle — linked lists shine. Understanding node structure is crucial because every operation manipulates these containers.
"How does a linked list differ from an array in memory, and what does a node contain?"
Linked list uses non-contiguous memory — nodes can be anywhere. Arrays require contiguous blocks. Each node contains data and a pointer to the next node. The pointer stores the memory address (location) of the next node, not the value itself.