Linked Lists: Dynamic Data Chains

The Problem: When Arrays Get in the Way

Suppose your school's Class 8-B result sheet is stored as a Python list of marks, in roll-number order: marks = [56, 78, 45, 90, 63, 88]. A new student, roll number 3, joins the class mid-term and needs to be slotted in at index 2, with a mark of 70. In an array (which is what a Python list is, under the hood: one continuous block of memory), every value lives in a fixed slot right next to its neighbour. There is no gap at index 2 to drop the new mark into — slots 2, 3, 4, and 5 are all occupied. So the computer has no choice but to physically shift every mark from index 2 onward one position to the right, starting from the last one, to open up space:

Before:  [56, 78, 45, 90, 63, 88]        indices: 0   1   2   3   4   5   (length 6)
Goal:    insert 70 at index 2  ->  array grows to length 7

Step 1:  shift 88 from index 5 into index 6  -> [56, 78, 45, 90, 63, 88, 88]
Step 2:  shift 63 from index 4 into index 5  -> [56, 78, 45, 90, 63, 63, 88]
Step 3:  shift 90 from index 3 into index 4  -> [56, 78, 45, 90, 90, 63, 88]
Step 4:  shift 45 from index 2 into index 3  -> [56, 78, 45, 45, 90, 63, 88]
Step 5:  place 70 into index 2               -> [56, 78, 70, 45, 90, 63, 88]

Look closely at that trace and you'll notice the trap: you must shift from the back of the array toward the insertion point, never from the front, otherwise you overwrite a value before you've copied it elsewhere — try shifting index 2 into index 3 first, and the original 90 at index 3 is gone before anyone reads it. Done correctly, inserting at index 2 requires shifting the 4 elements originally at indices 2, 3, 4, and 5 — one slot each — before the new value can be written in. In general, inserting at index k in an array of n elements costs n − k moves in the worst case. Insert near the front of a 10,000-row attendance array, and you move close to 10,000 values just to fit in one new name. This is not a Python quirk — it is a direct consequence of arrays using contiguous memory: every element's address is calculated as base_address + index × element_size, which only works if there are no gaps. Deleting from the middle has the identical problem in reverse: every later element must shift left to close the gap.

A Better Idea: Coaches, Not Numbered Seats

Think about how an Indian Railways train is assembled. Coach S4 does not need to sit in physical position 4 of the platform for the train to work — it just needs to know which coach is coupled right after it. If the railways want to insert a new pantry coach between S4 and S5, they do not uncouple and shift every single coach behind S5 down the track. They simply uncouple S4 from S5, roll the new coach in, and couple S4 to the new coach, and the new coach to S5. Two couplings change; nothing else in the train moves.

A linked list stores data the same way. Instead of keeping elements in fixed, numbered slots next to each other in memory, it keeps a chain of small packets scattered anywhere in memory, where each packet knows only one thing about its neighbour: where to find the next one. Inserting or removing a packet in the middle means re-pointing at most two connections — not moving every packet that comes after it.

Anatomy of a Node

Each packet in this chain is called a node, and every node has exactly two parts:

• data — the actual value being stored (a mark, a name, a train coach number)
• next — a reference (in C this would be called a pointer) that holds the memory location of the following node, or a special value like None if this is the last node

The list itself keeps only one extra piece of information: a reference called HEAD, pointing to the very first node. If you lose the HEAD reference, the entire chain becomes unreachable, even though every node still physically exists in memory — this is why linked lists are always accessed starting from HEAD and walking forward, never by jumping to an arbitrary middle node the way arr[3] jumps straight to index 3 in an array.

Building a Linked List in Python

CBSE's Python-based curriculum lets us build this structure directly, using a class for the node and a class for the list:

class Node:
    def __init__(self, data):
        self.data = data   # the value
        self.next = None   # reference to next node; None until linked

class LinkedList:
    def __init__(self):
        self.head = None   # empty list: head points at nothing

    def append(self, data):
        new_node = Node(data)
        if self.head is None:          # list is empty
            self.head = new_node
            return
        current = self.head
        while current.next is not None:  # walk until the last node
            current = current.next
        current.next = new_node          # attach at the end

    def print_list(self):
        current = self.head
        while current is not None:
            print(current.data, end=" -> ")
            current = current.next
        print("None")

Building the same roll-number marks from before, one node at a time:

ll = LinkedList()
for mark in [67, 82, 45, 91]:
    ll.append(mark)
ll.print_list()

Output: 67 -> 82 -> 45 -> 91 -> None

