ETH_Informatik/Informatik_I/Exercise_11/Task_3

[Hidden tests][Exam 2019.02 RW] Sorted List

• Sorted Linked List
  • Chosen memory management
  • Tasks
  • The command interface
• Solution

Sorted Linked List

In this task you complete the functions add and remove of a singly linked sorted (in ascending order) list.

One invariant of the sorted linked list is the following: for subsequent nodes n and next it holds \(n.value \leq next.value \).

Chosen memory management

We do not want to deal with the memory management by ourselves. Therefore we use std::shared_ptr instead of normal pointers. Behind the scenes, shared pointers contain a counter that counts the number of references to the pointer. As soon as this counter reaches the value zero, the object behind the pointer is removed, i.e. delete is called automatically.

Otherwise, a shared pointer has nearly the same functionality as a normal pointer. For this exercise:

• Where we previously used the pointer type node*, we now use std::shared_ptr<node>
• Members of a shared pointer are accessed like on a normal pointer: using the -> operator.
• Assignments and comparisons work in the same way as for normal pointers.
• Only allocation, like new node(value), is replaced by std::make_shared<node>(value).
• Calls to delete can be omitted completely. Shared pointers call delete automatically when required.

Consider for example the finished implementation of the print function and the already implemented part of the add function.

Tasks

1. Complete the function void sorted_list::add(int value) such that a new node with the provided value is inserted into the linked list. The list needs to remain sorted in ascending order. Several nodes with the same value may be contained. The order of the nodes with same value is unimportant.
2. Complete the function bool sorted_list::remove(int value) such that a node with the given value is removed from the list. If no node with this value exists, the function should return false. Otherwise one (and only one) element is removed and the function returns true. Hint: help yourself with copy&paste from the previous function add.

The command interface

The main function implements the command interface that understands the following commands:

• add {int} ("add" followed by a sequence of integers) – calls add on a sorted list for all the integers provided. Example: add 1 2 3 adds numbers 1, 2 and 3 to the list.
• remove {int} ("remove" followed by a sequence of integers) – calls remove on a sorted list for all integers provided. Example: remove 3 6 removes an element with value 3 and an element with value 6 from the list (as far as available).
• print – calls print on the linked list.
• end – ends the program.

Solution

#include "sorted_list.h"

// post: add a new node with value to the sorted linked list
//       several nodes with the same value are possible
void sorted_list::add(int value) {
  // this creates a new node in dynamic memory, wrapped in a shared pointer
  // analogously to new node(value) for normal pointers
  node_ptr newNode = std::make_shared<node>(value);

  node_ptr prev = nullptr;
  node_ptr n = first;
  while (n != nullptr && n->value < value) {
    prev = n;
    n = n->next;
  }

  if (prev == nullptr) {
    newNode->next = first;
    first = newNode;
  } else {
    newNode->next = n;
    prev->next = newNode;
  }
}

// post: remove the first node which holds 'value', if any.
//       if there is no such node, return false
//       otherwise return true
bool sorted_list::remove(int value) {
  node_ptr searchNode = std::make_shared<node>(value);

  node_ptr prev = nullptr;
  node_ptr n = first;
  while (n != nullptr && n->value != searchNode->value) {
    prev = n;
    n = n->next;
  }

  if (n != nullptr) {
    if (prev != nullptr) {
      prev->next = n->next;
      return true;
    } else {
      first = n->next;
      return true;
    }
  } else {
    return false;
  }
}

---

Made by JirR02 in Switzerland 🇨🇭