// linklist1.cpp 		By: Aiman Hanna -  ©1993-2002 Aiman Hanna

// This program shows the creation and manipulation of linked lists.
//
// Key Pints: 	1) Linked list data Structure.

#include "linklist1.h"

Node::Node(int val)
{
 value = val;
 next = NULL;	
}



ostream& operator<< ( ostream& os, const IntList& lst )
{
  Node *ndptr = lst.first;

  while( ndptr )
  {
   	os << ndptr -> value;
	os << " ----> ";
	ndptr = ndptr -> next;
  }
  	os << "X" << endl;		 // 'X" here indicates NULL in the output.
  return os;		
}




IntList::IntList()
{
 cout << "\n Constructing a new list" << endl;
 cout << " =======================" << endl;

 // Initialize first and last to NULL, and size to zero
 first = last = NULL;
 size = 0;

 Node* tmp;
 int v;
 cout << " Enter your values to create the list. Enter -1 to terminate" << endl;
 cin >> v;

 while (v != -1)
 {
  // Check first whether there are any nodes in the list. if the list is empty 
  // then add the first node.
  
    if ( first == NULL )	// list is empty
    {
      last = first = new Node(v);
    }
    else 	// list is not empty
    {
     // Create a new node and insert it at the end of the list
     tmp = new Node(v);
     last -> next = tmp;	// change last to point to the new node
     last = tmp; 		// move tmp to point to the new node 
    }

    size++; 	// in both cases, increment the size of the list. 
    cin >> v; 
 }

}







void IntList::InsertFirst( int x )
{
 // Insert a new node with value = x at the beginning of the list

 Node *tmp = new Node(x);
      
if ( first == NULL )	// list is empty
    {
      last = first = tmp;      // first and last point to the new node
    }
    else 	// list is not empty
    {
     tmp -> next = first;
     first = tmp;       		// move head to point the first node
    }		
 size++;		// increment the list size anyway as you added one node
}




void IntList::InsertLast( int x )
{
 // Insert a new node with value = x at the end of the list

 Node *tmp = new Node(x);
      
if ( first == NULL )	// list is empty
    {
      last = first = tmp;      // first and last point to the new node
    }
    else 		// list is not empty
    {
     last -> next = tmp; 	// make the current last node points to the new one 
     last = tmp;		// move tail to point the last node
    }		
 size++;		// increment the list size anyway as you added one node
}





IntList::~IntList()
{
 // de-allocate the memory before you terminate to eliminate memory leak
 Node *tmp = first;		// Two pointers are needed to delete the list

 while ( first )
 {
  first = first -> next;
  delete tmp;
  tmp = first;

  size--;
 }
 last = NULL;	// first is already NULL by now 
}




int main()
{
 IntList list1, list2;

 
 cout << "\n List1 is: " << list1 << endl;

 cout << " List2 is: " << list2 << endl;

 list1.InsertFirst( 10 );
 cout << " List1 now  is: " << list1 << endl;

 list2.InsertFirst( 100 );
 list2.InsertLast( 900 );  
 cout << " List2 now  is: " << list2 << endl;

 return 0;
}




// The result of running the program is:
/*
   
 Constructing a new list
 =======================
 Enter your values to create the list. Enter -1 to terminate
9 12 4 7 3 5 12 8 -1

 Constructing a new list
 =======================
 Enter your values to create the list. Enter -1 to terminate
120 342 89 11 75 -1

 List1 is: 9 ----> 12 ----> 4 ----> 7 ----> 3 ----> 5 ----> 12 ----> 8 ----> X

 List2 is: 120 ----> 342 ----> 89 ----> 11 ----> 75 ----> X

 List1 now  is: 10 ----> 9 ----> 12 ----> 4 ----> 7 ----> 3 ----> 5 ----> 12 ----> 8 ----> X

 List2 now  is: 100 ----> 120 ----> 342 ----> 89 ----> 11 ----> 75 ----> 900 ----> X

 */