#include <stdio.h>
#include <stdlib.h>

// how many bytes is this struct?
// 12 bytes (on my machine)
struct node {
  int data;
  struct node *next;
  struct node *prev;
};

struct node *create_node(int data, struct node *next);
struct node *insert_at_tail(int data, struct node *head);
void print_ll(struct node *head);
int size_of_ll(struct node *head);
struct node *remove_at_index(struct node *head, int index);
struct node *remove_at_tail(struct node *head);

struct node *remove_at_index(struct node *head, int index) {
  struct node *current = head;
  struct node *prev = NULL;
  int counter = 0;

  // empty case
  if (current == NULL) {
    return NULL;
  }

  while (current->next != NULL && counter != index) {
    prev = current;
    current = current->next;
    counter++;
  }
  // this is the case where we are at end of list, but counter is less than
  // index
  if (counter != index) {
    return head;
  }

  if (prev == NULL) {
    free(current);
    return NULL;
  }

  // to get here, counter IS index (at the right position), and we are not
  // beyond end of LL here, we want to delete current and hook prev to point to
  // current's next. and free current.
  prev->next = current->next;
  free(current);

  return head;
}

// insert at the position passed in.
// so 1 -> 2 -> 3, and index 1 data 1
// 1 -> 1-> 2 -> 3
struct node *insert_at_index(int data, struct node *head, int index) {
  index--;
  struct node *current = head;
  int counter = 0;

  // empty case
  if (current == NULL) {
    return NULL;
  }

  while (current->next != NULL && counter != index) {
    current = current->next;
    counter++;
  }

  if (counter != index) {
    return head;
  }

  // we want to add a new node after current.
  struct node *new_node = create_node(data, current->next);
  current->next = new_node;
  return head;
}

// Remove's the last node of a linked list
// Traverse every element until you find the NULL pointer in next, then remove
struct node *remove_at_tail(struct node *head) {
  struct node *current = head;
  struct node *prev = NULL;

  // empty case
  if (current == NULL) {
    return NULL;
  }

  while (current->next != NULL) {
    prev = current;
    current = current->next;
  }

  // for the case that prev was NULL
  if (prev == NULL) {
    free(current);
    return NULL;
  }

  // if there was something in prev, then hook it all back up...
  prev->next = NULL;
  free(current);

  return head;
}

// a function which takes a linked list, and adds a new node at the end.
// is append a node (at the end of the LL)
struct node *insert_at_tail(int data, struct node *head) {
  struct node *current = head;

  // empty case
  if (current == NULL) {
    return create_node(data, NULL);
  }

  // if head is NULL, we are trying to dereference it to check ->next.
  // reassign current to current->next UNTIL current-> next is NULL.
  while (current->next != NULL) {
    current = current->next;
  }

  current->next = create_node(data, NULL);
  return head;
}

struct node *create_node(int data, struct node *next) {
  // create the node on the heap
  struct node *new_node = malloc(sizeof(struct node));

  // assign data and next
  new_node->data = data;
  new_node->next = next;

  return new_node;
}

// will it work if it's empty?
// will it work if first node, a node within a LL, and the tail node
void print_ll(struct node *head) {
  struct node *current = head;
  while (current != NULL) {
    printf("%d -> ", current->data);
    current = current->next;
  }
  printf("NULL \n");
}

int size_of_ll(struct node *head) {
  struct node *current = head;
  int counter = 0;
  while (current != NULL) {
    current = current->next;
    counter++;
  }
  return counter;
}

int main(void) {
  // creating the first node
  // next can't be uninitialised
  struct node *head = insert_at_tail(4, NULL);
  head = insert_at_tail(6, head);
  head = insert_at_tail(8, head);
  head = insert_at_tail(10, head);
  head = insert_at_tail(12, head);
  head = insert_at_tail(14, head);

  print_ll(head);

  printf("Insert at index 1 value 7\n");
  head = insert_at_index(7, head, 1);
  print_ll(head);

  printf("Remove at tail\n");
  head = remove_at_tail(head);
  print_ll(head);

  printf("Remove at index 1\n");
  head = remove_at_index(head, 1);
  print_ll(head);

  // free all the data remaining in the linked list.
  while (head != NULL) {
    head = remove_at_tail(head);
  }

  return 0;
}