Dynamic Implementation of Linked List

DSA, Database System & Operating System — Data Structure, Lists, Linked Lists and Trees, NEC licence examination syllabus (Nepal Engineering Council).

Dynamic Implementation of Linked List

Trading "instant access by index" for "grow forever, insert anywhere cheaply."

A linked list is built from individual nodes, each holding data plus a POINTER to the next node — there's no requirement that nodes sit next to each other in memory at all, unlike an array.

This is the fundamental tradeoff of this whole chapter: arrays give fast random access but expensive insertion/deletion; linked lists give cheap insertion/deletion (just repoint a pointer) but slow random access (must walk node-by-node from the start).

💡 One-liner: "Why can't you binary search a linked list efficiently, even though it might be sorted?" → Binary search needs instant access to the MIDDLE element, but a linked list requires walking node by node to reach any position — no shortcut to the middle exists.

The hidden cost nobody mentions

The array-versus-list trade-off is usually stated as random access against cheap insertion, which is correct but incomplete. There is a second effect that often dominates in practice.

Array elements sit next to each other in memory, so reading one pulls its neighbours into cache along with it. Linked-list nodes can be scattered anywhere, so each hop may cost a fresh memory fetch. This is why walking an array is frequently several times faster than walking a linked list of the same length, even though both are O(n).

💡 So "linked lists are better for insertion" carries an asterisk. Inserting is O(1) once you are holding the node — but finding that position is O(n), and the walk is cache-unfriendly. If you must search before every insert, the array often wins outright.

The pointer discipline that questions test

Insertion and deletion are exam favourites because the order of pointer updates matters. To insert node N after node P: first point N to P's successor, then point P to N. Do it the other way round and P's successor is lost before anything records it — the rest of the list is unreachable and leaked.

The same reasoning governs deletion: the predecessor must be made to point past the doomed node before that node is freed, or the link is read after release.

💡 Both operations need a reference to the previous node, which a singly linked list cannot give you from the node itself. That single limitation is the main practical argument for a doubly linked list — deletion becomes possible in O(1) given only the node to remove.

Syllabus points

Node, pointer-based linked list

Create a free account to tick topics off, take notes as you read, watch the video lessons and get a day-by-day study plan built around your exam date.