#include <vector>
#include <iostream>
#include <algorithm>
#include <cstring>

using namespace std;

// структуру List не реализовал, потому что впадлу, все это некомпилирующийся код, но функция вставки рабочая при написании недостающего кода, например для List
struct Node {
public:
    Node(int value) : value(value) {}

    int value;
    Node *next;
};

Node* head = NULL;
Node* tail = NULL;

// У циклического списка l есть begin - указатель на первый элемент списка, end - указатель на последний элемент списка,
// а также каждый элемент списка, знает указатель на соседа справа через метод next.
void insert(int value, int index) {

    Node* insertedNode = new Node(value);

    if (head == NULL) {
        head = insertedNode;
        head->next = head;
        return;
    }

    --index;
    int ithElement = 0;
    Node* current = head;


    // находим куда вставлять value в спикске l (допускаем, что index < чем длина списка, то есть вставить можем всегда)
    while (ithElement != index) {

        current = current->next;
        ++ithElement;
    }

    // до вставки на (index)-ый элемент указывал (index-1)-ый, теперь мы на место (index)-го вставляем новый, значит нужно поменять указатель на
    // следующий элменет у (index-1)-го элемента, а у вставленного элемента следующим элементом указать (index)-й
    //
    // как было раньше:  ... -> list[index - 1] -> list[index] ->  ...
    //
    // как стало: ... -> list[index - 1] -> current -> list[index] -> ...  (в терминах старых индексов)
    //
    // в терминах новых индексов это то же самое, что и: ... -> list[index - 1] -> list[index] -> list[index + 1] (здесь list[index + 1] это list[index] из строчки выше
    Node* temp = current->next;
    current->next = insertedNode;
    insertedNode->next = temp;
}

int main() {

    insert(5, 0);
    insert(6, 1);
    insert(7, 1);

    Node* cur = head;
    while (cur->next != head) {
        cout << cur->value << " ";
        cur = cur->next;
    }
    cout << cur->value << endl;
    return 0;
}