+ 12
There are a few steps to deleting a specific element from the list:
Find the node with the element (if it exists).
Remove that node.
Reconnect the linked list.
Update the link to the beginning (if necessary).
The order in which we perform these steps will depend on how we implement the deletion operation.
Note:Â For simplicity, if there are two elements with the value we want, we'll just remove the first one.
Finding the node in question is a matter of traversing the list and looking at each node's element.
Reconnecting the list once a node is to be removed is more interesting. Let's consider at least 3 cases:
Removing a node from the beginning.
Removing a node from the middle.
Removing a node from the end.
Removing from the beginning
When removing the node at the beginning of the list, there is no relinking of nodes to be performed, since the first node has no preceding node.
However, we must fix the pointer to the beginning of the list
Removing from the middle
Removing a node from the middle requires that the preceding node skips over the node being removed.
This means that we need some way to refer to the node before the one we want to remove.
Removing from the end
Removing a node from the end requires that the preceding node becomes the new end of the list (i.e., points to nothing after it).
Note that the last two cases (middle and end) can be combined by saying that "the node preceding the one to be removed must point where the one to be removed does."