Question

Implement an application that uses linked lists. To be completed by a group of 3 people. Assignment: This is a group assignment. Go back to the Introduction to the Class assignment to search for group members you think may work well with you. Then visit Working in Groups to learn how to join a group. The first person to join a group will be assigned a leader role, which makes the person responsible for putting all parts together and submitting the work for the group, as explained below. Detailed Specifications: Chapter 7 introduces you to linked lists. In this lab assignment you will use the concepts presented in this chapter to implement a phone book that keeps a list of names with respective phone numbers. The contacts should be kept in alphabetical order by their last name, then first name. No repetitions are allowed. The algorithms presented in the zyBook use a tail pointer which is very useful for the append operation. For simplification since you won't need to append, you can implement the list with head pointer only. Here you will find Linked List Operations to insert, delete and destroy the list. These algorithms are incomplete. Look for the places that look like /***** insert code here *****/to add your own code. ZyBook 7.8 has an algorithm to traverse. You will need to code it in C++. The header file is provided here: Contact.h The class that implements the phone book must have the following member functions: • Constructor: should initialize the head to null. • Destructor: should clean up the list. Note that this method must follow the algorithm that eliminates one node at a time. If you just set head to null, you create a memory leak in your program. • Insert: must create a new node (with the name and phone number passed as parameters) and insert it in the list keeping it in alphabetical order. • Delete: receives the name as a parameter, looks for the node that matches the name and removes it from the list. • Print: traverses the list printing each contact (name and phone number) The following is a fair breakdown of the work needed to complete this lab in a group of 3 people: • Person 1: This is the group leader and the person who will turn in all files, implements the main function that instantiates the phone book object, develops the appropriate logic to interface with the user asking for names to be inserted/deleted and calls the appropriate methods. Makes sure all files compile when put together. Test and attach the output as a comment at the end of main. • Person 2: implements the insert and delete methods. Includes appropriate documentation of the function. • Person 3: implements constructor, destructor and print (traverse). Includes appropriate documentation of the function. Turn in: contactlist.cpp (with implementation of all member functions) and main.cpp (with the logic of the phone book

linked list operation

/*************************************************************************************** 
     This function creates a new node with the information give as a parameter and looks
     for the right place to insert it in order to keep the list organized
****************************************************************************************/  
void insertNode(string first_name, string last_name, string phoneNumber)
{
    ContactNode *newNode;
    ContactNode *nodePtr;
    ContactNode *previousNode = nullptr;

    newNode = new ContactNode;

    /***** assign new contact info to the new node here *****/

    if (!head)  // head points to nullptr meaning list is empty
    {
        head = newNode;  // head now points to the new node
        newNode->next = nullptr;
    }
    else // otherwise look for the right place to insert node
    {
        nodePtr = head;
        previousNode = nullptr;
        while (nodePtr != nullptr /***** && condition you need to keep the list sorted *****/)
        {
            previousNode = nodePtr;
            nodePtr = nodePtr->next;
        }
        if (previousNode == nullptr) // if the new node is to be the first in the list
        {
            head = newNode;
            newNode->next = nodePtr;
        }
        else // otherwise insert after the previous node
        {
            previousNode->next = newNode;
            newNode -> next = nodePtr;
        }
    }
}

/*************************************************************************************** 
   Delete the node whose information is given as a parameter. If not found, just returns.
****************************************************************************************/ 

