LinkList in C

hi, I have created this LinkList in C. There is no problem with this program but I would like to hear some good advice from others if my coding needs modification. I cannot see any flaw on my own, but those who are experienced in C Programming I hope I would hear something from all of you that would help realize something I could use to improve my coding.

Code:

#include <stdio.h>
#include <conio.h>
#include <ctype.h>
#include <stdlib.h>

struct Node {
    int value;
    struct Node *nextPtr;
};

typedef struct Node NodePtr;
typedef NodePtr *ListNodePtr;

void addInFront( ListNodePtr*, int );
void addAtBack( ListNodePtr*, int );
void searchAndDestroy( ListNodePtr*, int );
void deleteFromFront( ListNodePtr* );
void deleteFromBack( ListNodePtr* );
void searchItemList( ListNodePtr, int );
void displayItemList( ListNodePtr );
void menu( void );

int found = 0;

int main( void )
{
    ListNodePtr Head = NULL;
    int inputValue, selection;
    char choose;
    clrscr();

    do
    {
	clrscr();
	gotoxy( 5, 3 );cprintf( "SINGLY Linked-List\n\n" );
	gotoxy( 5, 5 );cprintf( "[A]dd Item\n" );
	gotoxy( 5, 6 );cprintf( "[D]elete Item\n" );
	gotoxy( 5, 7 );cprintf( "Dis[P]lay Item\n" );
	gotoxy( 5, 8 );cprintf( "[S]earch Item\n" );
	gotoxy( 5, 9 );cprintf( "[Q]uit Program\n" );
	gotoxy( 5, 10 );choose = toupper( getch() );

	if( choose == 'A' )
	{
	   gotoxy( 5, 12 );printf( "Enter Item: " );scanf( "%d", &inputValue );fflush( stdin );
	   gotoxy( 5, 15 );printf( "1. Add In Front" );
	   gotoxy( 5, 16 );printf( "2. Add At Back " );scanf( "%d", &selection );fflush( stdin );
	   if( selection == 1 )
	   {
	     addInFront( &Head, inputValue );
	   }
	   else if( selection == 2 )
	   {
	     addAtBack( &Head, inputValue );
	   }
	   printf( "\n\n" );
	   displayItemList( Head );
	}
	if( choose == 'P' )
	{
	   printf( "\n\n" );
	   displayItemList( Head );
	}
	if( choose == 'D' )
	{
	   gotoxy( 5, 12 );printf( ">>>>Delete Item<<<<\n\n" );
	   gotoxy( 5, 14 );printf( "1. Delete from Front" );
	   gotoxy( 5, 15 );printf( "2. Delete from Back" );
	   gotoxy( 5, 16 );printf( "3. Search and Destroy" );scanf( "%d", &selection );fflush( stdin );
	   if( selection == 1 )
	   {
	      deleteFromFront( &Head );
	   }
	   else if( selection == 2 )
	   {
	      deleteFromBack( &Head );
	   }
	   else if( selection == 3 )
	   {
	      gotoxy( 5, 13 );printf( "Delete Item: " );scanf( "%d", &inputValue );fflush( stdin );
	      searchAndDestroy( &Head, inputValue );
	   }
	   displayItemList( Head );
	}
	if( choose == 'S' )
	{
	   printf( ">>>>Search Item<<<<\n\n" );
	   printf( "Search item: " );scanf( "%d", &inputValue );fflush( stdin );
	   searchItemList( Head, inputValue );
	   printf( "\n\n" );
	   displayItemList( Head );
	}
    }while( choose != 'Q' );

    return 0;
}
//add item in front
void addInFront( ListNodePtr *nodePtr, int rcvValue )
{
   ListNodePtr NewPtr;

   NewPtr = ( NodePtr * ) malloc( sizeof( NodePtr ) );
   if( NewPtr == NULL )
   {
      printf( "No available memory" );
      exit( 1 );
   }
   else
   {
      NewPtr->value = rcvValue;
      NewPtr->nextPtr = *nodePtr;
      *nodePtr = NewPtr;
   }
}
//add item at back
void addAtBack( ListNodePtr *nodePtr, int rcvValue )
{
   ListNodePtr NewPtr;
   ListNodePtr LastPtr = *nodePtr;

   NewPtr = ( NodePtr * ) malloc( sizeof( NodePtr ) );

   if( NewPtr == NULL )
   {
      printf( "No available memory" );
      exit( 1 );
   }
   else
   {
      if( *nodePtr == NULL )
      {
	 NewPtr->value = rcvValue;
	 NewPtr->nextPtr = *nodePtr;
	 *nodePtr = NewPtr;
      }
      else
      {
	 NewPtr->value = rcvValue;
	 NewPtr->nextPtr = NULL;

	 while( LastPtr->nextPtr != NULL )
	 {
	    LastPtr = LastPtr->nextPtr;
	 }
	 LastPtr->nextPtr = NewPtr;
      }
   }
}
void deleteFromFront( ListNodePtr *nodePtr )
{
   ListNodePtr tempPtr = *nodePtr;

   if( nodePtr == NULL )
      printf( "List Empty!" );
   else
      *nodePtr = tempPtr->nextPtr;

   free( tempPtr );
}

