Lab 8 - part 3 - Inserting/Deleting inside a Linked List
Back to part 2          on to part 4

In the Activity 1, you learned to insert a new node at the top of a linked list and in Activity 2, you learned to search for an item in a linked list.  We can use things that we learned from these two activities to insert a node in the middle of the linked list and/or delete a node from the middle of a liked list.  Before we get into any of these two scenarios, let's have one basic rule in mind.  If we remove one a link from the middle of a chain, the remaining two pieces will become a new chain only if somehow you connect the end of the fisrt piece to the end of the second one.  The same is true when we want to add a link in the middle of a chain.  You break the chain into two pieces, connect the last link on the first piece to the new link, and at last connect the other end of the newly added link to the first link on the second piece.  We will follow a similar process to insert or remove a node from the middle of a linked list.

Inserting in the Middle of a Linked List
When you want to insert a node in the middle of a linked list, you need to know the location where the insertion will take place.  Thus, one of the arguments to a function that performs the insertion in the middle of the list would be that location, suppose for now we call that location after_me.  Of course, you immediately realize that if you want to insert a node into a specific location, you need to first find that location, i.e., the node after which you will add the new node.  Thus, we first use the search function to locate the node after which the insertion will happen, then we do the insertion.  The insertion in the middle of a linked list is a bit tricky.  Here is the process (Suppose the insertion is going to happen between after_me and second Nodes):
    1) Search for the node, after_me, after which you wish to insert the new Node, new_node
    2) Disconnect the link between after_me Node and the second Node
    3) Connect the link from Node after_me to the Node new_node
    4) Connect the link from the new_node to the second Node

Now, let's modify program p15_2.cpp to insert a new Node.

// P15_3.cpp - Program to demonstrate the function insert.
// It asks users to input an item and the count and will ask
// them where they want to insert the new node. If the request
// is valid, the new node will be inserted.

#include <iostream>
#include <cstddef>
#include <string>
using namespace std;

struct Node
{
 string item;
    int count;
    Node *link;
};

typedef Node* NodePtr;

void insert(NodePtr after_me, string an_item, int a_number);
void head_insert(NodePtr& head, string an_item, int a_number);
void show_list(NodePtr& head);
NodePtr search(NodePtr head, string target);

int main()
{
     string new_item, target;
     int new_count;
     NodePtr head = NULL;
     head_insert(head, "Tea", 2);
     head_insert(head, "Jam", 3);
     head_insert(head, "Rolls", 10);

    cout << "List contains:" << endl;
    show_list(head);

    NodePtr after_me = head;
    after_me = after_me ->link;

    cout << "Enter the item you wish to insert (string) \n";
    cin >> new_item;
    cout << "Enter the count of new item \n";
    cin >> new_count;

    cout << "Enter the item after which you want \n";
    cout << "to insert the new node \n";
    cin >> target;
    after_me = search(head, target);
 

    if(after_me != NULL)
    {
          cout << "\nWill insert " <<  new_item << " with count" << endl
                  << new_count << " after the node with "
                  << (after_me -> item) << endl << endl;

          insert(after_me, new_item, new_count);

          cout << "List now contains:" << endl;
          show_list(head);
     }
     else
     {
          cout << "I can't find " << target
                  << " in the list, so I can't insert anything \n";
     }

    return 0;
}

//Uses cstddef:
void insert(NodePtr after_me, string an_item, int a_number)
{
    NodePtr temp_ptr;
    temp_ptr = new Node;

    temp_ptr -> item = an_item;
    temp_ptr -> count = a_number;

    temp_ptr ->link = after_me -> link;
    after_me ->link = temp_ptr;
}

//Uses cstddef:
void head_insert(NodePtr& head, string an_item, int a_number)
{
    NodePtr temp_ptr;
    temp_ptr = new Node;

    temp_ptr -> item = an_item;
    temp_ptr -> count = a_number;

    temp_ptr->link = head;
    head = temp_ptr;
}

//Uses iostream and cstddef:
void show_list(NodePtr& head)
{
    NodePtr here = head;

    while (here != NULL)
    {
          cout << here-> item << "\t";
          cout << here-> count << endl;
          here = here->link;
    }
}

NodePtr search(NodePtr head, string target)
{
   // Point to the head node
    NodePtr here = head;

    // If the list is empty nothing to search
    if (here == NULL)
    {
        return NULL;
    }
    // Search for the item
    else
    {
        // while you have still items and you haven't found the target yet
        while (here-> item != target && here->link != NULL)
            here = here->link;
            // Found the target, return the pointer at that location
            if (here-> item == target)
                return here;
            // Search unsuccessful, return Null
            else
                return NULL;
    }
}

Deleting a Node from the Middle of a Linked List
The deletion of a node from a linked list must be done in several steps.

Here is the process (Suppose the target is located between two nodes before and after)
    1) Search for the node that is to be removed, target
    2) Connect the link from node before to after
    3) Discard the node target

Exercise 15.3
Modify P15_3.cpp such that it deletes a requested node from the middle of the linked list.

Back to part 2          on to part 4