P-4.2 Linked Lists
You can implement a singly and doubly linked list, state which operations are genuinely cheaper than in an array, and explain why they are often slower in practice anyway.
Linked storage trades away indexing for cheap insertion and deletion at a position you already hold. The classical analysis says this makes it better than an array for insert-heavy work, and on modern hardware it frequently does not, because scattered nodes defeat the memory cache. Both facts are true and being able to hold them together is more useful than either one alone.
Work through these
A node holds a value and the address of the next node
The structure is a chain rather than a block, so it grows one node at a time without ever copying what is already there. This is the property arrays cannot offer.
NPTEL: Data Structures and Algorithms · CourseInsertion and deletion are constant time once you are there
Splicing a node in or out is a couple of assignments and no shifting. The catch is contained in the words once you are there, because getting there is a walk from the front.
There is no indexing, and finding the tenth element means walking
Without contiguous storage there is no arithmetic that jumps to a position, so every access by index is a traversal. Any algorithm that indexes repeatedly is the wrong fit.
Doubly linked lists, and what the second link buys
Storing the previous node as well lets you walk backwards and delete a node given only that node. The cost is another address in every node and two more assignments in every update.
Why the cache often makes an array faster despite the analysis
Processors fetch memory in blocks, so walking contiguous storage is far faster per element than following addresses scattered around the heap. Measured performance and operation counting disagree here, and measurement wins.
Sign in to keep your progress.
Free resources
We haven't checked most of these for screen reader use yet.
Links last checked 31 Aug 2026.
Stuck here?
Ask a mentor. A real person answers, and they can see exactly which topic you're on. Usually within a couple of working days.
Checking your session…
Topics shown in module order.