Chapter 13, Problem 1P

The following program creates a linked list with three names:

  #include <iostream>

  #include <string>

  using namespace std;

  struct Node

  {

  string name;

  Node *link;

  };

  typedef Node* NodePtr;

  int main()

  {

  NodePtr listPtr, tempPtr;

  listPtr = new Node;

  listPtr–>name = “Emily”;

  tempPtr = new Node;

  tempPtr–>name = “James”;

  listPtr–>link = tempPtr;

  tempPtr–>link = new Node;

  tempPtr = tempPtr–>link;

  tempPtr–>name = “Joules”;

  tempPtr–>link = NULL;

  return 0;

  }

Add code to the main function that:

1. a. Outputs in order all names in the list.
2. b. Inserts the name “Joshua” in the list after “James” then outputs the modified list.
3. c. Deletes the node with “Joules” then outputs the modified list,
4. d. Deletes all nodes in the list.

Program Plan Intro

Creation of program to produce a linked list and perform operations

Program Plan:

• Define a structure “Node” with member variable and link to another node.
• Define a method “displayList()” to display nodes present in the list.
  • Perform a loop operation until list reaches null.
  • Display name of node and move to next node.
  • Continue this process until list reaches null.
• Define a method “insertNameAfter()” to insert a name after a particular name.
  • Perform a loop operation until list reaches null.
  • Compare each word with given name.
  • If required name is reached, insert new name after the given name.
  • Update the next node pointer.
• Define a method “deleteNameList()” to delete a particular name in list.
  • Perform a loop operation until list reaches null.
  • Compare each word with given name.
  • If required name is reached, delete name.
  • Update the next node pointer.
• Define a method “deleteAllNodes()” to delete all nodes in list.
  • Declare variables that are required for program.
  • Perform a loop operation until list reaches null.
  • Assign “head” to a temporary variable.
  • Move to next node.
  • Delete the “head” of linked list.
• Define a main method to perform operations on list.
  • Declare variables that are required for program.
  • Define nodes and assign values.
  • Call method “displayList()” to display nodes in list.
  • Call method “insertNameAfter()” to insert a name after a particular name.
  • Call method “deleteNameList()” to delete a particular name in list.
  • Call method “deleteAllNodes()” to delete all nodes in list.

Program Description Answer

Program Description:

The following C++ program describes about creation of program to create a linked list and perform operations on list.

Explanation of Solution

Program:

//Include libraries

#include <iostream>

#include <string>

//Use namespace

using namespace std;

//Define a structure

struct Node

{

//Declare member variable

string name;

//Declare link

Node *link;

};

//Define instance

typedef Node* NodePtr;

//Define a method displayList()

void displayList(NodePtr head)

{

//Loop until empty

while(head!=NULL)

{

//Display value

cout<<head->name<<" ";

//Move to next node

head=head->link;

}

//New line

cout<<endl;

}

//Define method insertNameAfter()

void insertNameAfter(NodePtr head,string sName, string newName)

{

//Declare variable

NodePtr temp;

//Create instance of node

temp=new Node;

//Assign value

temp->name=newName;

//Assign null value

temp->link=NULL;

//Loop until it reaches null

while(head!=NULL)

{

//If condition satisfies

if(head->name.compare(sName)==0)

{

//Assign value

temp->link=head->link;

//Assign value

head->link=temp;

//Break

break;

}

//Assign value

head=head->link;

}

}

//Define method deleteNameList()

void deleteNameList(NodePtr head,string sName)

{

//Declare variable

NodePtr prev=NULL;

//Loop until it reaches null

while(head!=NULL)

{

//If condition satisfies

if(head->name.compare(sName)==0)

{

//Assign value

prev->link=head->link;

//Delete

delete head;        

//Break

break;

}

//Assign value

prev=head;

//Assign value

head=head->link;

}

}

//Define method deleteAllNodes()

void deleteAllNodes(NodePtr head)

{

//Declare variable

NodePtr temp;

//Loop

while(head)

{

//Assign value

temp=head;

//Move to next value

head=head->link;

//Delete node

delete temp;   

}

}

//Define main method

int main()

{

//Declare variables

NodePtr listPtr,tempPtr;

//Create new instance

listPtr =new Node;

//Assign value

listPtr->name="Emily";

//Create new node

tempPtr=new Node;

//Assign value

tempPtr->name="James";

//Assign value

listPtr->link=tempPtr;

//Create new node

tempPtr->link=new Node;

//Move to next value

tempPtr=tempPtr->link;

//Assign value

tempPtr->name="Joules";

//Assign null value

tempPtr->link=NULL;

//Display message

cout<<"All Names in the list are: "<<endl;

//Call method displayList()

displayList(listPtr);

//Call method insertNameAfter()

insertNameAfter(listPtr,"James","Joshua");

//Display message

cout<<"Output modified list after Insert Joshua are:"<<endl;

//Call method displayList()

displayList(listPtr);

//Call method deleteNameList()

deleteNameList(listPtr,"Joules");

//Display message

cout<<"Output modified list after deleting Joshua are:"<<endl;

//Call method displayList()

displayList(listPtr);

//Call method deleteAllNodes()

deleteAllNodes(listPtr);

//Pause console window

system("pause");

//Return

return 0;

}

Sample Output

All Names in the list are:

Emily James Joules

Output modified list after Insert Joshua are:

Emily James Joshua Joules

Output modified list after deleting Joshua are:

Emily James Joshua

Press any key to continue . . .