#include <iostream>

struct Node{
  int data;
  struct Node *next;
};

// Given a reference (pointer to pointer) to the start pointer, appends a new node at the end of the list
void append(Node **start, const int new_data){
  // create a new Node
  Node *new_node = new Node;
  new_node->data = new_data;
  new_node->next = NULL;

  // if the list is empty then set the newly created note as start
  if(*start == NULL){
    *start = new_node;
    return;
  }

  // else travel the list till the last node
  Node *node = *start;
  while(node->next != NULL){
    node = node->next;
  }

  // set the new node as the next of the last node in the list
  node->next = new_node;
  return;
}

// adds a node to the front of the list
void push(Node **start, int new_data){
  Node *new_node = new Node;
  new_node->data = new_data;
  new_node->next = *start;
  *start = new_node;
}

void display(struct Node *node){
  while (node != NULL){
     std::cout << node->data << " ";
     node = node->next;
  }
}

// adds a node after a specified node in the list
void insert_after(Node *prev_node, const int new_data){
  if(!prev_node){
    std::cout << "the given previous node can not be NULL";
  }

  Node *new_node = new Node;
  new_node->data = new_data;
  new_node->next = prev_node->next;
  prev_node->next = new_node;
}

// remove the node whose data matches the given key
void remove(Node **start, int key){
  Node *node = *start;
  Node *prev;

  // if start does not exist then return
  if(!start){
    return;
  }

  // if start matches the key then remove start
  if(node->data == key){
    *start = node->next;
    delete node;
    return;
  }

  // else find the node which matches the key
  while(node->next){
    if(node->data == key){
      break;
    }
    prev = node;
    node = node->next;
  }

  // if the no node matches the key then do nothing
  if(!node->next && node->data != key){
    std::cout << "the given key was not found.\n";
    return;
  }

  // else delete the matching node
  prev->next = node->next;
  delete node;
}

int main(int argc, char const *argv[]) {
  Node *start = NULL;

  append(&start, 10);
  append(&start, 20);
  append(&start, 30);
  append(&start, 40);
  append(&start, 50);
  push(&start, 20);
  remove(&start, 50);
  remove(&start, 100);
  display(start);

  return 0;
}