Trace exactly what happens, since this is the mechanic the entire chapter rests on. append(67): self.head is None, so the new node becomes head directly. append(82): head now exists, so current starts at the 67-node; its next is already None, so the while loop body never runs, and current.next is set straight to the new 82-node. append(45): current starts at 67, sees current.next is the 82-node (not None), so the loop runs once, moving current to 82; now current.next is None, the loop stops, and 45 is attached after 82. append(91) follows the same pattern, walking two hops before attaching. Notice something important here: append gets slower as the list grows, because reaching the end always means walking from HEAD — there is no shortcut to "the last node" the way there is to "the last index" in an array.

Traversal: Walking the Chain

"Traversal" just means visiting every node once, from HEAD to the end. It is the linked-list equivalent of a for loop over an array, but instead of incrementing an index, you follow the next reference each time. Here is the state of every variable during print_list() on the list built above:

• Step 1: current = 67-node → print 67 -> → current becomes 82-node
• Step 2: current = 82-node → print 82 -> → current becomes 45-node
• Step 3: current = 45-node → print 45 -> → current becomes 91-node
• Step 4: current = 91-node → print 91 -> → current becomes None
• Step 5: current is None → loop condition fails → print None on the same line

Five steps to reach four nodes plus the terminator — that's the general pattern: visiting all n nodes always takes n hops, regardless of what the data values are. There is no way to skip ahead to node 3 without first visiting nodes 1 and 2, because the only address you're ever handed is HEAD's.

Insertion: Rewiring References, Not Shifting Data

Now bring back the exact scenario that opened the chapter — inserting mark 70 for the new roll-number-3 student, so it lands between 82 and 45. In the linked list, the code that does this is:

def insert_after(self, prev_node, data):
    if prev_node is None:
        print("Previous node must exist")
        return
    new_node = Node(data)
    new_node.next = prev_node.next   # new node points to what prev used to point to
    prev_node.next = new_node        # prev now points to new node

Suppose prev_node is the node holding 82 (whose next currently points to the 45-node). Trace the two lines in order — the order matters:

• Line 1: new_node.next = prev_node.next → the new 70-node's next is set to the 45-node (the same node 82 used to point to). If you swapped this order, you would lose the reference to 45 forever.
• Line 2: prev_node.next = new_node → the 82-node's next is now the 70-node instead of the 45-node.

Result: 82 -> 70 -> 45, exactly two reference fields changed, no matter how many hundreds of nodes exist elsewhere in the list. Compare this to the array trace from the introduction, where inserting one value required physically moving four existing values. That is the entire payoff of a linked list: once you are holding a reference to the right spot, insertion costs a fixed, constant amount of work — it does not grow with the size of the list.

Deletion: Skipping a Node

Deletion works the same way, in reverse — you skip over the unwanted node rather than erase it and shift the rest:

def delete_after(self, prev_node):
    if prev_node is None or prev_node.next is None:
        return
    removed = prev_node.next        # the node being cut out
    prev_node.next = removed.next   # bridge over it

Continuing the example, to delete the 70-node we just inserted, call delete_after(prev_node) with prev_node as the 82-node. removed is set to the 70-node. Then prev_node.next = removed.next makes 82's next point directly to 45, the node that came after 70. The 70-node still technically exists in memory for an instant, but nothing in the chain points to it anymore, so it is unreachable — in Python, its memory is automatically reclaimed by the garbage collector shortly after. Once again: one reference field changed, regardless of list size, versus an array where deleting from the middle forces every later element to shift left by one to close the gap.

Two Common Misconceptions, Corrected

Misconception 1: "Linked lists are always faster than arrays." This is only half-true, and the half people usually forget is access. An array gives you direct access to any element: marks[3] computes an address and reads it in one step, regardless of array size — this is called O(1), or constant-time, access. A linked list has no such shortcut. To reach the 4th node you must start at HEAD and take three hops, because each node only knows about its immediate neighbour, not its position. So ll_get(3) is O(n) in the worst case — it gets slower as the list grows. The speed advantage of linked lists is strictly about insertion and deletion once you already hold a reference to the correct spot; it is not a blanket "linked lists win" rule. If your program mostly looks things up by position (like "what is the 500th student's mark?"), an array is the better tool. If it mostly inserts and removes from the middle (like a music app reordering an upcoming-songs queue), a linked list is better.

Misconception 2: "Linked lists use less memory than arrays." The opposite is true, element for element. An array of 4 integers stores exactly 4 integers, packed tightly with nothing extra. A linked list storing the same 4 integers needs 4 Node objects, and every single one carries an extra next reference alongside its data — that's memory spent purely on bookkeeping, not on the actual values. For small elements like a single number, this overhead can even double the memory used. Linked lists trade away raw memory efficiency and fast lookups in exchange for cheap insertion and deletion; they are not a free upgrade over arrays in every respect.

Arrays vs Linked Lists: A Fair Comparison

