When a chain beats a Python list

Linked lists Junior Python 3.13+ Reviewed 1 Nov 2026 By Best Latest Apps

Pick the fix

You must repeatedly remove items from the front of a long queue. Which choice is right?

Optionscollections.deque with popleft()A list with pop(0)Sort the list first

Choose an answer, then open Show answer below to check it.

Show answer

Answer: A collections.deque with popleft()

Right: O(1) at both ends.

Picking the structure by its cheap operations is the point; deque gives queue behaviour without writing a chain yourself.

Why not the others?

B A list with pop(0). Each call shifts every remaining item.
C Sort the list first. Sorting does not change the cost of removing from the front.

30-second answer

A Python list is a dynamic array: O(1) indexing and appends, but O(n) inserts and removals near the front. A chain gives O(1) insert and remove at a link you already hold, but O(n) to find a position and poor memory locality. In practice, chains win when you hold references to links and splice often, such as in LRU caches, and deque covers most queue needs.

Practise saying it · 45 s. No recording, just a timer

Compare chains with Python lists.

Say your answer out loud, then check which of these points you covered:

List: O(1) index, O(n) front insert
Chain: O(1) splice at a held link
Locality favours arrays

Deep dive

Arrays are usually faster in practice because neighbouring items sit together in memory.

Each link costs an object header plus a reference; a list stores one reference per item.

Interviews use chains mainly to test pointer handling, not because they are the best everyday choice.

Operation	Python list	Singly linked chain
Read item i	O(1)	O(i)
Append at the end	O(1) amortised	O(1) with a tail pointer
Insert at the front	O(n)	O(1)
Insert after a held link	O(n)	O(1)

Common mistakes

Claiming chain insertion is O(1) without saying you must already hold the link.
Using list.pop(0) in a loop, which is O(n) per call.

Senior take & follow-ups

Mention memory locality; it shows practical judgement.

Follow-up questions

Think of your answer first, then open the hint.

Which structure backs Python's deque?
Show hint
A doubly linked list of fixed-size blocks.
How does a UI list handle big updates?
Show hint
It computes a diff and applies inserts and moves in batches rather than rebuilding everything.

Similar on iOS: Value types vs reference types The iOS page contrasts Swift value and reference types; this page compares chains of references (links) with contiguous Python lists.

What each operation costs: Linked List · Singly Linked List · Doubly Linked List

From the author

DSA Master - Data & Algorithms

Free on iPhone and iPad: watch 50+ data structures and algorithms step through animations, run the code in the playground, and try the daily challenge.

Get it on the App Store

Suggest a fix if something here is wrong or out of date.