-
Notifications
You must be signed in to change notification settings - Fork 43
Data Structures
Avery Lieu edited this page Dec 7, 2016
·
19 revisions
Definition: A linear collection of nodes in which each node links to the next node.
Each node has a single pointer to the next node.
- Need constant time insertion or deletion
- Only at head (front of list)
- Inserting elements is easier in singly linked list that in doubly linked list
- Unknown number of elements
- No need for random access
- Need linked list and memory is a concern
- Requires less memory than doubly linked list
| Average | Worst | |
|---|---|---|
| Access | θ(n) | O(n) |
| Search | θ(n) | O(n) |
| Insertion | θ(1) | O(1) |
| Deletion | θ(1) | O(1) |
Each node has two pointers, one to the previous node and one to the next node.
- Need constant time insertion or deletion
- Only at head or tail (front or back of list)
- Doubly linked list deletion is faster that singly linked list deletion, except when deleting the head
- Unknown number of elements
- No need for random access
| Average | Worst | |
|---|---|---|
| Access | θ(n) | O(n) |
| Search | θ(n) | O(n) |
| Insertion | θ(1) | O(1) |
| Deletion | θ(1) | O(1) |