Memory Management

Section 27.7 Memory Management

Because linked lists are responsible for managing dynamic memory (using new to create nodes), they also are responsible for properly deleting that memory and doing deep copies of that memory when needed. This means we should be implementing a destructor, copy constructor, and copy assignment operator (the Rule of Three).

🔗

Subsection 27.7.1 Destruction

If the linked list itself is destroyed, say by going out of scope, we need to make sure that all the nodes in the list are deleted to avoid memory leaks. This of course is the responsibility of the destructor.

🔗

We might also want to provide a method to clear the list explicitly, which would delete all the nodes and leave the list empty. If so, the destructor can call this method to avoid duplicating code.

🔗

template <typename T>
LinkedList<T>::~LinkedList() {
    clear();
}

There is no easy way to delete all the individual nodes. If we do delete head;, it would only delete the first node in the list. (And the rest of the nodes would then be unreachable and cause a memory leak.) Instead, we need to remove the nodes one by one until the list is empty.

🔗

Insight 27.7.1.

Every new call requires a delete call. We allocated each node individually using new, so we must delete each node individually as well.

🔗

Fortunately, we can use a loop to repeatedly remove the first node until the list is empty. The logic is pretty simple:

🔗

clear():
  while(head != nullptr):
    removeStart()

This loop will keep calling removeStart() until the head pointer is nullptr, indicating the list is empty. Each call to removeStart() will delete the first node in the list, so by the time the loop finishes, all nodes will have been deleted.

🔗

Note 27.7.2.

It is worth stopping to think about the efficiency of this approach. In particular, we should make sure that removeStart() doesn’t represent a costly operation that would make this approach inefficient. Although we have not analyzed the efficiency of removeStart() yet, it is not hard to see that it runs in constant time—it has no loops or recursive calls. So calling it is no more expensive than doing the equivalent work directly in clear.

🔗

Activity 27.7.1. Linked List Clear.

The animation is set to clear the list by deleting nodes until head is null. 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...
  
  🔗
🔗
🔗

🔗

Subsection 27.7.2 Copying

When copying a linked list, either using a copy constructor or an assignment operator, we need to make sure to perform a deep copy of the nodes. We can’t just do something like newList.head = oldList.head; because we would end up with a shallow copy where both lists share the same nodes, leading to potential issues like double deletion.

🔗

The stack shows two lists, myList and other. Both lists have head pointers that point to the same node on the heap.🔗 — Figure 27.7.1. A shallow copy. The list `other` shares the same nodes as the original list.
🔗

The stack shows two lists, myList and other. Both lists point to different chains of nodes that have the same values.🔗 — Figure 27.7.2. A deep copy. The list `other` has its own separate nodes.
🔗

To perform a deep copy, we can iterate through the nodes of the original list and create new nodes for the new list with the same data values. Each new node will need to be added to the end of the list of copied nodes we are building. Currently, this will be challenging since we don’t have an easy way to add nodes to the end of the list.

🔗

We could make an efficient implementation by tracking the location of what node we are copying in the other list (sourceCur) and the last node in the new list (copyCur).

🔗

The stack shows two lists, myList and other. Both lists point to different chains of nodes. The pointers sourceCur and copyCur indicate the current nodes being copied and the last node in the new list, respectively.🔗 — Figure 27.7.3. Making a deep copy using current pointers in both the source and destination lists. When sourceCur advances to the next node, we will make a new node and copyCur will be updated to point.
🔗

Our algorithm might look something like:

🔗

if (other.head == nullptr) {
    head = nullptr // If the original list is empty, the new list should also be empty
    return
}
ListNode* sourceCur = other.head      // Pointer to traverse original list
head = new Node(other.head->data);    // Create the first node of new list
ListNode* copyCur = head;             // Pointer to track last node in new list
while (sourceCur->next != nullptr) {
    sourceCur = sourceCur->next;              // advance to the next node in the source
    copyCur->next = new Node(sourceCur->data);
    copyCur = copyCur->next;                  // advance copyCur to the new last node
}

However, we will soon improve our linked list to simplify inserting at the end of a list. That will allow us to simplify this logic significantly. In this simple linked list, we will just disable copying by deleting the copy constructor and assignment operator. That way we won’t accidentally create shallow copies of our list and cause memory management issues. To do so, we simply set each of them to delete in the class definition:

🔗

template <typename T>
class SimpleLinkedList {
    //...
    public:
        // Disable the default copy constructor and assignment operator to prevent shallow copies
        SimpleLinkedList(const SimpleLinkedList<T>& other) = delete;
        SimpleLinkedList<T>& operator=(const SimpleLinkedList<T>& other) = delete;
    //...
};

🔗

Checkpoint 27.7.1.

Trace this attempt at a copy constructor and identify its flaw:

🔗

SimpleLinkedList(const SimpleLinkedList<T>& other) {
  ListNode<T>* copyCur = other.head;
  while (copyCur != nullptr) {
    this->insertStart(copyCur->data);
    copyCur = copyCur->next;
  }
}

The elements will get added in reverse order.
insertStart is too inefficient to use as a helper.
It would skip the first element of the original list.
It would skip the last element of the original list.

🔗

You have attempted of activities on this page.

🔗

Prev Top Next