• Access by position (get the value at position k): array — O(1), instant; linked list — O(n), must walk from HEAD
• Search for a value (is 45 present?): array — O(n); linked list — O(n) (both must check element by element, since neither is sorted here)
• Insert/delete at the very front: array — O(n), everything shifts; linked list — O(1), just move HEAD
• Insert/delete once you're already positioned at the spot: array — O(n), everything after shifts; linked list — O(1), rewire two references
• Extra memory per element: array — none; linked list — one reference field per node
• Memory layout: array — one contiguous block; linked list — scattered nodes connected by references

Neither structure is "better" in general — they are better at different jobs, and choosing between them is itself a core skill in data structures, not a detail to memorise and forget.

Where Linked Lists Actually Show Up

The "next" idea is not just a classroom toy. A browser's back/forward history is naturally a chain of visited pages where each page needs to know only what comes before and after it. An "undo" feature in a text or drawing app that lets you step backward through recent actions one at a time works on the same principle — you never need to jump to action number 47 directly, only to step to the previous or next one. A playlist's "play next" button only needs to know the current song's neighbour in the queue, not its numeric position — which is exactly why reordering a queue by dragging a song is cheap: it is a small number of reference changes, not a rewrite of the whole list. Even something as unglamorous as how an operating system cycles through running processes for their turn on the CPU (round-robin scheduling) is commonly organised as a circular chain of processes, each pointing to the next.

A Quick Look Ahead: Doubly and Circular Lists

The chain built in this chapter is a singly linked list: each node points forward only, so if you're standing at the 45-node, you have no way to get back to 82 without restarting from HEAD. A doubly linked list gives every node two references — next and prev — so you can walk in either direction, at the cost of one more reference field per node to maintain. A circular linked list makes the last node's next point back to the first node instead of to None, turning the chain into a loop with no true "end" — useful for exactly the round-robin CPU scheduling mentioned above. Both are direct extensions of everything covered here: same nodes, same references, same rewiring logic, just with one or two extra connections to keep consistent.

Check Your Understanding

1. Q: A singly linked list holds 30 -> 55 -> 12 -> 90 -> None. Write out the list after calling insert_after(prev_node, 40) where prev_node is the node holding 55.
   A: 30 -> 55 -> 40 -> 12 -> 90 -> None. Only 55's next and the new 40-node's next change.
2. Q: Why can't you write my_list[2] to fetch the third node of a linked list the way you would with a Python list, even though both structures store an ordered sequence of values?
   A: A linked list has no contiguous memory block and no index-to-address formula; the only known address is HEAD's, so reaching position 2 requires walking two hops through the next references — there is no direct-jump operation.
3. Q: In insert_after, why must new_node.next = prev_node.next execute before prev_node.next = new_node, and not after?
   A: If prev_node.next is overwritten first, the reference to the rest of the list (everything that used to come after prev_node) is lost before the new node has a chance to copy it, permanently disconnecting the remainder of the chain.
4. Q: A class has 500 students stored as an array, sorted by roll number. A new student is added at roll number 1 (the very front). How many existing values must shift? What if the same class were stored as a linked list and you already held a reference to the front?
   A: Array: all 500 existing values shift right by one, so 500 moves. Linked list: zero data moves — only HEAD needs to be redirected to the new first node, an O(1) operation.
5. Q: True or false: "A linked list storing 1,000 integers uses less total memory than an array storing the same 1,000 integers." Justify your answer.
   A: False. Each of the 1,000 nodes carries an extra next reference on top of its data, so the linked list uses strictly more memory than the tightly packed array, not less.

Summary

• An array stores elements in one contiguous memory block, so inserting or deleting in the middle forces every later element to shift — costing up to n moves.
• A linked list stores elements as scattered nodes, each holding data and a next reference to the following node; the list itself only tracks HEAD.
• Traversal always starts at HEAD and follows next references one hop at a time — there is no shortcut to an arbitrary position, unlike array indexing.
• Insertion and deletion at a known position rewire just one or two reference fields — constant work, independent of list size — which is the entire advantage over arrays.
• The trade-off: linked lists lose O(1) random access (misconception 1) and use more memory per element than arrays, not less (misconception 2).
• Singly linked lists point forward only; doubly linked lists add a prev reference; circular linked lists loop the last node back to the first — all built from the same node-and-reference idea covered here.

Practice Exercises

Now it is time to practice! Complete these challenges to solidify your understanding:

• Exercise 1: Write a short program that demonstrates the core concept from this chapter. Test it with at least 3 different inputs.
• Exercise 2: Find a real-world example where linked lists: dynamic data chains is used in an Indian company (like TCS, Infosys, Flipkart, or ISRO). Write a paragraph explaining the connection.
• Exercise 3: Create a mind-map connecting linked lists: dynamic data chains to at least 3 other topics you have studied.