Linked Lists
Nodes joined by pointers · grows one node at a timeA linked list stores each value in its own node, and every node points to the next one. Inserting or deleting only changes a few arrows — but to reach a node you must walk from the head. Switch between singly, doubly, circular and doubly circular lists below and watch the pointers move, then see a real use: storing and adding, subtracting and multiplying polynomials.
- Singlydata | next → … → NULL
- Doublyprev | data | next
- Circularlast node → head
- Doubly circularhead.prev = last · last.next = head
- Polynomialcoef | exp | next
- Current
- Comparing
- New / found
- Removing
- Changed link
- Removed link
Ready
Keyboard: ← → step · Space play / pause · R reset · Esc exit classroom mode
Polynomials with linked lists
A polynomial such as 3x³ + 2x + 5 can have gaps (no x² term) and any length, so an array wastes space or needs a big size.
A linked list stores one node per term — coef | exp | next — sorted from the highest exponent down.
Adding two polynomials becomes a merge of two sorted lists. Type your own polynomials and try each operation.
- Current
- Comparing
- New / updated
- Removing
- Changed link
Ready
Write terms like 3x^3 -x 7 · up to 4 terms, exponents 0–5 · keyboard shortcuts work on the visualizer you used last.
Every operation, in plain steps
These are exactly the steps the visualizer animates.
What is a node?
Each node stores a value (data) and a pointer (next) to the following node. The list only remembers where the first node is — the head. In a singly list the last node points to NULL. A doubly node also has a prev pointer, and in a circular list the last node points back to head. A doubly circular list does both: head.prev is the last node and last.next is head. For polynomials the node holds a whole term: a coefficient and an exponent.
// Singly and circular lists
struct Node {
int data; // the value
struct Node *next; // address of the next node
};
// Doubly and doubly circular lists
struct DNode {
struct DNode *prev; // address of the previous node
int data;
struct DNode *next;
};
// Polynomials: one node = one term, e.g. 3x^2
struct Term {
int coef; // 3
int exp; // 2
struct Term *next; // the term with the next lower exponent
};
struct Node *head = NULL; // empty list
Insert at beginning
- Create a new node with the value.
- Point the new node to the current head.
- Move head to the new node.
- Only 2 pointer changes — O(1).
Insert at end / position
- Create a new node.
- Walk with temp to the node before the spot.
- newNode.next = temp.next (do this first!).
- temp.next = newNode.
Delete a node
- Walk with temp to the node before the target.
- Point temp.next past the target.
- Free the target node's memory.
- Deleting the head is O(1) — just move head.
Reverse
- Keep three pointers: prev, curr, next.
- Save next = curr.next.
- Flip the link: curr.next = prev.
- Move prev and curr one step; finally head = prev.
Doubly: two directions
- Every node also has a prev pointer.
- Every insert or delete fixes BOTH next and prev.
- You can walk backward from the last node.
- Delete needs no "node before" walk — use prev.
Circular: no end
- The last node points back to head, not NULL.
- Loops stop when curr comes back to head.
- Changing head means updating the last node too.
- A single node points to itself.
Doubly circular: no walking
- head.prev is the last node, and last.next is head.
- So the last node is found in O(1) — no loop.
- Insert or delete at either end changes 4 pointers.
- A single node points to itself in both directions.
Polynomial: one node per term
- Each node is [coef | exp | next], e.g. 3x² = [3 | 2].
- Keep the list sorted: highest exponent first.
- One node per exponent — like terms are combined.
- A term with coefficient 0 is never stored.
Polynomial: add or subtract
- Put p on P and q on Q, like merging two sorted lists.
- Higher exponent: copy that term, move that pointer.
- Equal exponents: add (or subtract) the coefficients; skip the term if the result is 0.
- When one list ends, copy the rest of the other.
Polynomial: multiply
- Take every term of P and multiply it by every term of Q.
- Multiply the coefficients, ADD the exponents.
- Insert each product into the sorted result.
- If its exponent is already there, add the coefficients instead.
Polynomial: evaluate P(x)
- Start with sum = 0 and curr = head.
- For each node compute coef × x^exp.
- Add it to sum and move to the next node.
- When curr is NULL, sum is P(x).
Pseudocode
Language-independent steps. The visualizer shows the same logic in C, Python and Java.
How fast is each operation?
n = number of nodes. Every list operation uses O(1) extra space. For polynomials, m and n are the numbers of terms in P and Q.
| Operation | Best | Average | Worst | Speed |
|---|---|---|---|---|
| Insert at beginning | O(1) |
O(1) |
O(1) |
Instant |
| Insert at end | O(n) |
O(n) |
O(n) |
Grows with n |
| Insert at position | O(1) |
O(n) |
O(n) |
Grows with n |
| Delete at beginning | O(1) |
O(1) |
O(1) |
Instant |
| Delete at end | O(n) |
O(n) |
O(n) |
Grows with n |
| Search | O(1) |
O(n) |
O(n) |
Grows with n |
| Access i-th node | O(1) |
O(n) |
O(n) |
Grows with n |
| Reverse | O(n) |
O(n) |
O(n) |
Grows with n |
| Doubly circular: insert / delete at either end | O(1) |
O(1) |
O(1) |
Instant |
| Polynomial: add or subtract (m and n terms) | O(m + n) |
O(m + n) |
O(m + n) |
Grows with n |
| Polynomial: multiply (m and n terms) | O(m · n) |
O(m · n · (m + n)) |
O(m · n · (m + n)) |
Grows with n |
| Polynomial: evaluate P(x) | O(n) |
O(n) |
O(n) |
Grows with n |
Singly vs Doubly vs Circular vs Doubly circular
| Singly | Doubly | Circular | Doubly circular | |
|---|---|---|---|---|
| Pointers per node | next | prev + next | next | prev + next |
| Last node points to | NULL | NULL | head | head (and head.prev = last) |
| Walk backward? | No | Yes | No | Yes — and it wraps around |
| Insert at beginning | O(1) | O(1) | O(n) — must update the last node* | O(1) — head.prev is the last node |
| Insert / delete at the end | O(n) | O(n) | O(n) | O(1) — head.prev is the last node |
| Delete a node you already have | O(n) — need the node before it | O(1) — use prev | O(n) — need the node before it | O(1) — use prev |
| Extra memory | 1 pointer per node | 2 pointers per node | 1 pointer per node | 2 pointers per node |
| Typical use | Stacks, simple lists | Browser back / forward, undo & redo | Round-robin turns, playlists on repeat | Music player (next, previous, repeat), rotating schedules |
* With an extra tail pointer, a circular list can insert at the beginning in O(1). A doubly circular list needs no tail pointer: head.prev already is the tail.
Polynomials: array vs linked list
| Array (one slot per power) | Linked list (one node per term) | |
|---|---|---|
| Stores 5x¹⁰⁰ + 3 | 101 slots, almost all zero | 2 nodes |
| Size needed | Highest exponent + 1 | Number of terms |
| Add two polynomials | O(highest exponent) | O(m + n) — only the real terms |
| Coefficient of xᵏ | O(1) — poly[k] | O(n) — walk the list |
| Best for | Dense polynomials (most powers present) | Sparse polynomials (few terms, big gaps) |
Neither is always better: a list wins when most powers are missing, an array wins when most are present.
Array vs Linked List
| Array | Linked List | |
|---|---|---|
| Memory | One block, side by side | Nodes anywhere, joined by pointers |
| Size | Fixed capacity | Grows and shrinks freely |
| Access the i-th element | O(1) — calculate the address | O(n) — follow pointers from head |
| Insert at the front | O(n) — shift everything | O(1) — change 2 pointers |
| Extra memory | None | One pointer per node |
Check your understanding
Answer each question — you will see the explanation straight away.
What does the next pointer of the LAST node hold?
In a singly linked list the last node points to NULL — that is how we know the list has ended.
What is the time complexity of inserting at the beginning of a linked list?
Only two pointers change (newNode.next and head), no matter how long the list is.
Inserting a new node after temp: which step must happen FIRST?
If temp.next changed first, we would lose the address of the rest of the list. Connect the new node to the rest first.
Why can't a linked list jump straight to the 5th node like an array can?
Nodes can be anywhere in memory. The only way to reach one is to start at head and follow the pointers — O(n).
In a doubly linked list, what does head.prev hold?
Nothing comes before the first node, so its prev pointer is NULL (just like the last node's next).
How does a loop over a circular linked list know when to stop?
There is no NULL at the end of a circular list. We stop when we are back where we started — at head.
In a doubly circular linked list with 4 nodes, what does head.prev hold?
The list is a circle in both directions: last.next is head, and head.prev is the last node.
Which operation is O(1) in a doubly circular list, but O(n) in a singly circular list that has no tail pointer?
In the doubly circular list head.prev is the last node, so we never have to walk to it. The singly circular list must loop until last.next is head.
Which fields does one node of a polynomial linked list hold?
Each node is one term: its coefficient, its exponent, and a pointer to the term with the next lower exponent.
Adding 3x² + 2x and 5x + 1: both pointers reach a term with exponent 1. What happens?
Equal exponents are like terms, so we add the coefficients (2 + 5 = 7) and store a single node. If the sum were 0 we would store nothing.
Why is a polynomial list kept sorted by exponent?
With both lists sorted the same way, comparing the two current exponents tells us which term comes next — just like merging two sorted lists.
Multiplying the terms 3x² and 4x³ gives which term?
Multiply the coefficients (3 × 4 = 12) and ADD the exponents (2 + 3 = 5).
Linked Lists quiz
Test yourself: 5 questions, 70% to pass. Create a free account to take the quiz, save your progress and work towards the certificate.