Week 9

Dynamic memory allocation

The following class represents a node in a linked list of integers:

class Node {
    public:
        Node(int num, Node* next=nullptr) :
            num {num}, next {next} {}

        int num;
        Node* next;
};

Each node contains an integer num and a pointer next to the next node in the list. If there is no next node, next should be nullptr.

Given a pointer to a node in a linked list, the following function prints the integers in the list (separated by spaces) starting from that node:

void print(Node* node) {
    while (node) {
        cout << node->num << ' ';
        node = node->next;
    }
    cout << '\n';
}

Exercise 9.1

(a) Write a function named push_front that takes a pointer to the first node of a linked list along with an integer, and adds a node containing that integer to the front of the list. If the list is empty, the pointer passed will be nullptr.

For example, the code

Node* list = nullptr;

push_front(list, 3);
print(list);

push_front(list, 2);
push_front(list, 1);
print(list);

should produce the output

3 
1 2 3 

Solution

Here is one possible solution.

void push_front(Node*& node, int num) {
    node = new Node(num, node);
}

---

(b) Write a function named pop_front that takes a pointer to the first node of a linked list and removes the node at the front of the list. If the list is empty, the function should do nothing.

For example, the code

Node* list = nullptr;

push_front(list, 2);
push_front(list, 1);
print(list);

pop_front(list);
print(list);

pop_front(list);
pop_front(list);
print(list);

should produce the output

1 2 
1 

Solution

Here is one possible solution.

void pop_front(Node*& node) {
    if (node) {
        Node* next_node = node->next;
        delete node;
        node = next_node;
    }
}

---

(c) Write a function named clear that takes a pointer to the first node of a linked list and removes all the nodes in the list. If the list is empty, the function should do nothing.

For example, the code

Node* list = nullptr;

push_front(list, 3);
push_front(list, 2);
push_front(list, 1);
print(list);

clear(list);
print(list);

clear(list);
print(list);

should produce the output

1 2 3 

Solution

Here is one possible solution, assuming that pop_front has been defined as in part (b).

void clear(Node*& node) {
    while (node) {
        pop_front(node);
    }
}