Practice question · True or false
Removing a node from a singly linked list is O(1) once you hold a reference to that node.
Hints
- What does unlinking a node actually require?
- You need the node before it.
Show the answer
False
Why
False. Unlinking needs the predecessor, whose next pointer must be redirected, and finding it in a singly linked list is an O(n) walk. A doubly linked list stores that back pointer and does make it O(1), which is the whole reason to pay for the extra pointer per node.
Practise Arrays, Lists, and Memory Layout
The app has 7 more questions on this lesson, and keeps your place in the course. Computer Science I is free to start.