Kerala Plus Two Computer Science (DHSE): Linked Lists and Memory Management

Linked Lists and Memory Management

This domain tests dynamic node structures, pointer rewiring, and the lifetime rules of heap memory.

Linked list basics

• A node holds data and a next pointer. The list is accessed through head; the last node's next is nullptr.
• Unlike arrays, nodes need not be contiguous; insertion/deletion at a known position is O(1), but search is O(n).
• Traversal: for (Node *p = head; p != nullptr; p = p->next).

Dynamic memory

• new allocates on the heap and returns an address; delete frees one object, delete[] frees an array.
• Every successful new needs exactly one matching delete; otherwise a memory leak occurs.
• After delete p, set p = nullptr to avoid a dangling pointer.
• Deleting the same pointer twice is undefined behaviour.

Worked example

Insert 5 at the front: Node *n = new Node; n->data = 5; n->next = head; head = n;. Reasoning: the new node must point to the old first node before head is changed; reversing these two statements loses the rest of the list. For deletion of the head: Node *t = head; head = head->next; delete t;.

Traps

• Overwriting head before saving the old head.
• Forgetting to set the last node's next to nullptr, causing traversal to run into garbage.
• Using delete instead of delete[] for arrays.
• Accessing a node after freeing it.
• Confusing a node with a pointer to a node in declarations.