In what concerns the continuous evaluation solving exercises grade during the semester, you should submit until 23:59 of November 9th
(this exercise will still be available for submission after that deadline, but without couting towards your grade)
[to understand the context of this problem, you should read the class #05 exercise sheet]


[AED023] Inserting an element on a given position

In this problem you should only submit a singlyLinkedList.h file with a self-containing definition of a class SinglyLinkedList<T>

Base Code

Use as a basis the class SinglyLinkedList<T> (see code | download code) which implements a generic singly linked list similar to what was done on classes, with methods to add and remove an element in the end, return the size, knowing if the list is empty or printing the list.

The Problem

Add a new method void insert(int pos, const T & v) to the class. The function should insert element with value v right before position pos (with the positions starting in zero). If pos is invalid and not between 0 and length then the method should do nothing. Note that inserting at position length should mean adding at the last position (right before nullptr).

Submission

You should submit the file singlyLinkedList.h with the method insert added to SinglyLinkedList<T> as requested (and without removing any of the other existing methods). You can however create additional methods, if you need them.

Mooshak will use the following code to link to your class, read the inputs, build the lists and call your method, printing its result.

#include <iostream>
#include <string>

#include "singlyLinkedList.h"

// Read n and then n elements to add to the list using addFirst, followed by
// Read q and then q queries pos val to call insert(pos,val)
template <typename T>
void read() {
  int n;
  std::cin >> n;
  SinglyLinkedList<T> lst;
  for (int i=0; i<n; i++) {
    T v;
    std::cin >> v;
    lst.addFirst(v);
  }
  std::cout << "lst = " << lst.toString() << " | size = " << lst.size() << std::endl;
  std::cin >> n;
  for (int i=0; i<n; i++) {
    int pos;
    T v;
    std::cin >> pos >> v;
    std::cout << "lst.insert(" << pos << "," << v << ")" << std::endl;
    lst.insert(pos, v);
    std::cout << "lst = " << lst.toString() << " | size = " << lst.size() << std::endl;
  }
  std::cout << "-------------------------" << std::endl;
}

int main() {

  int n;
  std::cin >> n;
  for (int i=0; i<n; i++) {
    std::string type;
    std::cin >> type;
    if (type == "int") read<int>();
    else if (type == "char") read<char>();
    else if (type == "string") read<std::string>();
  }
  
  return 0;
}

Example Input Example Output
3

int 1
1
5
0 2
2 3
4 4
1 5
2 6

char 4
a b c d
5
4 z
0 y
-1 x
10 w
1 v

string 0

2
0 hello
1 world
lst = {1} | size = 1
lst.insert(0,2)
lst = {2,1} | size = 2
lst.insert(2,3)
lst = {2,1,3} | size = 3
lst.insert(4,4)
lst = {2,1,3} | size = 3
lst.insert(1,5)
lst = {2,5,1,3} | size = 4
lst.insert(2,6)
lst = {2,5,6,1,3} | size = 5
-------------------------
lst = {d,c,b,a} | size = 4
lst.insert(4,z)
lst = {d,c,b,a,z} | size = 5
lst.insert(0,y)
lst = {y,d,c,b,a,z} | size = 6
lst.insert(-1,x)
lst = {y,d,c,b,a,z} | size = 6
lst.insert(10,w)
lst = {y,d,c,b,a,z} | size = 6
lst.insert(1,v)
lst = {y,v,d,c,b,a,z} | size = 7
-------------------------
lst = {} | size = 0
lst.insert(0,hello)
lst = {hello} | size = 1
lst.insert(1,world)
lst = {hello,world} | size = 2
-------------------------


Algorithms and Data Structures (L.EIC011) 2024/2025
DCC/FCUP & DEI/FEUP - University of Porto