void deleteNode (string name)
{
   ContactNode *nodePtr;
   ContactNode *previousNode;

   if (!head) // if the list is empty, do nothing
      return;

   /***** write code to test if the first node is the one *****/
   {
      nodePtr = head->next;
      delete head;
      head = nodePtr;
   }
   else
   {
      nodePtr = head;
      // skip all nodes whose values don't match
      while (nodePtr != nullptr /***** && test for node values) *****/
      {
         previousNode = nodePtr;
         nodePtr = nodePtr->next;
      }
      if (nodePtr) // if nodePtr is not at the end
      {
         previousNode->next = nodePtr->next; // link the previous node to the node after
         delete NodePtr;  // delete the node
      }
   }
}

/*************************************************************************************** 
     This function destroys a linked list one one node at a time
****************************************************************************************/ 
destroy()
{
    ContactNode *nodePtr;
    ContactNode *nextNode;
    ContactNode = head;

    while (nodePtr != nullptr)
    {
        nextNode = nodePtr->next; // save the pointer to the next node
        delete nodePtr;  // delete the current node
        nodePtr = nextNode; // move on the next node on the list
    }
}

contact.h

#ifndef CONTACT_H_

#define CONTACT_H_

#include <string>

class Contact {

private:

struct ContactNode

{

std::string first_name;

       std::string last_name;

std::string phoneNumber;

ContactNode *next;

};

ContactNode *head;

public:

     Contact();

virtual ~Contact();

   void insertContact(std::string first_name, std::string last_name, std::string

phoneNumber);

void deleteContact(std::string first_name, std::string last_name);

void printContacts();

};

#endif /* CONTACT_H_ */

Answer 1

// contact.h
#ifndef CONTACT_H_
#define CONTACT_H_

#include <string>

class Contact {

private:

struct ContactNode
{
std::string first_name;
std::string last_name;
std::string phoneNumber;
ContactNode *next;
};

ContactNode *head;

public:

Contact();
virtual ~Contact();
void insertContact(std::string first_name, std::string last_name, std::string phoneNumber);
void deleteContact(std::string first_name, std::string last_name);
void printContacts();

};

#endif /* CONTACT_H_ */

//end of contact.h

// contactlist.cpp

#include "contact.h"
#include <iostream>

using namespace std;

//linked list operation

// constructor to create an empty list
Contact::Contact()
{
head = nullptr;
}

/***************************************************************************************
This function creates a new node with the information give as a parameter and looks
for the right place to insert it in order to keep the list organized
****************************************************************************************/
void Contact::insertContact(string first_name, string last_name, string phoneNumber)
{
ContactNode *newNode;
ContactNode *nodePtr;
ContactNode *previousNode = nullptr;

newNode = new ContactNode;

/***** assign new contact info to the new node here *****/
newNode->first_name = first_name;
newNode->last_name = last_name;
newNode->phoneNumber = phoneNumber;
newNode->next = nullptr;

if (!head) // head points to nullptr meaning list is empty
{
head = newNode; // head now points to the new node
newNode->next = nullptr;
}
else // otherwise look for the right place to insert node
{
nodePtr = head;
previousNode = nullptr;
// loop that continues till we find the node which has first_name comes after the first_name to insert alphabetically
// or first_names are equals and last_name comes after last_name to insert.
while ((nodePtr != nullptr) && ((nodePtr->first_name < first_name) || (nodePtr->first_name == first_name && nodePtr->last_name <= last_name)))
{
previousNode = nodePtr;
nodePtr = nodePtr->next;
}

if (previousNode == nullptr) // if the new node is to be the first in the list
{
head = newNode;
newNode->next = nodePtr;
}
else // otherwise insert after the previous node
{
previousNode->next = newNode;
newNode -> next = nodePtr;
}
}
}

/***************************************************************************************
Delete the node whose information is given as a parameter. If not found, just returns.
****************************************************************************************/

void Contact::deleteContact(std::string first_name, std::string last_name)
{
ContactNode *nodePtr;
ContactNode *previousNode;

if (!head) // if the list is empty, do nothing
return;

/***** write code to test if the first node is the one *****/
// if head's first_name and last_name equals the input first_name and last_name, delete the head node
if(head->first_name == first_name && head->last_name == last_name)
{
nodePtr = head->next;
delete head;
head = nodePtr;
}
else
{
nodePtr = head;
// skip all nodes whose values don't match the first_name and last_name
while ((nodePtr != nullptr) && (nodePtr->first_name != first_name || nodePtr->last_name != last_name))
{
previousNode = nodePtr;
nodePtr = nodePtr->next;
}

if (nodePtr) // if nodePtr is not at the end
{
previousNode->next = nodePtr->next; // link the previous node to the node after
delete nodePtr; // delete the node
}
}
}

/***************************************************************************************
This function destroys a linked list one one node at a time
****************************************************************************************/
// destructor to delete all the nodes of the list
Contact::~Contact()
{
ContactNode *nodePtr;
ContactNode *nextNode;
nodePtr = head;

while (nodePtr != nullptr)
{
nextNode = nodePtr->next; // save the pointer to the next node
delete nodePtr; // delete the current node
nodePtr = nextNode; // move on the next node on the list
}
}

// function to display the contacts of the list
void Contact:: printContacts()
{
ContactNode *nodePtr = head; //set nodePtr to head

// loop over the list
while(nodePtr != nullptr)
{
// display the node's details
cout<<nodePtr->first_name<<" "<<nodePtr->last_name<<" "<<nodePtr->phoneNumber<<endl;
nodePtr = nodePtr->next; // go to next node
}
cout<<endl;
}

//end of contactlist.cpp

// main.cpp
#include <iostream>
#include "contact.h"
using namespace std;

int main()
{
Contact list;
list.insertContact("John","Smith","1234567890");
list.insertContact("Aaron","Hayes","2345678901");
list.insertContact("Shaun","Marsh","3456789021");
list.insertContact("Shaun","Hope","4567890213");
list.insertContact("Kelly","Larson","5678902134");
cout<<"List:"<<endl;
list.printContacts();

list.deleteContact("Shaun","Hope");
list.deleteContact("Aaron","Hayes");
list.deleteContact("Shaun","Marsh");
list.deleteContact("Kelly","Bolt");

cout<<"List:"<<endl;
list.printContacts();

return 0;
}

//end of main.cpp

Output:

List: Aaron Hayes 2345678901 John Smith 1234567890 Kelly Larson 5678902134 Shaun Hope 4567890213 Shaun Marsh 3456789021 List: John Smith 1234567890 Kelly Larson 5678902134