Nodes with pointers allow cheap insertion and deletion.
A linked list stores nodes with data and pointers to the next (and previous) node. Insertion and deletion at a known node are O(1), but access by index is O(n) and cache locality is poor. Variants: singly, doubly and circular lists.
A music playlist with next and previous track uses a doubly linked list.
Linked lists allow fast insertion and removal at known positions without moving other items, which helps when data changes often.
Nodes with pointers allow cheap insertion and deletion.
Linked lists allow fast insertion and removal at known positions without moving other items, which helps when data changes often.
Access by index is slow because you must follow pointers from the start, and each node uses extra memory for the pointer.
They appear inside operating systems, caches and language runtimes, though arrays are often faster for simple data.
Typical applications include implementing a playlist where songs are added and removed frequently, building a free list in a memory allocator and storing a chain of events that changes order often.
Study "Stacks and queues" first (topic 19 of 104 in Software & Computing). It covers the groundwork this topic builds on.
Head and tail pointers. Reversal in O(n). Dummy nodes simplify code.
A music playlist with next and previous track uses a doubly linked list.
The next topic is "Hash tables", which builds directly on this one.
It is classed as Beginner in Software & Computing (topic 20 of 104). It is an entry-level topic. It relies only on basic school mathematics and the ideas introduced earlier in this discipline.
Want to practise? Open the interactive course for quick checks, quizzes, simulations and progress tracking.