Linked List
see data structure
a list where each element points to the next (and optionally previous) element
time computational complexity:
| Singly-Linked | Doubly-Linked | |
|---|---|---|
| Search | O (*) |
O (*) |
| isEmpty | O ->1 |
O ->1 |
| Contains | O (*) |
O (*) |
| Insert / Remove / Peek at head | O ->1 |
O ->1 |
| Insert / Remove / Peek at tail | O (*) |
O ->1 |
| Insert / Remove / Peek at mid | O (*) |
O (*) |
representation Singly-Linked List
graph LR
HEAD --> E1(element) --> E2(element) --> E3(element) --> TAIL
representation Doubly Linked List
graph LR
HEAD --> E1(element) --> E2(element) --> E3(element) --> TAIL
TAIL --> E3 --> E2 --> E1 --> HEAD
applications
can be used to implement lists, queues and stacks because of their efficient insertion and deletion computational complexity
can be used in hash table › operations (separate chaining) implementations to deal with hash› collisions
often used in the implementation of adjacency lists for graphs