Deletion
Deletion is very similar to insertion in terms of efficiency. To delete a node from the beginning of a linked list, all we need to do is perform one step: we change the first_node of the linked list to now point to the second node.
Let’s return to our example of the linked list containing the values "once", "upon", "a", and "time". If we wanted to delete the value "once", we would simply change the linked list to begin at "upon":
| | list.first_node = node_2 |
Contrast this with an array in which deleting the first element means shifting all remaining data one cell to the left, an efficiency of O(N).
When it comes to deleting the final node of a linked list, the actual deletion takes one step—we just take the second-to-last node and make its link null. However, it takes N steps to first get to the second-to-last node, since we need to start at the beginning of the list and follow the links until we reach it.
The following table contrasts the various scenarios of deletion for both arrays and linked lists. Note how it’s identical to insertion:
Situation | Array | Linked list |
|---|---|---|
Delete at beginning | Worst case | Best case |
Delete at middle | Average case | Average case |
Delete at end | Best case | Worst case |
To delete from the middle of the list, the computer must modify the link of the preceding node. The following example will make this clear.
Let’s say that we want to delete the value at index 2 ("purple") from the previous linked list. The computer finds index 1 and switches its link to point to the "green" node:
Here’s what the delete operation would look like in our class:
| | class LinkedList |
| | |
| | attr_accessor :first_node |
| | |
| | # rest of code omitted here... |
| | |
| | def delete_at_index(index) |
| | # If we are deleting the first node: |
| | if index == 0 |
| | # Simply set the first node to be what is currently the second node: |
| | self.first_node = first_node.next_node |
| | else |
| | current_node = first_node |
| | current_index = 0 |
| | |
| | # First, we find the node immediately before the one we |
| | # want to delete and call it current_node: |
| | while current_index < (index - 1) do |
| | current_node = current_node.next_node |
| | current_index += 1 |
| | end |
| | |
| | # We find the node that comes after the one we're deleting: |
| | node_after_deleted_node = current_node.next_node.next_node |
| | |
| | # We change the link of the current_node to point to the |
| | # node_after_deleted_node, leaving the node we want |
| | # to delete out of the list: |
| | current_node.next_node = node_after_deleted_node |
| | end |
| | end |
| | |
| | end |
After our analysis, it emerges that the comparison of linked lists and arrays breaks down as follows:
Operation | Array | Linked list |
|---|---|---|
Reading | O(1) | O(N) |
Search | O(N) | O(N) |
Insertion | O(N) (O(1) at end) | O(N) (O(1) at beginning) |
Deletion | O(N) (O(1) at end) | O(N) (O(1) at beginning) |
Search, insertion, and deletion seem to be a wash, and reading from an array is much faster than reading from a linked list. If so, why would one ever want to use a linked list?