#include <assert.h>
#include <stdlib.h>

template <class Item>
size_t list_length(Node<Item>* head_ptr) {
  Node<Item> *cursor;
  size_t answer;
  answer = 0;
  for (cursor = head_ptr; cursor != NULL; cursor = cursor->link)
    answer++;
  return answer;
}

template <class Item>
void list_head_insert(Node<Item>*& head_ptr, const Item& new_item) {
  Node<Item> *insert_ptr;
  insert_ptr = new Node<Item>;
  insert_ptr->data = new_item;
  insert_ptr->link = head_ptr;
  head_ptr = insert_ptr;
}

template <class Item>
void list_insert(Node<Item>* previous_ptr, const Item& new_item) {
  Node<Item> *insert_ptr;
  insert_ptr = new Node<Item>;
  insert_ptr->data = new_item;
  insert_ptr->link = previous_ptr->link;
  previous_ptr->link = insert_ptr;
}

template <class Item>
Node<Item>* list_search(Node<Item>* head_ptr, const Item& target) {
  Node<Item> *cursor;
  for (cursor = head_ptr; cursor != NULL; cursor = cursor->link)
    if (cursor->data == target)
      return cursor;
  return NULL;
}

template <class Item, class SizeType>
Node<Item>* list_locate(Node<Item>* head_ptr, SizeType position) {
  Node<Item> *cursor;
  size_t i;
  assert(position > 0);
  cursor = head_ptr;
  for (i = 1; (i != position) && (cursor != NULL); i++)
    cursor = cursor->link;
  return cursor;
}

template <class Item>
void list_head_remove(Node<Item>*& head_ptr) {
  Node<Item> *remove_ptr;
  remove_ptr = head_ptr;
  head_ptr = head_ptr->link;
  delete remove_ptr;
}

template <class Item>
void list_remove(Node<Item>* previous_ptr) {
  Node<Item> *remove_ptr;
  remove_ptr = previous_ptr->link;
  previous_ptr->link = remove_ptr->link;
  delete remove_ptr;
}

template <class Item>
void list_clear(Node<Item>*& head_ptr) {
  while (head_ptr != NULL)
    list_head_remove(head_ptr);
}

template <class Item>
void list_copy
(Node<Item>* source_ptr, Node<Item>*& head_ptr, Node<Item>*& tail_ptr) {
  head_ptr = NULL;
  tail_ptr = NULL;
  if (source_ptr == NULL)
    return ;
  list_head_insert(head_ptr, source_ptr->data);
  tail_ptr = head_ptr;
  for (source_ptr = source_ptr->link; source_ptr != NULL; source_ptr = source_ptr->link) {
    list_insert(tail_ptr, source_ptr->data);
    tail_ptr = tail_ptr->link; }
}

template <class Item>
void list_piece
(Node<Item>* start_ptr, Node<Item>* end_ptr, Node<Item>*& head_ptr, Node<Item>*& tail_ptr) {
  head_ptr = NULL;
  tail_ptr = NULL;
  if (start_ptr == NULL)
    return ;
  list_head_insert(head_ptr, start_ptr->data);
  tail_ptr = head_ptr;
  if (start_ptr == end_ptr)
    return ;
  for (start_ptr = start_ptr->link; start_ptr != NULL; start_ptr = start_ptr->link) {
    list_insert(tail_ptr, start_ptr->data);
    tail_ptr = tail_ptr->link;
    if (start_ptr == end_ptr)
      return ; }
}