ETH_Informatik/Informatik_I/Exercise_11/Task_1

[Exam 2022.01 (MATH/PHYS/RW)] Circular Linked List

• Circular Linked List
  • Your Task
  • Input Format
    • Sample Interactions
      • Creating and showing a simple list with two values
      • Inserting two elements and removing one
• Solution

Circular Linked List

A circular linked list is a variation of a linked list in which the last node points to the first node, completing a full circle of nodes. In other words, this variation of the linked list doesn't have a null element at the end.

Take a brief look at the file Node.hpp.

A Node contains a pointer to the next Node, as well as a value, which is the data stored in the node:

struct Node {
int value;
Node* next;
}

In our implementation, each Node stores a value of type int. Moreover, we reserve the value 0 to indicate the sentinel Node (see below).

Now open the the file CircularLinkedList.hpp.

A CircularLinkedList contains a single public member variable Node* sentinel. The sentinel node is only there to facilitate the implementation. It is the only node in the list when the list is empty, and it can be identified as being the only node where value = 0.

Notice that, in an empty list, the next pointer of the sentinel node points to the sentinel itself.

A list containing a single value 1 looks like in the following image: the sentinel's next points to the first node of the list, and that node points to the sentinel in a circular fashion.

New values can be inserted in the list either at the beginning or at the end. A node inserted at the beginning comes immediately after the sentinel, while a node inserted at the end comes immediately before the sentinel.

Your Task

Your task is to implement the following functions in file tasks.hpp:

1. void CircularLinkedList::insertAtBegin(int value): given a strictly positive value, inserts the value in a node at the beginning of the list;
2. void CircularLinkedList::insertAtEnd(int value): given a strictly positive value, inserts the value in a node at the end of the list; hint: a sentinel can become a normal node (and vice versa);
3. void CircularLinkedList::removeValues(int value): removes all the nodes containing the provided value; leaves the list in the same state if no node with the provided value is present.
4. CircularLinkedList::~CircularLinkedList(): deconstructs the whole list, which includes deallocating all its nodes and the sentinel

Input Format

Various commands can be entered to test your implementation; each consists of a command followed by appropriate arguments:

• ib V : add value V at the beginning
• ie V : add value V at the end
• r V : removes all nodes with value V
• s : show the current status of the list
• exit : exits the program without checking for the correct deallocation of all the nodes
• exitSafe : exits the program checking the correct deallocation of all the nodes

Sample Interactions

Copy & Paste: in the ETH exam room use CTRL+SHIFT+C to copy and CTRL+SHIFT+V to paste into the console.

Creating and showing a simple list with two values

Input:

ib 1
ib 2
s
exit

Output:

List=[(2)=>(1)]

Inserting two elements and removing one

Input:

ib 1
ie 2
s
r 1
s
exit

Output:

List=[(1)=>(2)]
List=[(2)]

Solution

#pragma once

#include "CircularLinkedList.hpp"
#include "Node.hpp"
#include <cassert>

// PRE: value > 0
// POST: insert a new Node containing the value at the beginning of the list
void CircularLinkedList::insertAtBegin(int value) {
  assert(value > 0);

  Node *ram = new Node(value);
  ram->next = sentinel->next;
  sentinel->next = ram;
}

// PRE: value > 0
// POST: insert a new Node containing the value at the end of the list
void CircularLinkedList::insertAtEnd(int value) {
  assert(value > 0);

  Node *last = sentinel->next;

  while (last->next != sentinel)
    last = last->next;

  Node *ram = new Node(value);
  last->next = ram;
  ram->next = sentinel;
}

// PRE: value > 0
// POST: removes *all* the nodes with the provided value from the list
//       and deallocates the memory of the deleted nodes.
void CircularLinkedList::removeValues(int value) {
  assert(value > 0);

  Node *cur = sentinel;
  Node *ram = cur->next;

  while (ram != sentinel) {
    if (ram->value == value) {
      cur->next = ram->next;
      delete ram;
      ram = cur->next;
    } else {
      cur = ram;
      ram = cur->next;
    }
  }
}

// POST: Deconstructs the whole list, which includes deallocating
//       all its nodes and the sentinel
CircularLinkedList::~CircularLinkedList() {
  Node *cur = sentinel;
  Node *ram = cur->next;

  while (ram != sentinel) {
    cur->next = ram->next;
    delete ram;
    ram = cur->next;
  }
  delete ram;
}

---

Made by JirR02 in Switzerland 🇨🇭