LList

// Linked List class.
// Stores positive integers.
//
#include "llist.h"
#include <cstdlib>
using namespace std;
//
//----------------------------------------------------------------
llist::llist() 
{
    head=new node;  // We are using a dummy node.
    head->next=NULL;
}
//----------------------------------------------------------------
llist::~llist() 
{
    deallocate();
}
//----------------------------------------------------------------
llist::llist(const llist &L)  // Deep copy
{
    // head=L.head; // Shallow copy.
    copy(L);
}
//----------------------------------------------------------------
llist& llist::operator =(const llist &L) 
{
    if(&L!=this)
    {
        deallocate();
        copy(L);
    }
    return *this;
}
//----------------------------------------------------------------
void llist::copy(const llist &L) // Assume an empty list.
{
    head=new node;
    node *S=head;
    node *T=L.head->next;
    while(T!=NULL) 
    {
         S->next=new node;
         S=S->next;
         S->key=T->key;
         T=T->next;
    }
    S->next=NULL;
}
//----------------------------------------------------------------
void llist::deallocate() 
{
   node *T=head->next;
   delete head;
   while(T!=NULL) 
   {
     head=T;
     T=T->next;
     delete head;
   }
}
//----------------------------------------------------------------
// Insert node at the head. Return 1 if successful, 0 otherwise.
bool llist::insert_at_head(node *x) 
{
    x->next=head->next;
    head->next=x;
    return 1;
}

//----------------------------------------------------------------
// Pre: the node y is actually in the list.
// Insert node pointed to by x after node pointed to by y.
// Return 1 if successful, 0 otherwise.
bool llist::insert_after(node *y,node *x) 
{
   if(y!=NULL) 
   {
       x->next=y->next;
       y->next=x;
       return 1;
   }
   else
       return 0;
}

//----------------------------------------------------------------
// Remove the node pointed to by x.  
// Return the key value of x if successful, -1 otherwise.
keytype llist::remove(node *x) 
{
   node *P=head;
   while(P!=NULL && P->next!=x)
        P=P->next;
   if(P!=NULL) 
   {
      P->next=x->next;
      keytype k=x->key;
      delete x;
      return k; 
   }
   else
      return -1;
}


//----------------------------------------------------------------
// Return the value of the key pointed to by head.
keytype llist::head_value() 
{
    if(head->next!=NULL)
      return head->next->key;
    else
      return -1;
}

//----------------------------------------------------------------
// Locate a value in the list.  Return a pointer to the first
// node found with key=value, NULL if no such node exists.
node *llist::find(keytype value) 
{
     // BAD CODE:   
     // node *T=new node;
     // T=head;
     node *T=head->next;
     while(T!=NULL && T->key!=value)
          T=T->next;
     return T; 
}
//----------------------------------------------------------------