Inserting Items

One of the advantages of linked lists is that you can insert items into the list by only allocating one new item and changing the appropriate pointers to point to it, and make it point to the next item in the list. Contrast this to allocating an array of task objects; if you want to insert a new item somewhere in the middle, you would have to allocate a new array big enough for the old items and the new one and then copy the old items to the new array, copying in the new item in the right position.

The problem with the wallpaper task list is that the room has some painted wood and, as any decorator knows, it is best to paint the woodwork before hanging the wallpaper, and usually before sizing the walls. We need to insert a new task between filling any holes and sizing the walls. Further, before you do any decorating, you should cover any furniture in the room before doing anything else, so you need to add a new task to the beginning.

The first step is to find the position where we want to put our new task to paint the woodwork. We will look for the task that we want to be before the task we are inserting. Before main add the following:

    task *find_task(const string& name) 
    { 
        task* pTask = pHead; 

        while (nullptr != pTask) 
        { 
            if (name == pTask->description) return pTask; 
            pTask = pTask->pNext; 
        }  
        return nullptr; 
    }

This code searches the entire list for a link with the description that matches the parameter. This is carried out through a loop which uses the string comparison operator, and if the required link is found, a pointer to that link is returned. If the comparison fails, the loop initializes the loop variable to the address of the next link and if this address is nullptr it means that the required task is not in the list.

After the list is created in the main function, add the following code to search for the fill holes task:

    queue_task("hang new wallpaper"); 

    // oops, forgot to paint woodworktask
    * pTask = find_task("fill holes");
    if (nullptr != pTask) {   
        // insert new item after pTask
    } 
    execute_all();

If the find_task function returns a valid pointer, then we can add an item at this point.

The function to do this will allow you to add a new item after any item in the list that you pass to it and, if you pass nullptr, it will add the new item to the beginning. It's called insert_after, but clearly, if you pass nullptr it also means insert before the beginning. Add the following just above the main function:

    void insert_after(task* pTask, const string& name) 
    { 
        task* pNewTask = new task; 
        pNewTask->description = name; 
        if (nullptr != pTask) 
        { 
            pNewTask->pNext = pTask->pNext; 
            pTask->pNext = pNewTask; 
        } 
    }

The second parameter is a const reference because we will not change the string, but the first parameter is not a const pointer because we will be changing the object that it points to. This function creates a new task object and initializes the description member to the new task name. It then checks to see if the task pointer passed to the function is null. If it is not, then the new item can be inserted after the specified link in the list. To do this, the new link pNext member is initialized to be the next item in the list, and the pNext member of the previous link is initialized to the address of the new link.

What about inserting an item at the beginning, when the function is passed nullptr as the item to insert after? Add the following else clause.

    void insert_after(task* pTask, const string& name) 
    { 
        task* pNewTask = new task; 
        pNewTask->description = name; 
        if (nullptr != pTask) 
        { 
            pNewTask->pNext = pTask->pNext; 
            pTask->pNext = pNewTask; 
        } 
        else {      
            pNewTask->pNext = pHead;      
            pHead = pNewTask;   
        } 
    }

Here, we make the pNext member of the new item to point to the old beginning of the list and then change pHead to point to the new item.

Now, in the main function, you can add a call to insert a new task to paint the woodwork, and since we also forgot to indicate that it is best to decorate a room after covering all furniture with dustsheets, add a task to do that first in the list:

    task* pTask = find_task("fill holes"); 
    if (nullptr != pTask) 
    { 
        insert_after(pTask, "paint woodwork"); 
    } 
    insert_after(nullptr, "cover furniture");

You can now compile the code. When you run the code, you should see the tasks performed in the required order:

    executing cover furniture
    executing remove old wallpaper
executing fill holes
executing paint woodwork
executing size walls
executing hang new wallpaper