Linked list
The other commonly used form of a list is the linked list. It has a collection of nodes with each node containing the element and a link pointing to the next node in the list. In contrast to the dynamic array, the linked list is not contiguous and allows for faster performance when adding or deleting from the middle.
| Pros | Cons |
|---|---|
| No max size (besides memory) | Bad performance when indexing |
| Inserting or deleting in middle of list can be a constant-time operation if we have a pointer to the changing node. | Extra overhead to store the nodes |
| No data locality/cache performance boost |
Implementations
Python: Internal Implementation
linked_list = collections.deque([1, 2, 3])
linked_list.appendleft(0) # [0, 1, 2, 3]
linked_list.append(4) # [0, 1, 2, 3, 4]linked_list.popleft() # [1, 2, 3, 4]
linked_list.pop() # [1, 2, 3]
Java: LinkedList
List<Integer> ll = new LinkedList<>(Arrays.asList(1, 2, 3));
ll.addFirst(0); // [0, 1, 2, 3]
ll.addLast(4); // [0, 1, 2, 3, 4]ll.pollFirst(); // [1, 2, 3, 4]
ll.pollLast(); // [1, 2, 3]
C++: list
std::list<int> linked_list = {1, 2, 3};
linked_list.push_front(0); // [0, 1, 2, 3]
linked_list.push_back(4); // [0, 1, 2, 3, 4]linked_list.pop_front(); // [1, 2, 3, 4]
linked_list.pop_back(); // [1, 2, 3]
| Operations | Worst | Average |
|---|---|---|
| Delete (Beginning) | O(1) | |
| Delete (Middle/End - known element) | O(1) | |
| Delete (Middle/End - unknown element) | O(n) | |
| Index | O(n) | |
| Insert (Beginning) | O(1) | |
| Insert (Middle/End - known element) | O(1) | |
| Insert (Middle/End - unknown element) | O(n) |
