Learning linked lists (v) – deleting a node

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.

  1. Find the previous node of the node to be deleted. A node is usually identified by the data it contains.
  2. Change the next of the previous node.
  3. 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:

Fig.1: Deleting a node from a linked list

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.

Imagination and tinkering

Some people wonder why kids these days have problems concentrating on things. I would suggest that some of the contributing factors are being inside too much, and spending too much time on computer devices. If you look back 50 years, many kids were outside building forts, and tree-houses. Even in cold weather. Or, maybe some were playing with their Atomic Energy Labs. One Saturday last winter it snowed, probably about 15cm. On Sunday it was a beautiful winters day outside – a perfect day to build a snow fort! How many kids were outside? Seemingly not many. A hundred years ago most kids didn’t have fancy toys, but they likely had a lot of imagination, and were able to build things with what they could find. Every boy was likely enamoured with toys like Meccano, where you could build anything.

Gilbert U-238 Atomic Energy Lab (1950-1951)

Along with Meccano there was The Meccano Magazine, where one could learn about building different things using Meccano. But this magazine was more than that, it was a gateway to achievements being made around the world in engineering, rail and air. But the magazine didn’t provide step-by-step instructions – just pictures. Consider the picture of the locomotive below:

meccano model of a locomotive
Reader submitted example of a Meccano model published in Dec. 1928. It is a model of a locomotive from the Swiss Rhaetian Railway.

An interested reader could construct this locomotive, but that would require the ability to reproduce the model from a single picture. How many children have the patience for such undertakings today?

Learning linked lists (iv) – inserting a node

Now we may want to add a node somewhere inside the list. This is where linked lists come into their own – you can’t just add an element to an array (in most languages, although newer languages are becoming more flexible). To add an element somewhere on the list, one has to traverse the list, using the code outlined in the previous post, create a new node, and “link in” the node between two existing nodes. Here is the list of what to do:

  1. Traverse the list to the node which will sit before the node to be inserted. This is the found node.
  2. Create the new node.
  3. Point the new node to where the found node is currently pointing to.
  4. Point the found node’s pointer to the new node.

For the purpose of this example, we will assume that pt is the (found) node after which a new node newp will be inserted.

1   new(newp);
2   newp^.data := 23;
3   newp^.next := pt^.next;
4   pt^.next := newp;

The new node is created on line 1, and the value 23 is assigned to its data value on line 2. Line 3 links the next field of newp, with the node currently being pointed to by pt. Finally in line 4, the node, pt is linked to the new node newp.

Here is what that process looks like in visual form:

Fig 1: Inserting a node into a linked list

In Fig.1A, the original list is shown. The found node is identified (pt), and the new node newp is created in Fig.1B. In Fig.1C the new node is inserted in between the found node, and the node that follows it in the original list. Fig.1D represents the new list.

Learning linked lists (iii) – traversing a list

In the previous post we built a small linked list. Now we probably want to iterate through it, and the simplest thing to do is to print out the list. For the purposes of accessing the list, we can create another variable pt, of type link, which allows us to move through the list. Here is the code to print out the values of all the nodes in the list. The first thing to do is to associate pt with the linked list list (line 1).

1   pt := list;
2   while pt <> NIL do
3   begin
4      writeln(pt^.data);
5      pt := pt^.next;
6   end;

The while loop iterates through the list, testing to ensure that the pointer is not nil, i.e. the end of the list has been reached. If a node exists, then the data value is printed out (line 4). Then the next node in the list is accessed (line 5). At the last node, the value of next will be NIL. This prints out the list in the reverse order, because remember, the first item input becomes the “tail” of the list.

Of course there are other ways one might want to traverse a list, for example to find a node with a particular value. This can be done by modifying the above traversal to incorporate a second condition. For example:

1   pt := list;
2   while (pt <> nil) and (pt^.data <> key) do
3      pt := pt^.next;

This basically traverses the list until the end trying to find the piece of data that matches the variable key.