#~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~#
#   Link List Code Examples For Ordered Lists.   #
#________________________________________________#

typedef struct
{
    char key[26];
    int  ssn;
} data_t;

typedef struct node_s
{
	struct node_s *next;
	data_t entry;
}node_t;


/**************************************************
* Name -- addlist : adds into the link list in 
*         ascending order
*
* parameters :
*	parameter1 :  link list node/head pointer  
*	Parameter2 :  element to add
*
* return : success (0) or
*          failure to add (-1)
*
* Pre-cond:
*	link list must have been initilized
* Post-cond:
*	link list is altered.
***************************************************/
int addlist(node_t **a, data_t b)
{
   node_t *work;
   node_t *prev;
   node_t *curr;

   curr=(node_t *)malloc(sizeof(node_t));
   if ( curr == NULL)
      return(-1);

   curr->next=NULL;
   curr->entry=b;

   if (*a == NULL)
   {
      *a=curr;
   }
   else
   {
      work=*a;
      prev=NULL;

      while(work != NULL &&
         (strcmp(work->entry.key,curr->entry.key) < 0))
      {
         prev=work;
         work=work->next;
      }
      /* Now have a spot to insert */
      if (prev == NULL)
      {
         *a=curr;
         curr->next=work;
      }
      else
      {
         curr->next = prev->next;
         prev->next=curr;
      }
   }

   return (0);

}


/**************************************************
* Name -- <LSearch> : Linear Search for an element.
*
* parameters :
*	parameter1 :  link list node  
*	Parameter2 :  element to look for
* return :  address to a data element or null
*
* Pre-cond:
*	link list must exist
* Post-cond:
*	link list unmodified
***************************************************/
data_t *LSearch(node_t *a, char *keya)
{
	node_t *curr = a;
 	while (curr!=NULL)
	{
		if (strcmp(curr->entry.key,keya)==0)	
			return (&(current->entry));
		curr=curr->next;
	}
	return NULL;
} 


/**************************************************
* Name -- <initlist> : Initializing the link list
*
* parameters :
*	parameter1 :  address of head pointer to the link list  
* return :     void
* Pre-cond:
*	
* Post-cond:
*	link list head initilized to NULL
***************************************************/
void initlist(node_t **a)
{
	*a = NULL;
}

      

/**************************************************
* Name -- <dellist> : Delete an element in the link list
*
* parameters :
*	parameter1 :  address of head pointer to the link list  
*       parameter2 : element to be deleted
*
* return :  success(0) or failure (-1)
*
* Pre-cond:
*	List must be properly built
* Post-cond:
*	element removed if found
***************************************************/
int dellist(node_t **a, char *keya)
{
   node_t *prev = NULL,
          *work = *a;

   if (*a == NULL)
   {
      return (-1);
   }
   
   while (work != NULL &&
          strcmp(work->entry.key, keya) != 0))
   {
      prev = work;
      work = work->next;
   }

   if (work == NULL)
   {
      return (-1);
   }
   else
   {
      if (prev == NULL)
      {
         *a = work->next;
      }
      else
      {
         prev->next = work->next;
      }

      free(work);
      return (0);
   }
}

/**************************************************
* Name -- <lengthlist> : Get the length of the list
*
* parameters :
*	parameter1 : head pointer to the link list  
*
* return :  count
*
* Pre-cond:
*	List must be properly built
* Post-cond:
*	No change in the list
***************************************************/
int lengthlist(node_t *a)
{
   int count = 0;
   node_t *work = a;

   while(work != NULL)
   {
      count++;
      work = work->next;
   }

   return (count);
}


#~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~#
#  End of Link List Code Examples For Ordered Lists.  #
#_____________________________________________________#






#~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~#
#   Link List Code Examples For Last In First Out.   #
#____________________________________________________#

typedef struct
{
    char key[26];
    int  ssn;
} data_t;

typedef struct node_s
{
	struct node_s *next;
	data_t entry;
}node_t;


/**************************************************
* Name -- addlist : adds to the end of the link list
*
* parameters :
*	parameter1 :  link list node  
*	Parameter2 :  element to add
*
* return : success or failure to add
*
* Pre-cond:
*	link list must exist
* Post-cond:
*	
***************************************************/
int addlist(node_t **a, data_t b)
{
   node_t *work;
   node_t *prev;
   node_t *curr;

   curr=(node_t *)malloc(sizeof(node_t));
   if ( curr == NULL)
      return(-1);

   curr->next=NULL;
   curr->entry=b;

   if (*a == NULL)
   {
      *a=curr;
   }
   else
   {
      work=*a;
      prev=NULL;

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

      if (prev == NULL)
      {
         *a=curr;
      }
      else
      {
         prev->next=curr;
      }
   }

   return (0);

}


/**************************************************
* Name -- <LSearch1> : Linear Search for an element.
*
* parameters :
*	parameter1 :  link list node  
*	Parameter2 :  element to look for
* return :  address to a data element
*
* Pre-cond:
*	link list must exist
* Post-cond:
*	
***************************************************/
data_t *LSearch(node_t *a, char *keya)
{
	node_t *work = a;
 	while (work != NULL)
	{
		if (strcmp(work->entry.key,keya) == 0)	
			return (&(work->entry));
		work = work->next;
	}
	return NULL;
} 


/**************************************************
* Name -- <initlist> : Initializing the link list
*
* parameters :
*	parameter1 :  address of head pointer to the link list  
* return :     void
* Pre-cond:
*	
* Post-cond:
*	
***************************************************/
void initlist(node_t **a)
{
	*a = NULL;
}


/**************************************************
* Name -- dellist : Delete an element from the 
*     end of the link list
*
* parameters :
*	parameter1 :  address of head pointer to the link list  
*       parameter2 : element to be deleted
*
* return :     void
*
* Pre-cond:
*	
* Post-cond:
*	
***************************************************/
int dellist(node_t **a)
{
   node_t *prev,
          *work;

   if (*a == NULL)
   {
      return (-1);
   }

   work = *a;
   prev = NULL;
   
   while (work->next != NULL)
   {
      prev = work;
      work = work->next;
   }

   if (prev == NULL)
   {
      *a = NULL;
   }
   else
   {
      prev->next = NULL;
   }

   free(work);
   return (0);
}

/**************************************************
* Name -- <lengthlist> : determine link list length
*
* parameters :
*	parameter1 : head pointer to the link list  
*
* return :  count of the number of nodes
*
* Pre-cond:
*	    correctly initilized link list
* Post-cond:
*	    no change in the list
***************************************************/
int lengthlist(node_t *a)
{
   int count = 0;
   node_t *work = a;

   while (work != NULL)
   {
      count++;
      work = work->next;
   }

   return (count);
}


#~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~#
#   End of Link List Code Examples For Last In First Out.   #
#___________________________________________________________#