void deleteFromBack( ListNodePtr *nodePtr )
{
   ListNodePtr tempPtr = *nodePtr;
   ListNodePtr previousPtr = NULL;

   if( *nodePtr == NULL )
   {
      printf( "Empty List!" );
   }
   else
   {
      while( tempPtr->nextPtr != NULL )
      {
	 previousPtr = tempPtr;
	 tempPtr = tempPtr->nextPtr;
      }
      if( previousPtr == NULL )
	 *nodePtr = previousPtr->nextPtr;
      else
	 previousPtr->nextPtr = tempPtr->nextPtr;
   }
   free( tempPtr );
}

void searchAndDestroy( ListNodePtr *nodePtr, int rcvValue )
{
  ListNodePtr previousPtr, workingPtr;
  previousPtr = NULL;
  workingPtr = *nodePtr;

  while( workingPtr != NULL && rcvValue != workingPtr->value )
  {
    previousPtr = workingPtr;
    workingPtr = workingPtr->nextPtr;
  }
  if( workingPtr == NULL )
  {
     printf( "NULL" );
  }
  else
  {
     if( previousPtr == NULL )
     {
	*nodePtr = workingPtr->nextPtr;
     }
     else
     {
	previousPtr->nextPtr = workingPtr->nextPtr;
     }
  }
  free( workingPtr );
}
void searchItemList( ListNodePtr nodePtr, int rcvValue )
{
   if( nodePtr != NULL )
   {
      while( nodePtr != NULL && rcvValue != nodePtr->value )
      {
	 nodePtr = nodePtr->nextPtr;
      }
      if( rcvValue == nodePtr->value )
      {
	 printf( "\n\nFound %d\n\n", nodePtr->value );
      }
   }
}
void displayItemList( ListNodePtr nodePtr )
{
   if( nodePtr != NULL )
   {
     while( nodePtr != NULL )
     {
	printf( "%d-->", nodePtr->value );
	nodePtr = nodePtr->nextPtr;
     }
   }
   printf( "NULL" );
   getch();
}

Without much work you could delete a node from anywhere in the list:

Code:

ListNodePtr deleteNode ( ListNodePtr list, ListNodePtr oldvalue )
{
   ListNodePtr beforeold = list;
   if ( list != oldvalue ) { /**Not deleting the head **/
      while ( beforeold && beforeold->nextPtr != oldvalue ) beforeold = beforeold->nextPtr;
      beforeold->nextPtr = oldvalue->nextPtr;
   }
   else {
      list = oldvalue->nextPtr;
   }
   free( oldvalue );
   return list;
}

Be warned that this code is untested but you should have the general idea now. I suppose you should check for null parameters too.

You'll want to figure out something similar for adding nodes anywhere, given a position. I consider a complete linked list library to at least be able to search, sort, add anywhere, delete nodes anywhere, and find stuff. Most libraries do much more, some not, because linked lists can be as complicated as you want them to be. Also, double linked lists are better from a performance perspective as these tasks are somewhat easier because of the prev link; that is, it's easier to find neighboring nodes.

So... work on that, and you might realise why I hate building my own data structure libraries a lot of the time.

Code:

ListNodePtr deleteNode ( ListNodePtr list, ListNodePtr oldvalue )
{
   ListNodePtr beforeold = list;
   if ( list != oldvalue ) { /**Not deleting the head **/
      while ( beforeold && beforeold->nextPtr != oldvalue ) beforeold = beforeold->nextPtr;
      beforeold->nextPtr = oldvalue->nextPtr;
   }
   else {
      list = oldvalue->nextPtr;
   }
   free( oldvalue );
   return list;
}

My search and destroy will let you enter a value, this functil will delete that node that has the value you entered. So the code that you gave above will delete a specific node on its own, anywhere it wants to go?

Code:

typedef struct Node NodePtr;

"Ptr" in the "NodePtr" is a bit misleading, don't you think.

Code:

