#include <iostream.h>


// A definition of the type of data we will store
// In this case, we will store ints
typedef int Listelement;


// The List Node class
// Each Listnode object will be one element of the list 
class Listnode {
public:
  Listelement data;
  Listnode *next;
};


// The Linked List class
class Linkedlist {
private:
  Listnode *first;
  Listnode *last;
  int numnodes;
  
public:
  Linkedlist(void);                      // Create a linked list
  Linkedlist(const Linkedlist& L);       // Create a LL as a copy of another one
  int Length(void) const;                // Return the length of the LL
  void Insert(const Listelement& Elem);  // Insert an element at the front
  void Append(const Listelement& Elem);  // Insert an element at the end
  void Delete(unsigned int pos);                  // Remove an element
  int Lsearch(const Listelement& searchval) const;  // Find an element
  ~Linkedlist(void);                     // Destroy a linked list
};


// The basic constructor
Linkedlist::Linkedlist(void)
{
  first = NULL;
  last = NULL;
  numnodes = 0;
}


// The copy constructor
Linkedlist::Linkedlist(const Linkedlist& L)
{
  Listnode *oldnode;
  Listnode *newnode;

  numnodes = L.numnodes;

  if(numnodes == 0) {
    first = NULL;
    last = NULL;
  } else {
    oldnode = L.first;

    newnode = new Listnode;

    newnode->data = oldnode->data;

    oldnode = oldnode->next;

    first = newnode;

    while(oldnode != 0) {
      newnode->next = new Listnode;

      newnode = newnode->next;

      newnode->data = oldnode->data;

      oldnode = oldnode->next;
    }

    last = newnode;
  }
}


// The Length function
int Linkedlist::Length(void)
{
  return(numnodes);
}


// Insert an element at the front of the list
void Linkedlist::Insert(const Listelement& elem)
{
  Listnode *newptr;

  newptr = new Listnode;
  newptr->data = elem;

  newptr->next = first;
  first = newptr;

  if(numnodes == 0)
    last = newptr;

  numnodes++;
}


// Append an element at the end of the list
void Linkedlist::Append(const Listelement& elem)
{
  Listnode *newptr;

  newptr = new Listnode;
  newptr->data = elem;

  newptr->next = NULL;

  if(last != NULL)
    last->next = newptr;

  last = newptr;

  if(numnodes == 0)
    first = newptr;

  numnodes++;
}


// Delete a specific node from the list
void Linkedlist::Delete(unsigned int pos)
{
  int i;
  Listnode *prevptr;
  Listnode *delptr;

  if(pos >= numnodes) {
    cout << "Can't delete past the end of the list" << endl;
    return;
  }

  if(pos == 0) {

    delptr = first;

    first = first->next;

    if(last == delptr)
      last = NULL;

  } else {

    for(i = 1; i < pos; i++) {
      prevptr = prevptr->next;
    }

    delptr = prevptr->next;

    prevptr->next = delptr->next;

    if(last == delptr)
      last = prevptr;
  }

  numnodes--;

  delete delptr;
}


// Linear search of the linked list for a particular element
// Returns the position in the list
int Linkedlist::Lsearch(const Listelement& searchval) const
{
  Listnode *nodeptr;
  int i;

  nodeptr = first;

  for(i = 0; i < numnodes; i++) {
    if(nodeptr->data == searchval)
      return(i);

    nodeptr = nodeptr->next;
  }

  return(-1);
}


// Destructor
Linkedlist::~Linkedlist(void)
{
  Listnode *tempptr;

  tempptr = first;

  while(tmpptr != NULL) {
    first = first->next;
    delete tempptr;
    tempptr = first;
  }
}