While nodes can be added, they should also be able to be deleted. They can be deleted from the front of a list, or within a list. For the first case, the first node in the list is deleted. We use pt, a temporary pointer, to point to the start of the list. The list itself is then modified to point to the second element of the list, represented by pt^.next.
1 pt := list; 2 list := pt^.next;
To delete a particular node in the list, the method is a little different. Here is the list of what to do to delete an “internal” node.
- Find the previous node of the node to be deleted. A node is usually identified by the data it contains.
- Change the next of the previous node.
- Free memory of the node to be deleted.
For the purpose of this example, we will assume that key is the data associated with the node to be deleted and prev (type link) represents the previous node.
1 pt := list; 2 while (pt <> NIL) and (pt^.data <> key) do 3 begin 4 prev := pt; 5 pt := pt^.next; 6 end; 7 prev^.next := pt^.next;
We again use pt, a temporary pointer, to point to the start of the list. The list is then traversed, while the end of the list has not been reached, and the data item of the current node does not equal key. At each iteration of the loop, prev is set to the current node, and the node pointer is advanced. When the loop exits, prev will contain the previous node. On line 7, the next field of the previous node is linked to the node following the one to be deleted.
Below this process is described in a visual manner:
In Fig.1A the node with the value 12 is marked to be deleted. In Fig.1B, the loop has exited with the node to be deleted, and its predecessor marked. In Fig.1C, the node is bypassed (Line 7), and Fig.1D shows the resulting shortened list.