#include <iostream>
static int NUMITEMS = 30;
static int NULPTR = -1;
static std::string DATA[] = {
    "Joe Australia",
    "Mark Carney",
    "Donald J. Trump",
    "Geert Wilders",
};
class Node {
public:
  std::string value;
  int next;
};
class LinkedList {
public:
  int root;
  int free;
  Node *src;
  LinkedList() {
    std::printf("Called constructor\n");
    root = NULPTR;
    free = 0;
    src = new Node[NUMITEMS];
    for (int i = 0; i < NUMITEMS; i++) {
      Node n;
      n.next = i + 1;
      src[i] = n;
    }
    src[NUMITEMS - 1].next = NULPTR; // set last ptr
  }
  void show() {
    int i = root;
    while (i != NULPTR) {
      std::cout << "[" << i << "] " << src[i].value << " -> " << src[i].next
                << std::endl;
      i = src[i].next;
    }
  }
  void insert(std::string element) {
    src[free].value = element;
    int next = src[free].next;
    src[free].next = root;
    root = free;
    free = next;
  }
  void insert_after(std::string element, int index) {
    int ptr = root;
    int i = 0;
    while (ptr != NULPTR) {
      if (i == index) {
        src[free].value = element;
        int next = src[ptr].next;
        src[ptr].next = free;
        src[free].next = next;
        free = src[free].next;
      }
      i++;
      ptr = src[ptr].next;
    }
  }
  bool find(std::string element) {
    int i = root;
    while (i != NULPTR) {
      if (src[i].value == element) {
        return true;
      }
      i = src[i].next;
    }
    return false;
  }
  ~LinkedList() { delete[] src; }
};
int main() {
  LinkedList l;
  for (const std::string &elem : DATA) {
    std::cout << "element: " << elem << std::endl;
    // std::cout << "root: " << l.root << "\tfree: " << l.free << std::endl;
    l.insert(elem);
  }
  l.show();
  l.insert_after("Putin", 0);
  l.show();
  return 0;
}