Practice Flashcards
Flip to reveal answersWhat does each node in a singly linked list hold?
Track your progress — Sign up free to save your progress and get smart review reminders based on spaced repetition.
All 5 Flashcards — Evaluating linked lists
Sign up free to track progress and get spaced-repetition review schedules.
Question
What does each node in a singly linked list hold?
Answer
A **value** and a **reference to the next node**. Nothing else, and no node needs to sit beside another in memory.
Question
Why is reaching the nth element of a linked list O(n)?
Answer
There is no calculation that locates a node — you must start at the head and **follow every reference** in turn.
Question
Singly, doubly, circular — what is the difference?
Answer
**Singly** points forwards only. **Doubly** points both ways, at the cost of a second reference per node. **Circular** links the last node back to the first, so there is no null end.
Question
What is the linked-list trade-off?
Answer
It gives up **direct access** (O(n) to reach position n) and gains **cheap insertion and deletion** (O(1) once in position), plus a size that grows and shrinks.
Question
Why can an array beat a linked list even when complexity says otherwise?
Answer
Array elements are **contiguous**, so reading one pulls its neighbours into cache. Linked-list nodes are scattered, so each hop risks a cache miss.
Read the notes
Full study notes for Evaluating linked lists
Topic 8.1 hub
Fundamentals of ADTs
More from Topic 8.1
All flashcards in this topic
Computer Science exam skills
Paper structures & tips
Track your progress with spaced repetition
Sign up free — Aimnova tells you exactly which cards to review and when, so you remember everything before your IB exam.
Start Free