Printing and Looping

Section 27.6 Printing and Looping

Any algorithm that needs to work with elements other than the first one in our simple linked list will need to work its way through the list by following the next pointers from one node to the next.

🔗

For example, to print all the values in the list, we can start at the head node and repeatedly follow the next pointer to get to the next node, printing each node’s value. To keep track of where we are in the list, we can use a temporary pointer that starts at the head and moves through the list.

🔗

Assuming we call our pointer current, we can advance it to the next node by setting current = current->next;. That accesses the node that current points at, gets the memory address stored in its next member, and then updates the current pointer to point at that address.

🔗

Activity 27.6.1. Linked List Traversals.

The animation is set to print the list. Use > to step through the process.

🔗

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

🔗

Warning 27.6.1.

We never want to change the head pointer itself when traversing the list, because that would lose track of the list’s first node. Any loop logic will usually use a temporary pointer like the current in the animation to move through the list.

🔗

We don’t know in advance how many nodes are in the list, so we need a way to keep going until we reach the end. There are two conditions that we could use to determine when to stop:

Stop when the current pointer is nullptr, indicating we have moved past the last node.

🔗
Stop when the current pointer’s next pointer is nullptr, indicating the current node is the last node.

🔗

Both approaches work, but the first one is often simpler because it allows us to handle the last node in the same way as all the others. It also allows us to handle the case of an empty list more easily, since the current pointer will be nullptr right from the start.

🔗

Insight 27.6.2.

Doing current->next when current is nullptr will cause an error because you are trying to access a member of a null pointer.

🔗

If we are going to test or use current->next, we need to make sure that current is not nullptr first.

🔗

Our print function thus might look like:

🔗

template <typename T>
void SimpleLinkedList<T>::print() const {
    //current will point to each element in turn
    ListNode<T>* current = head;

    while(current != nullptr) {
        cout << current->data << " ";   //print current item
        current = current->next;        //advance to next
    }
    cout << endl;
}

Checkpoint 27.6.1.

Why do we not delete current at the end of the print function?

🔗

It does not “own” any of the memory it points to. It just temporarily points to nodes in the list.
Because it is a Node, not a pointer.
The memory will be automatically deleted when we do current = current->next.

🔗

You have attempted of activities on this page.

🔗

Prev Top Next