typedef NodePtr *ListNodePtr;

void addInFront( ListNodePtr*, int );

Either make it a double pointer in the typedef, or just declare:

Code:

void addInFront( Node**, int );

--
Mats

Originally Posted by $l4xklynx

My search and destroy will let you enter a value, this functil will delete that node that has the value you entered. So the code that you gave above will delete a specific node on its own, anywhere it wants to go?

My code will delete a node as long as you know where it is, without respect to the value. It can be useful. To properly destroy the list you only need to repeatedly call the function, for instance.

Not sure how to say this either, but your implementation quickly gets annoying when you have duplicates. Imagine the list 7, 1, 2, 7, 6, 7, and you want to delete all the sevens. With your implementation, it's very performance intensive (I can't even really use SearchItem to do this, since it doesn't return any nodes found and it's tied to output operations and I may not want to echo print.)

That reminds me of something else. It's a good idea to separate the list processing from the other operations in the program; if you do a reasonably good job at that, you'll find you don't need to write a completely new linked list library every time you need a linked list, you can just use what you wrote before.

I'm only doing what you asked me to do. For a first attempt, you did an ok job. If this is the second time around though...

typedef struct Node NodePtr;"Ptr" in the "NodePtr" is a bit misleading, don't you think.

so I should remove the "Ptr" instead put a different one for it is not really a pointer to a structure just yet.

typedef NodePtr *ListNodePtr;

void addInFront( ListNodePtr*, int );Either make it a double pointer in the typedef, or just declare:

Code:
void addInFront( Node**, int );

In my own opinion I guess it would be ok if I use typedef so that I could avoid typing double * for my structure variable name. But, if there is a big advantage in using the code that you provided compared to mine I will do it. But is there a big difference, I wanted to see the importance so that I could learn and know why I need to use that code you provided to me.

Not sure how to say this either, but your implementation quickly gets annoying when you have duplicates.

You're correct, I didn't even think about that. I will be working out with that, so the code that you provided does that job right?

Well my code is 17 inches long and doesn't allow me to ride a bicycle while sitting!

Originally Posted by whiteflags

Also, double linked lists are better from a performance perspective as these tasks are somewhat easier because of the prev link; that is, it's easier to find neighboring nodes.

I haven't done much research on the topic but I did just finish a comparative merge/bubble/insertion sort, and it seems to me that a double linked list is just easier to code, and not easier for the processor. In fact, it doubles the number of pointers you have to switch in a sort. Since they always take place link to link, operations that traverse a list can easily keep a "prev" pointer; i can't think of anything that would necessitate adding one to every single struct or how this would work out to a performance advantage.

But like I said, I haven't done much reading about it.

Originally Posted by MK27

I suppose that is true. However, it is hard to think of a situation where you had arrived somewhere, but could not keep track of where you were coming from (since there is no other way to get there) when you knew it would matter without actually seeing one yourself.

But things change. I admit I haven't found a practical application for the linked list in my life, but no doubt if I did I would soon want to make use of a "prev"

I'm not sure if I understand completely where you are coming from, but linked lists are as practical as arrays, especially if you need to do a lot of deletions and insertions. Doubly linked lists are also essentially binary trees. Provided, being well-balanced and ordered gives that the performance properties of a tree, but that has everything to do with the root value and the n-height.

Previous links offer substantial speedups a majority of the time for insertion, deletion, and other list operations, like splicing. If not stored then finding the previous link takes at most linear time; I don't think that's a cost you want to pay every single time.

And while you could pass in the previous link to do something with it, I don't particularly trust the design. Just any vanilla pointer won't do.

edit #2: doesn't this all end in "hash"?

You're thinking of another data structure perhaps? I don't think that's relevant.

If you need to traverse upward its also substancially faster. So do not assume it is bad to use them.

Originally Posted by master5001

If you need to traverse upward its also substancially faster. So do not assume it is bad to use them.

I suppose that is true. However, it is hard to think of a situation where you had arrived somewhere, but could not keep track of where you were coming from (since there is no other way to get there) when you knew it would matter without actually seeing one yourself.

But things change. I admit I haven't found a practical application for the linked list in my life, but no doubt if I did I would soon want to make use of a "prev"

edit: For some reason I am thinking the only real reason to use a double linked list is in something forked or multithreaded, but maybe I am getting too fancy for my pants
edit #2: doesn't this all end in "hash"?
edit #3: In the end, if it was something you couldn't keep track of like a variable pointer after a sort, the amount of calculation required to reorganize your prev pointers might as well be put into a function that will produce an array of pointers for "head" to "here"