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,

Tell me. What happens when a new node should be placed at the front of the list?

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.

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. . .

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

}

---