Skip to main content

Welcome to Programming and Data Structures

Andrew Scholer

Section 27.4 Inserting Values

Adding a value to our list means constructing a new node and inserting it into the existing chain of nodes. The natural place to insert a new node is at the start of the list, as that is the easiest place to access.
🔗
If we knew the list was empty, this would be easy: we would just create the new node and set the head pointer to point to it:
🔗
Listing 27.4.1. Flawed insertStart Implementation
🔗
void SimpleLinkedList<T>::insertStart(T value) {
    // allocate new node on the heap. Store the address in "newNode"
    ListNode<T>* newNode = new ListNode<T>(value);
    // set the list's head pointer to point to the new node
    head = newNode;
}
When we leave insertStart, the newNode variable goes out of scope. But the node it was pointing to is still allocated on the heap, and the list’s head pointer is still pointing to it. So the list still has access to the new node.
🔗
myList1 has a head pointer. It points to a node containing 6.🔗
Figure 27.4.2. Memory of main after calling myList1.insertStart(6).
🔗
But what if there is already something pointed at by head? Consider the figure below. We have started the insert process and created a new node to store the value 6. But head is already pointing to a node containing 10. We don’t want to just change head to point to the new node, because then we would lose track of the 10 node:
🔗
Head points to a node containing 10, and newNode points to a node containing 6.🔗
Figure 27.4.3. Adding a new node with 6 while a node with 10 is the existing first node
🔗
To avoid losing track of the old first node, we have to do two things:
  • Set the new node’s next pointer to point to the old first node (the one that head is currently pointing to).
    🔗
  • Then set head to point to the new node.
    🔗
A full implementation of insertStart that handles both the empty and non-empty list cases looks like this:
🔗
Listing 27.4.4. Correct insertStart Implementation
🔗
template <typename T>
void SimpleLinkedList<T>::insertStart(T value) {
    // allocate new node on the heap. Store the address in "newNode"
    ListNode<T>* newNode = new ListNode<T>(value);
    // set the new node's next pointer to point to the old first node
    newNode->next = head;
    // set the list's head pointer to point to the new node
    head = newNode;
}
This handles both the empty and non-empty list cases. If the list is empty, then head is nullptr, so the line newNode->next = head; sets the new node’s next pointer to nullptr, which is correct for a one-item list. If the list is not empty, then head points to the old first node, and we set the new node’s next pointer to point to that old first node. We should end up with something that looks like this:
🔗
Head points to a node containing 6 as does newNode. The new node’s next pointer points to the node containing 10.🔗
Figure 27.4.5. The result of inserting 6 at the start of a list that had 10.
🔗
As we leave the insertStart function, the newNode variable goes out of scope, but the linked list still has access to both nodes via the head pointer.
🔗

Activity 27.4.1. Linked List Insertion.

The animation is set to insert the value 6 at the start of the list. Press the > button to step through the insertion process.
🔗
When it finishes, type another value into the Value textbox and press Insert Front to start adding another value and then continue stepping.
🔗

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...
      🔗
    🔗
    🔗
🔗
🔗
🔗

Checkpoint 27.4.1.

Build an alternate version of the insertStart function that correctly inserts a new node at the beginning of the list. You will not use all the blocks.
🔗
🔗
You have attempted of activities on this page.
🔗
PrevTopNext