front insertion
Adding an item at the start of a sequence rather than the end.
In more detail
On a Python list, list.insert(0, x) shifts every existing element one slot right, so it costs O(n) and a loop of them costs O(n^2). A linked list or deque adds at the front in O(1). This single operation is often what decides between list and deque.
Related terms
- Python list — Python's built-in ordered, growable sequence, implemented as a dynamic array of pointers to objects.
- deque — A double-ended queue: a sequence that adds and removes items at either end in O(1) time; Python provides it as collections.deque.
- linked list — A sequence made of nodes scattered in memory, each holding a value and a pointer to the next node.
Taught in
- Bloom Filters: Membership Without The Data — Algorithms & Data Structures for Working Engineers
- Arrays: Contiguous Memory And Constant-Time Access — Algorithms & Data Structures for Working Engineers
- Linked Lists: Nodes, Pointers And Sentinels — Algorithms & Data Structures for Working Engineers
- Stacks And Queues: Last In Or First In — Algorithms & Data Structures for Working Engineers
- Deques And Ring Buffers — Algorithms & Data Structures for Working Engineers
- Choosing The Right Sequence — Algorithms & Data Structures for Working Engineers