Thread: Adding nodes to a linked list

  1. #1
    Registered User
    Join Date
    Oct 2006
    Posts
    8

    Adding nodes to a linked list

    Hello all,

    I have been writing a phonebook application. I am encountering an issue I cannot solve. The phonebook is based on a sorted linked list (sorted by First name) so adding a contact to the phonebook means a new node in the list is created and added. I have a problem adding the nodes in the proper order (function "insertSorted")

    Code:
    #include <stdio.h>
    #include <stdlib.h>
    #include <string.h>
    
    typedef struct
    {
          char* firstName;
          char* lastName;
    }nameDetails;
    
    typedef struct
    {
          int day;
          int month;
          int year;
    }Date;
    
    typedef struct
    {
          nameDetails name;
          char* phone;
          Date dateOfBirth;
          char* address;
    }Person;
    
    typedef struct Node_s
    {
          Person data;
          struct Node_s* next;
    }Node;
    
    typedef struct
    {
          Node* start;
          int num;
    }List;
    
    void getDOB (Date* ptr); // Date of birth
    void getData(char** ptr, char* message);
    
    /************************************************************/
    List* createList ()
    {
          List* ptrOfList=NULL;
          ptrOfList=(List*)malloc(sizeof(List));
          if (ptrOfList) //success to allocate
          {
                  ptrOfList->start=NULL;
                  ptrOfList->num=0;
          }
    	  else //fail to allocate
    	  {
    		  return NULL;
    	  }
          return ptrOfList;
    }
    /************************************************************/
    
    /************************************************************/
    Code:
    int insertSorted (List* ptrOfList, Person* ptrOfNewRecord)
    {
    	Node* ptrOfNewNode=NULL; // pointer to the new node
    	Node* currentPtr=NULL; // pointer which will go over the linked list
    
    	ptrOfNewNode=(Node*)malloc(sizeof(Node)); //creating a new node
    	if (ptrOfNewNode) //allocation successful
    	{
    		ptrOfNewNode->data=*ptrOfNewRecord; //putting the Person's new details into the data field of the node
    		// check where to insert the new node
    		
    		currentPtr=ptrOfList->start; // currentPtr will point to the beginning of the list
    		if (currentPtr!=NULL)
    		{
    			// list is not empty
    			
    			while ((currentPtr->next!=NULL) && (stricmp(currentPtr->data.name.firstName,ptrOfNewRecord->name.firstName)<0))
    			{
    				// still need to search, since First name is smaller
    				printf ("\nSearching...................................\n");
    				currentPtr=currentPtr->next;
    			}
    			// Let's put the new node in the correct location
    			printf ("putting new node!\n");
    
    			ptrOfNewNode->next=currentPtr->next;
    			currentPtr->next=ptrOfNewNode;
    		}
    		else
    		{
    			// list is empty
    			printf ("\nList is empty. putting in the beginning...\n");
    			ptrOfNewNode->next=currentPtr;
    			ptrOfList->start=ptrOfNewNode;
    		}
    		ptrOfList->num++;
    	}
    	else
    	{
    		//allocation failed
    	}
    	return 1; 
    }
    /************************************************************/
    
    /************************************************************/
    Person* searchRecordByName (List* ptrOfList, char* reqName)
    {
          if (ptrOfList->num=0)
          {
    		  printf ("List is empty.\n");
              return NULL;
          }
    	  //List not empty, let's get desired name
    	  printf ("Please enter desired name to look for");
    
    }
    
    /************************************************************/
    int removeRecordByFullName (List* ptrOfList, nameDetails* ptrOfNameDetails)
    {
    	Node* currentPtr=NULL; // Will be used in order to go over each node in the list
    	ptrOfNameDetails=(nameDetails*)malloc(sizeof(nameDetails)); //Allocating memory for the Person's new data
       // need to check if there is enough memo
    	
    	if (ptrOfList->num=0)
    	{
    		printf ("List is empty.\n");
    		return 1;
    	}
    
    	while ((currentPtr!=NULL) && (ptrOfNameDetails->firstName!=currentPtr->data.name.firstName) && (ptrOfNameDetails->lastName!=currentPtr->data.name.lastName))
    	{
    		//need to continue searching
    	}
    
    	if (currentPtr==NULL)
    	{
    		// arrived to the end of the list and didn't find the needed information
    		printf ("Couldn't find the following name to delete: %s %s",ptrOfNameDetails->firstName, ptrOfNameDetails->lastName);
    	}
    	else
    	{
    		// record found
    		printf ("record found");
    	}
    
    	return 0;
    }
    /************************************************************/
    
    /************************************************************/
    void printAllList (List* ptrOfList)
    {
    	Node* currentPtr=NULL;
          currentPtr=ptrOfList->start;
    
          if (ptrOfList->num==0)
          {
                  printf ("\nThe phonebook is empty!\n\n");
                  return;
          }
    	
    	  // List is not empty
          while (currentPtr!=NULL)
          {
    		  printf ("First name: %s\n"
    				"Last name: %s\n"
    				"Phone: %s\n"
    				"Address: %s\n"
    				"Day of birth: %d\n"
    				"Month of birth: %d\n"
    				"Year of birth: %d\n\n\n"
    				,currentPtr->data.name.firstName,currentPtr->data.name.lastName,currentPtr->data.phone,currentPtr->data.address,currentPtr->data.dateOfBirth.day,currentPtr->data.dateOfBirth.month,currentPtr->data.dateOfBirth.year);
    		
    		currentPtr=currentPtr->next;
          }
    }
    /************************************************************/
    
    /************************************************************/
    void getData(char** ptr, char* message)
    {
       char str[30];
    
    	printf ("%s", message);
        scanf ("%s",str); //Getting the item from the user
        *ptr = (char*)malloc(strlen(str) + 1); //Allocating memory for the item to add
    	// TODO: Check if there is enough memo
        strcpy (*ptr, str);
    }
    /************************************************************/
    
    /************************************************************/
    /* This function will send allocate memory for the Person's new data and will send to "getData" and "getDOB" the address of each field */
    
    Person* getAllUserDetails ()
    {
           Person* ptrOfStruct=NULL;
    
           ptrOfStruct=(Person*)malloc(sizeof(Person)); //Allocating memory for the Person's new data
    	   // need to check if there is enough memo
    
    		getData(&(ptrOfStruct->name.firstName), "Please enter First name: ");
    		getData(&(ptrOfStruct->name.lastName),  "Please enter Last name: ");
    		getData(&(ptrOfStruct->phone),  "Please enter phone number: ");
    		getData(&(ptrOfStruct->address),  "Please enter address: ");
    		getDOB(&(ptrOfStruct->dateOfBirth));
    
    	   return ptrOfStruct;
    }
    /************************************************************/
    
    /************************************************************/
    nameDetails* getNameDetails ()
    {
    	nameDetails* ptrOfNameDetails=NULL;
    	ptrOfNameDetails=(nameDetails*)malloc(sizeof(nameDetails)); //Allocating memory for the name details (for the erase)
    	// need to check if there is enough memo
    
    	getData(&(ptrOfNameDetails->firstName), "Please enter the First name of the record you want to remove: \n");
    	getData(&(ptrOfNameDetails->lastName), "Please enter the Last name of the record you want to remove: \n");
    
    	return ptrOfNameDetails;
    }
    /************************************************************/
    
    /************************************************************/
    void getDOB (Date* ptr)
    {
    	printf ("Please enter Day of birth: ");
    	scanf("%d", &(ptr->day));
    
    	printf ("Please enter Month of birth: ");
    	scanf("%d", &(ptr->month));
    
    	printf ("Please enter Year of birth: ");
    	scanf("%d", &(ptr->year));
    }
    /************************************************************/
    
    /************************************************************/
    
    int main ()
    {
       int action;
       List* ptrOfListMngr=NULL;
       Person* ptrOfNewPerson=NULL;
       nameDetails* ptrOfNameDetails=NULL;
       ptrOfListMngr=createList (); //will return the PTR of the list manager
       if (ptrOfListMngr==NULL)
       {
    	   printf ("Cannot allocate memory for the list manager");
    	//	exit;
       }
    
       do
       {
           printf ("\n\n" 
    			"My phonebook\n"
    			"========================================\n"
    			"\n"
    			"0 - Exit\n"
    			"1 - Add a record\n"
    			"2 - Print the phonebook\n"
    			"3 - Search record by name\n"
    			"4 - Remove a record\n"		
    			"5 - Erase all phonebook\n"
    			"6 - Download phonebook to file\n"
    			"7 - Upload phonebook from file\n"
    			"========================================\n"
    			"Please enter your choice: ");
    		
    
           scanf("%d",&action);
           fflush(stdin); //clean the keyboard buffer
    
           switch (action)
           {
           case 1:
    		   
    		   ptrOfNewPerson=getAllUserDetails();
    		   insertSorted(ptrOfListMngr,ptrOfNewPerson);
    			break;
    
           case 2:
                 printAllList (ptrOfListMngr);
    			
                   break;
    
    	   case 3:
    		   //
    
    	   case 4:
    		   ptrOfNameDetails=getNameDetails();
    			removeRecordByFullName(ptrOfListMngr,ptrOfNameDetails);
    
           default:
                   break; // back to main menu
           }
       } while (action!=0);
    
    }
    If you add: "Alex", "George", "Steve", it works (you can display the list and see) but if you add contacts in this following order: "Alex", "Steve", "George", it doesn't put "George" alfter "Alex" meaning in the right order...

    Please help...

    Thanks,

  2. #2
    Code Goddess Prelude's Avatar
    Join Date
    Sep 2001
    Posts
    9,897
    Tell me. What happens when a new node should be placed at the front of the list?
    My best code is written with the delete key.

  3. #3
    Registered User
    Join Date
    Oct 2001
    Posts
    2,934
    What you try to add node "George", you're already pointing at node "Steve". You need to add it before "Steve", not after "Steve". But you can't, because you're already past. Maybe you need to save a pointer to the previous node.

  4. #4
    {Jaxom,Imriel,Liam}'s Dad Kennedy's Avatar
    Join Date
    Aug 2006
    Location
    Alabama
    Posts
    1,065
    Somewhere on this forum, I wrote a function called addinorder(). . . it does what you want. It will need to be modified greatly, but it will do what you want. . . I guess what I'm saying is that this is asked often and you should search the forum. . . but now I'm sounding like I'm a broken record. . . . but now I'm sounding like I'm a broken record. . .

  5. #5
    Registered User
    Join Date
    Nov 2006
    Posts
    2
    Try this code...

    Things added:
    1. One mroe pointer to keep track of the previous node visited while searching.
    2. Check w.r.t the no. of elements in the list.


    Code:
    #include <stdio.h>
    #include <stdlib.h>
    #include <string.h>
    
    typedef struct
    {
          char* firstName;
          char* lastName;
    }nameDetails;
    
    typedef struct
    {
          int day;
          int month;
          int year;
    }Date;
    
    typedef struct
    {
          nameDetails name;
          char* phone;
          Date dateOfBirth;
          char* address;
    }Person;
    
    typedef struct Node_s
    {
          Person data;
          struct Node_s* next;
    }Node;
    
    typedef struct
    {
          Node* start;
          int num;
    }List;
    
    void getDOB (Date* ptr); // Date of birth
    void getData(char** ptr, char* message);
    
    /************************************************************/
    List* createList ()
    {
          List* ptrOfList=NULL;
          ptrOfList=(List*)malloc(sizeof(List));
          if (ptrOfList) //success to allocate
          {
                  ptrOfList->start=NULL;
                  ptrOfList->num=0;
          }
    	  else //fail to allocate
    	  {
    		  return NULL;
    	  }
          return ptrOfList;
    }
    /************************************************************/
    
    /************************************************************/
    // Code:
    int insertSorted (List* ptrOfList, Person* ptrOfNewRecord)
    {
    	Node* ptrOfNewNode=NULL; // pointer to the new node
    	Node* currentPtr=NULL; // pointer which will go over the linked list
            Node* previousPtr=NULL;
    
    	ptrOfNewNode=(Node*)malloc(sizeof(Node)); //creating a new node
    	if (ptrOfNewNode) //allocation successful
    	{
    		ptrOfNewNode->data=*ptrOfNewRecord; //putting the Person's new details into the data field of the node
    		// check where to insert the new node
    		
    		previousPtr=currentPtr=ptrOfList->start; // currentPtr will point to the beginning of the list
    		if (currentPtr!=NULL)
    		{
    			// list is not empty
    			
    			while ((currentPtr->next!=NULL) && (stricmp(currentPtr->data.name.firstName,ptrOfNewRecord->name.firstName)<0))
    			{
    				// still need to search, since First name is smaller
    				printf ("\nSearching...................................\n");
    				previousPtr=currentPtr;
    				currentPtr=currentPtr->next;
    			}
    			// Let's put the new node in the correct location
    			printf ("putting new node!\n");
    			
    			if (previousPtr != currentPtr)
    			{
    			previousPtr->next = ptrOfNewNode;
    			ptrOfNewNode->next=currentPtr;
    			}
    			else
    			{
                ptrOfNewNode->next=currentPtr;
    			ptrOfList->start=ptrOfNewNode;
    			}
    		}
    		else
    		{
    			// list is empty
    			printf ("\nList is empty. putting in the beginning...\n");
    			ptrOfNewNode->next=currentPtr;
    			ptrOfList->start=ptrOfNewNode;
    		}
    		ptrOfList->num++;
    	}
    	else
    	{
    		//allocation failed
    	}
    	return 1; 
    }
    /************************************************************/
    
    /************************************************************/
    Person* searchRecordByName (List* ptrOfList, char* reqName)
    {
          if (ptrOfList->num=0)
          {
    		  printf ("List is empty.\n");
              return NULL;
          }
    	  //List not empty, let's get desired name
    	  printf ("Please enter desired name to look for");
    
    }
    
    /************************************************************/
    int removeRecordByFullName (List* ptrOfList, nameDetails* ptrOfNameDetails)
    {
    	Node* currentPtr=NULL; // Will be used in order to go over each node in the list
    	ptrOfNameDetails=(nameDetails*)malloc(sizeof(nameDetails)); //Allocating memory for the Person's new data
       // need to check if there is enough memo
    	
    	if (ptrOfList->num=0)
    	{
    		printf ("List is empty.\n");
    		return 1;
    	}
    
    	while ((currentPtr!=NULL) && (ptrOfNameDetails->firstName!=currentPtr->data.name.firstName) && (ptrOfNameDetails->lastName!=currentPtr->data.name.lastName))
    	{
    		//need to continue searching
    	}
    
    	if (currentPtr==NULL)
    	{
    		// arrived to the end of the list and didn't find the needed information
    		printf ("Couldn't find the following name to delete: %s %s",ptrOfNameDetails->firstName, ptrOfNameDetails->lastName);
    	}
    	else
    	{
    		// record found
    		printf ("record found");
    	}
    
    	return 0;
    }
    /************************************************************/
    
    /************************************************************/
    void printAllList (List* ptrOfList)
    {
    	Node* currentPtr=NULL;
          currentPtr=ptrOfList->start;
    
          if (ptrOfList->num==0)
          {
                  printf ("\nThe phonebook is empty!\n\n");
                  return;
          }
    	
    	  // List is not empty
          while (currentPtr!=NULL)
          {
    		  printf ("First name: %s\n"
    				"Last name: %s\n"
    				"Phone: %s\n"
    				"Address: %s\n"
    				"Day of birth: %d\n"
    				"Month of birth: %d\n"
    				"Year of birth: %d\n\n\n"
    				,currentPtr->data.name.firstName,currentPtr->data.name.lastName,currentPtr->data.phone,currentPtr->data.address,currentPtr->data.dateOfBirth.day,currentPtr->data.dateOfBirth.month,currentPtr->data.dateOfBirth.year);
    		
    		currentPtr=currentPtr->next;
          }
    }
    /************************************************************/
    
    /************************************************************/
    void getData(char** ptr, char* message)
    {
       char str[30];
    
    	printf ("%s", message);
        scanf ("%s",str); //Getting the item from the user
        *ptr = (char*)malloc(strlen(str) + 1); //Allocating memory for the item to add
    	// TODO: Check if there is enough memo
        strcpy (*ptr, str);
    }
    /************************************************************/
    
    /************************************************************/
    /* This function will send allocate memory for the Person's new data and will send to "getData" and "getDOB" the address of each field */
    
    Person* getAllUserDetails ()
    {
           Person* ptrOfStruct=NULL;
    
           ptrOfStruct=(Person*)malloc(sizeof(Person)); //Allocating memory for the Person's new data
    	   // need to check if there is enough memo
    
    		getData(&(ptrOfStruct->name.firstName), "Please enter First name: ");
    		getData(&(ptrOfStruct->name.lastName),  "Please enter Last name: ");
    		getData(&(ptrOfStruct->phone),  "Please enter phone number: ");
    		getData(&(ptrOfStruct->address),  "Please enter address: ");
    		getDOB(&(ptrOfStruct->dateOfBirth));
    
    	   return ptrOfStruct;
    }
    /************************************************************/
    
    /************************************************************/
    nameDetails* getNameDetails ()
    {
    	nameDetails* ptrOfNameDetails=NULL;
    	ptrOfNameDetails=(nameDetails*)malloc(sizeof(nameDetails)); //Allocating memory for the name details (for the erase)
    	// need to check if there is enough memo
    
    	getData(&(ptrOfNameDetails->firstName), "Please enter the First name of the record you want to remove: \n");
    	getData(&(ptrOfNameDetails->lastName), "Please enter the Last name of the record you want to remove: \n");
    
    	return ptrOfNameDetails;
    }
    /************************************************************/
    
    /************************************************************/
    void getDOB (Date* ptr)
    {
    	printf ("Please enter Day of birth: ");
    	scanf("%d", &(ptr->day));
    
    	printf ("Please enter Month of birth: ");
    	scanf("%d", &(ptr->month));
    
    	printf ("Please enter Year of birth: ");
    	scanf("%d", &(ptr->year));
    }
    /************************************************************/
    
    /************************************************************/
    
    int main ()
    {
       int action;
       List* ptrOfListMngr=NULL;
       Person* ptrOfNewPerson=NULL;
       nameDetails* ptrOfNameDetails=NULL;
       ptrOfListMngr=createList (); //will return the PTR of the list manager
       if (ptrOfListMngr==NULL)
       {
    	   printf ("Cannot allocate memory for the list manager");
    	//	exit;
       }
    
       do
       {
           printf ("\n\n" 
    			"My phonebook\n"
    			"========================================\n"
    			"\n"
    			"0 - Exit\n"
    			"1 - Add a record\n"
    			"2 - Print the phonebook\n"
    			"3 - Search record by name\n"
    			"4 - Remove a record\n"		
    			"5 - Erase all phonebook\n"
    			"6 - Download phonebook to file\n"
    			"7 - Upload phonebook from file\n"
    			"========================================\n"
    			"Please enter your choice: ");
    		
    
           scanf("%d",&action);
           fflush(stdin); //clean the keyboard buffer
    
           switch (action)
           {
           case 1:
    		   
    		   ptrOfNewPerson=getAllUserDetails();
    		   insertSorted(ptrOfListMngr,ptrOfNewPerson);
    			break;
    
           case 2:
                 printAllList (ptrOfListMngr);
    			
                   break;
    
    	   case 3:
    		   //
    
    	   case 4:
    		   ptrOfNameDetails=getNameDetails();
    			removeRecordByFullName(ptrOfListMngr,ptrOfNameDetails);
    
           default:
                   break; // back to main menu
           }
       } while (action!=0);
    
    }

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Unknown memory leak with linked lists...
    By RaDeuX in forum C Programming
    Replies: 6
    Last Post: 12-07-2008, 04:09 AM
  2. Sorting linked list please help with CODE
    By scarlet00014 in forum C Programming
    Replies: 3
    Last Post: 09-27-2008, 11:24 PM
  3. Adding directory/file names to a linked list
    By thoseion in forum C Programming
    Replies: 13
    Last Post: 12-08-2006, 01:13 PM
  4. Reverse function for linked list
    By Brigs76 in forum C++ Programming
    Replies: 1
    Last Post: 10-25-2006, 10:01 AM
  5. How to use Linked List?
    By MKashlev in forum C++ Programming
    Replies: 4
    Last Post: 08-06-2002, 07:11 AM