Linked List Implementation - List

Started by aruljothi, Mar 31, 2009, 10:55 AM

Previous topic - Next topic

aruljothi

Code :
/* Header File... List.h */
#ifndef _List_H
struct Node;
typedef struct Node *PtrToNode;
typedef PtrToNode List;
typedef PtrToNode Position;
typedef int ElementType;

void MakeEmpty( List L );
int IsEmpty( List L );
int IsLast( Position P );
Position Find( ElementType X, List L );
void Delete( ElementType X, List L );
Position FindPrevious( ElementType X, List L );
void Insert( ElementType X, Position P );
void DeleteList( List L );
/*Position Header( List L);*/
/*Position First( List L );
/*Position Advance( Position P);*/
ElementType Retrieve( Position P);
#endif /* _List_H */

void FatalError( char  * );
void Error( char * );
--------------------------------------------------------------------------
-------
/* List Implementation --- Listl.c */


struct Node
{
  ElementType Element;
  Position Next;
};

List CreateList( void )
{
  List L;

  L = ( struct Node *)malloc( sizeof( struct Node ));
  if( L == NULL )
     FatalError( "Out of Space !!!" );
  L->Next = NULL;
  return L;
}

/* Return True if List is Empty */
/* Delete all the Nodes in the List Except Head */

void
MakeEmpty( List L )
{
  Position P,TmpCell;
  P = L->Next;
  while( P != NULL )
  {
    TmpCell = P;
    P = P->Next;
    free( TmpCell );
  }
  L->Next = NULL;

}


int
IsEmpty( List L )
{
  return ( L->Next == NULL );
}

/* Return True if P is the last position in the list L */
/* Parameter L is unused in this implementation */
int
IsLast( Position P)
{
  return P->Next == NULL;
}

/* Return Postion of X in L; NULL if not found */

Position
Find( ElementType X, List L )
{
  Position P;

  P = L->Next;
  while( P != NULL && P->Element != X )
      P = P->Next;
  return P;
}

/* Delete first occurence of X from a list */
/* Assume use of a header node */

void
Delete( ElementType X, List L)
{
  Position P, TmpCell;

  P = FindPrevious( X, L );
  if( !IsLast( P ) ) /* Assumption of header use */
  {             /* X is found; delete it */
    TmpCell = P->Next;
    P->Next = TmpCell->Next;
    free( TmpCell );
  }
}

/* If X is not found, then Next field of returned */
/* Position is NULL */
/* Assumes a header */

Position
FindPrevious( ElementType X, List L )
{
  Position P;
  P = L;
  while( P->Next != NULL && P->Next->Element != X )
      P = P->Next;
  return P;
}

/* Insert (after legal position p) */
/* Header implementation assumed */
/* Parameter L is unused in this implementation */

void
Insert( ElementType X, Position P )
{
  Position TmpCell;

  TmpCell =(struct Node *) malloc( sizeof( struct Node ) );
  if( TmpCell == NULL )
      FatalError("Out of space!!!" );
  TmpCell->Element = X;
  TmpCell->Next = P->Next;
  P->Next = TmpCell;
}
void DeleteList( List L )
{
  MakeEmpty( L );
  free( L );
}

ElementType
Retrieve( Position P )
{
  return P->Element;
}



---------------------------------------------------------------------

/*Lmain.c */


#include<stdio.h>
#include<conio.h>
#include "List.h"
#include "ListL.c"


void main( )
{
  int opt, data, x;
  List L;
  Position P;
  void Menu( );
  void Header( );
  void View( List L);
  L = CreateList( );
  MakeEmpty( L );

Menu:
  Header( );
  Menu( );
  scanf( "%d", &opt );
  switch( opt )
  {
    case 1: /* Insert at First */
   printf( "Enter the data : - ");
   scanf( "%d" , &data );
   P = L;
   Insert( data, P );
   printf( "%d Inserted
", L->Next->Element );
   break;
    case 2: /* Insert after X */
   printf( "Enter the data after which you want to Insert :- " );
   scanf( "%d", &x );
   P = Find( x, L );
   if( P == NULL )
       printf( "%d not found in List
", x );
   else
   {
     printf( "Enter the data : - ");
     scanf( "%d" , &data );
     Insert( data, P );
     printf( "%d Inserted
", data );
   }
   break;
    case 3: /* Insert at Last */
   P = L;
   while( !IsLast( P ) )
     P = P->Next;
   printf( "Enter the data : - ");
   scanf( "%d" , &data );
   Insert( data, P );
   printf( "%d Inserted
" ,data );
   break;
    case 4: /* Delete at First */
   if( IsEmpty( L ) )
      printf( "List Empty
" );
   else
   {
     x = Retrieve( L->Next );
     Delete( x, L );
     printf( "%d Deleted
", x );
   }
   break;
    case 5: /* Delete at First */
   if( IsEmpty( L ) )
      printf( "List Empty
" );
   else
   {
     printf( "Enter the data to Delete:- ");
     scanf( "%d", &x );
     P = Find( x, L);
     if( P == NULL )
        printf("%d Not Found
", x );
     else
     {
       Delete( x, L );
       printf( "%d Deleted
", x );
      }
   }
   break;
    case 6:
   if( IsEmpty( L ) )
      printf( "List Empty
" );
   else
   {
     P = L;
     while( !IsLast( P ) )
       P = P->Next;
     x = Retrieve( P );
     Delete( x, L );
     printf( "%d Deleted
", x );
   }
   break;
    case 7:
   View( L );
   break;
    case 8:
   DeleteList( L );
   printf( "List Deleted
" );
   getch( );
   exit( 0 );
   break;
    default:
   printf( "Enter a correct option.
" );
  }
  getch( );
  goto Menu;
}

void View( List L )
{
  Position P;
  P = L->Next;
  if( IsEmpty( L ) )
     printf( "List is Empty
" );
  else
  {
    printf( "The List Data are:-
" );
    while( P != NULL )
    {
   printf("%d
", P->Element );
   P = P->Next;
    }
  }
}


void Header( void )
{
  int i;
  clrscr( );
  printf( "          Implementation of List ADT
" );
  for( i = 0; i < 80; i++ ) putchar( 0xdf );
  putchar( '
' );
}

void Menu( void )
{
  printf( "Menu
----
" );
  printf( "    1.Insert at First
" );
  printf( "    2.Insert after X
" );
  printf( "    3.Insert at Last
" );
  printf( "    4.Delete at First
" );
  printf( "    5.Delete X
" );
  printf( "    6.Delete at Last
" );
  printf( "    7.View
" );
  printf( "    8.Exit
" );
  printf( "
Enter Your Option: - " );
}


void
Error( char *err )
{
   printf( "Error: %s
", err);
}

void
FatalError( char *err )
{
   Error( err );
   exit( 0 );
}