Linked Lists
dsa.fetehadin.com4.1 Pointers, new/delete & the Heap
A pointer holds an address. new asks the heap for memory that lives until you delete it. Master this and linked lists become easy.
&x, *p, p->field | O(1) |
new / delete one object | O(1) (amortised; done by the allocator) |
| Stack memory | automatic: freed when the function returns |
| Heap memory | manual: lives until delete |
- ✗Dereferencing
nullptror an uninitialised pointer, which crashes (segmentation fault). - ✗Using memory after
delete(dangling pointer). Set the pointer tonullptrright after. - ✗
new[]paired withdeleteinstead ofdelete[].
4.2 Singly Linked List
Nodes on the heap, each pointing to the next. Insert at front, end or a position, delete by value, search and traverse, plus the dummy-node trick and the classic pitfalls.
| Insert at front | O(1) |
| Insert at end | O(n), or O(1) with a tail pointer |
| Insert at position k | O(k) |
| Delete by value / search | O(n) |
| Access the i-th item | O(n): no random access |
| Space | O(n) plus one pointer per node |
- ✗Losing the list by updating
headbefore linking the new node (head = n;first). - ✗Dereferencing
temp->nextwithout checkingtemp != nullptr. - ✗Forgetting the empty-list and delete-the-head special cases.
4.3 Doubly Linked List
Each node points both forward and backward. You can walk in both directions and delete a node knowing only its address, at the cost of one extra pointer per node.
| Insert / delete at front or end (with tail) | O(1) |
| Delete a node you already have a pointer to | O(1): no need to find prev |
| Search / delete by value | O(n) |
| Traverse backward | O(n): impossible in a singly list without extra memory |
| Space | O(n), with 2 pointers per node |
- ✗Updating
nextbut forgettingprev(or the reverse). Each insert or delete touches both directions. - ✗Forgetting
cur->next->prevwhencur->nextisnullptr(deleting the tail) → crash. - ✗Not updating
tailwhen deleting the last node.
- Pointer:
- A variable that stores a memory address.
- Heap (memory):
- Memory for dynamic allocation with new/delete. Lives until you free it.
- Memory leak:
- Heap memory that is no longer reachable but was never deleted.
- Dangling pointer:
- A pointer to memory that has already been freed.
- Node:
- One element of a linked structure: data plus pointer(s) to other nodes.
- Head:
- Pointer to the first node of a linked list.
- Dummy (sentinel) node:
- A fake node placed before the head so every real node has a predecessor.
- Doubly linked list:
- Each node has both next and prev pointers, allowing backward traversal and O(1) delete given a node.