Removing the First Node

Section 27.5 Removing the First Node

Now that we have some data, we need to be able to remove it. In a linked list, the easiest place to work is at the start of the list as that is where we have direct access via the head pointer. So we will focus on removing the first node.

🔗

Two things need to happen when we remove the first node from a linked list:

We need to update the head pointer so that it points to the second node in the list (or to nullptr if there is no second node).

🔗
We need to delete the old first node to free up the memory it was using.

🔗

🔗

Activity 27.5.1. Linked List Remove Start.

The animation is set to remove the first node from the list. Use > to step through the removal process. Then press Delete Front and continue stepping to delete the second node.

🔗

Instructions.

When the > button is highlighted, an animation is prepared to run. Use the Step button to step through the animation one step at a time.

🔗

When no animation is in progress, you can use the data controls to start a new animation.

🔗

You can click and drag on the animation area to pan around. Use the Ctrl + mouse wheel (or touchpad scroll gesture) while over the animation area to zoom in and out.

🔗

Core Controls.
- << : Skip to the beginning of the animation.
  
  🔗
- < : Step backwards one step in the animation.
  
  🔗
- > : Step forward one step in the animation.
  
  🔗
- >> : Skip to the end of the animation.
  
  🔗
- Auto Step Speed Set to anything other than off to automatically step through the animation at the selected speed.
  
  🔗
- Zoom Set the zoom level. You can also use Ctrl + Mouse Wheel to zoom in and out.
  
  🔗
🔗
🔗
Data Controls.
- Value Use this area to enter a value when inserting, finding, deleting, etc...
  
  🔗
🔗
🔗

🔗

Notice that we need a pointer to keep track of the node that we will be deleting after we update head. If we just do head = head->next;, we will lose the address of the old first node and will not be able to delete it:

🔗

Head points to a node containing 10 as does newNode. The 6 node is now unreachable.🔗 — Figure 27.5.1. The 6 node is unreachable after updating head.
🔗

If we try to delete the head node without saving a pointer to the next node, we are in even worse shape because we will lose the address of the 10 node:

🔗

Head points to a bad address. The 10 node is now unreachable.🔗 — Figure 27.5.2. The 10 node is unreachable after deleting the 6 node.
🔗

So, as the animation shows, we need to:

Save a pointer to the node we want to delete.

🔗
Update the head pointer to point to the next node.

🔗
Delete the old first node using the saved pointer.

🔗

🔗

Right before deleting the old first node, the list looks like this:

🔗

toDelete points at the node we will delete. Head points to the next node.🔗 — Figure 27.5.3. toDelete points at the node we will delete. Head points to the next node.
🔗

We then delete the node that toDelete is pointing at. Then, as we leave the removeStart function, the toDelete variable goes out of scope. As long as we have called delete toDelete; before leaving the function, the memory used by the deleted node will also have been cleaned up.

🔗

This logic works for both the case where there are multiple nodes in the list and the case where there is only one node in the list. If there is currently just one node in the list, head will end up pointing to nullptr, which correctly indicates that the list is now empty.

🔗

A linked list with a single node. The head pointer points to the node containing 10, and head->next is nullptr.🔗 — Figure 27.5.4. A list with one node. `head->next` is `nullptr`. When our remove copies that to head as node is deleted, the final state will be correct.
🔗

Checkpoint 27.5.1.

Implement the removeStart function for our SimpleLinkedList.

🔗

void SimpleLinkedList<T>::removeStart() {
---
  ListNode<T>* toDelete = head;
---
  head = head->next;
---
  delete toDelete;
---
}

🔗

You have attempted of activities on this page.

🔗

Prev Top Next