Reviewing the efficiency of the linked lists
Let's review the efficiency of each method by review the Big O notation in terms of time of execution:
| Method | Singly | Doubly | Circular | Explanation |
append |
O(n) | O(1) | O(n) | In singly and circular lists, we must traverse to the end to append. Doubly lists have a tail reference for constant time append. |
prepend |
O(1) | O(1) | O(n) | All lists can add a new node as the head directly. However, in circular lists, we must update the last node's next pointer to the new head. |
insert |
O(n) | O(n) | O(n) | For all types, we need to traverse to the position to insert. |
removeAt |
O(n) | O(n) | O(n) | Similar to insertion, traversal to the position is required. Doubly lists have an optimization when removing the tail ( O(1) ), but this is less common than removing from an arbitrary position. |
remove |
O(n) | O(n) | O(n) | Searching for the data takes O(n) in all cases, then removal itself is either O(1) (if the node is found at the head) or O(n) (traversing to the node... |
