If you aren't familiar with Big O Notation, read the article in the Simple Wiki. Don't get caught in the details, only try to grasp the concept.
Simple example: If I have a todo list with pen and paper and I want to add a new todo to the end, that's
O(1). Why? No matter how long the list actually is, adding a new todo to the end always requires the same amount of work.
Today we start with a simple one: Singly Linked List.
Singly Linked List
- simple example in real life: a treasure hunt, where you have a starting point and have to seek places and solve riddles in a particular order; the current place knows about the next place, but the current place doesn't know about the previous place
What is a Singly Linked List?
- consists of nodes
- each node has a value and a pointer to the next node (or null at the end of the list)
- has a head (=start), a tail (=end) and a length
- has no index like an Array
- "singly" because only one connection to another node (the next one)
- access has always to start from the start (
- insertion is cheap (
- deletion can be cheap (
What is an Array?
- every element has an index
- accessed is cheap (
O(1)) (every element has an index)
- insert and delete can be expensive (
O(N)) (index has to be shifted)
Big O of Singly Linked List
When to use a Singly Linked List instead of an Array?
- if you insert data often (SLL:
- if you delete data at the head often (SLL:
When NOT to use a Singly Linked List instead of an Array?
- if you access data often (Array: