Thread: LinkList in C

  1. #1
    Registered User
    Join Date
    Oct 2008
    Posts
    115

    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();
    }

  2. #2
    Lurking whiteflags's Avatar
    Join Date
    Apr 2006
    Location
    United States
    Posts
    9,613
    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.
    Last edited by whiteflags; 11-28-2008 at 07:35 PM.

  3. #3
    Registered User
    Join Date
    Oct 2008
    Posts
    115
    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?

  4. #4
    Kernel hacker
    Join Date
    Jul 2007
    Location
    Farncombe, Surrey, England
    Posts
    15,677
    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
    Compilers can produce warnings - make the compiler programmers happy: Use them!
    Please don't PM me for help - and no, I don't do help over instant messengers.

  5. #5
    Lurking whiteflags's Avatar
    Join Date
    Apr 2006
    Location
    United States
    Posts
    9,613
    Quote Originally Posted by $l4xklynx View Post
    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...
    Last edited by whiteflags; 11-29-2008 at 11:30 AM.

  6. #6
    Registered User
    Join Date
    Oct 2008
    Posts
    115
    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?

  7. #7
    Banned master5001's Avatar
    Join Date
    Aug 2001
    Location
    Visalia, CA, USA
    Posts
    3,685
    Well my code is 17 inches long and doesn't allow me to ride a bicycle while sitting!

  8. #8
    spurious conceit MK27's Avatar
    Join Date
    Jul 2008
    Location
    segmentation fault
    Posts
    8,300
    Quote Originally Posted by whiteflags View Post
    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.
    C programming resources:
    GNU C Function and Macro Index -- glibc reference manual
    The C Book -- nice online learner guide
    Current ISO draft standard
    CCAN -- new CPAN like open source library repository
    3 (different) GNU debugger tutorials: #1 -- #2 -- #3
    cpwiki -- our wiki on sourceforge

  9. #9
    Lurking whiteflags's Avatar
    Join Date
    Apr 2006
    Location
    United States
    Posts
    9,613
    Quote Originally Posted by MK27 View Post
    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.

  10. #10
    Banned master5001's Avatar
    Join Date
    Aug 2001
    Location
    Visalia, CA, USA
    Posts
    3,685
    If you need to traverse upward its also substancially faster. So do not assume it is bad to use them.

  11. #11
    spurious conceit MK27's Avatar
    Join Date
    Jul 2008
    Location
    segmentation fault
    Posts
    8,300
    Quote Originally Posted by master5001 View Post
    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"
    Last edited by MK27; 12-04-2008 at 03:39 AM.
    C programming resources:
    GNU C Function and Macro Index -- glibc reference manual
    The C Book -- nice online learner guide
    Current ISO draft standard
    CCAN -- new CPAN like open source library repository
    3 (different) GNU debugger tutorials: #1 -- #2 -- #3
    cpwiki -- our wiki on sourceforge

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. help with reversing something in a linklist
    By Axel in forum C Programming
    Replies: 43
    Last Post: 10-23-2005, 07:14 AM
  2. LinkList Sorting in C
    By simly01 in forum C Programming
    Replies: 3
    Last Post: 11-25-2002, 01:21 PM
  3. Linklist Update
    By Nakeerb in forum C++ Programming
    Replies: 3
    Last Post: 11-16-2002, 12:08 PM
  4. MergeSort implementation with linklist.
    By Kam in forum C Programming
    Replies: 3
    Last Post: 10-21-2002, 11:04 AM
  5. Quick LinkList Help!!adding at the End
    By simly01 in forum C++ Programming
    Replies: 13
    Last Post: 07-28-2002, 07:19 AM