Courses/CS 2124/Lab Manual/The Singly-Linked List

From A-State Computer Science Wiki
Jump to: navigation, search

Introduction

This lab examines how linked list data structures may be implemented as C++ objects.

Structure of the Linked List

A linked list data structure is made up of a head pointer and a series of list nodes; the first of this series is pointed to by the head, the second of the series is pointed to by the first, the third of the series by the second, and so on. A list may be either ordered or unordered. An unordered linked list will be constructed here to represent a list of Items for use as an inventory manager in an adventure game.

Item Data

We will be creating a list to keep track of game item data; to facilitate this, we will create a new data type Item to encapsulate the necessary information. The code for Item is shown below; create a file Item.h containing this code:

struct Item {
    Item(std::string name, int magic=0)
        : name{name}, magic{magic} {}
    std::string name;       /// Item name
    int         magic = 0;  /// Amount of "magic" the item is imbued with

    std::ostream& write( std::ostream& fout ) const;
};
std::ostream& operator<<( std::ostream& fout, const Item& item );

Implement the write() method and the overloaded stream insertion operator in the Item.cpp file.

The write() method should display the name (in a 30 character block), and “magic” value of a game item, with a space between them. Write this method now, using iomanip’s setiosflags(std::ios::left) to left justify the strings and resetiosflags(std::ios::left) to undo the justification after use. The write() method should return the stream after using it. The overloaded operator << simply calls write(); complete this function as well.

References for setiosflage and resetiosflags:

Begin function main() with the following lines; execute the program to verify that the Item constructor, write() method and the stream insertion operator function are working properly.

ofstream dbg{"debug.txt"};  // open a file named debug.txt

Item test_item{"Great Sword", 1};
dbg << "test item: \n" << test_item << "\n" << endl;

Run your program and verify that the correctly formatted game item information was written to debug.txt. The output should look like this:

test item: 
Great Sword                     1

List Nodes

Consider the following class definition for a game item node object:

class ItemNode {
public:
    ItemNode( const Item& new_item );
    Item          get_item( ) const;
    ItemNode*     get_next( ) const;
    void          set_next( ItemNode* node );
    std::ostream& write( std::ostream& fout ) const;

private:
    Item      payload;
    ItemNode* next = nullptr;
};
std::ostream& operator<<( std::ostream& fout, const ItemNode& node );

Start a library for ItemNode by creating ItemNode.h and .cpp now and placing the class definition shown above in the header file.

The constructor for the class must sink its formal parameter directly into the payload attribute of the node using a constructor attribute initializer list (see the constructor for class Item for an example and https://en.cppreference.com/w/cpp/language/initializer_list for more information). Write this constructor now.

Methods get_item(), get_next() and set_next() are the usual accessors/mutators for the private data payload and next. Write these methods now.

The write() method make use of the Item’s own write() method to print the name and number. For debugging purposes, in parentheses display the name of the game item pointed to by next; if no such game item exists, display a series of hyphens in place of the name. The overloaded operator << simply calls write(); complete this function as well.

Add the following lines to main(); execute the program to verify that the node constructor, write() method and the stream insertion operator function are working properly.

ItemNode test_node_1{ Item{"Amulet of Feasting", 2} };
dbg << "test game item node: \n" << test_node_1 << "\n" << endl;

The code Item{"Amulet of Feasting", 2} is instantiating a Item using Uniform Initialization Syntax that was added in the C++11 standard. There is no constructor required for this, provided the data’s listing order matches the order the attributes were declared in the definition of Item.

The displayed results should look something like the following.

test game item node: 
Amulet of Feasting             2 ( -------- )

Extend function main() with the following to test the next pointer access methods.

ItemNode test_node_2{ Item{"Potion of Fire Walking", 3} };
test_node_1.set_next( &test_node_2 );
dbg << "test 2 items: \n"
    << test_node_1 << "\n"
    << test_node_2 << endl;

Sample results follow; note that the information displayed for the first node has changed to reflect the assignment of a location to its next pointer.

test 2 items: 
Amulet of Feasting            2 ( Potion of Fire Walking )
Potion of Fire Walking        3 ( -------- )

The Unordered List

In an unordered list, there will be no relationship between nodes in the list. For that reason, the only meaningful additions that can be defined are those occurring at the ends of the list. A list of three items might be diagrammed as follows.

head -----> item202 -----> item101 -----> item303 /
                                          ^
tail -------------------------------------|

Now consider the following class definition for an unordered list object:

class ItemList {
public:
    ItemList( ) = default;
    std::ostream& write( std::ostream& fout ) const;
    void          add_front( const Item& new_item );

private:
    ItemNode* head = nullptr;
    ItemNode* tail = nullptr;
};
std::ostream& operator<<( std::ostream& fout, const ItemList& list );

Start a library for ItemList by creating ItemList.h and .cpp now and placing the class definition shown above in the header file.

Since all the constructor for this class would need to do is set head and tail pointers to nullptr (but that is handled by the attribute initialization syntax in the class itself), there is nothing left for the constructor to do. This is indicated by marking the constructor as default. (Note: If no other constructors are being defined, this is optional.)

Adding to the Head of an Unordered List

Method add_front() accepts as its parameter a Item. The method will construct a new ItemNode containing this item’s data and add it to the beginning of the list. For an example of this, let’s consider creating a new ItemNode that we’ll refer to as item404.

Consider the addition of item404 to a list for which at least some nodes are already present.

new_node---> item404 /

head -----> item202 -----> item101 -----> item303 /
                                          ^
tail -------------------------------------|

There are two things to be done, and they must be done in a particular order. The node of item404 must be made to point to the current head, item202, and then the head pointer is redirected to item404. These two steps cannot be done in the reverse order; otherwise, the location of item202 (and consequently the integrity of the list) would be lost. Note that the tail pointer is not involved in this instance.

Consider now the addition of item404 to a list which is at present empty.

new_node---> item404 /

head /

tail /

Here, it is clear that item404 becomes both the head and tail of the list; the two assignments required can be done in either order. Since a non-empty list requires that the head be updated last, it can arbitrarily be done last here as well. Note here that the null next pointer placed in the node of item404 by its constructor is unchanged during the addition.

The steps for the addition of a node to the head of a list are summarized in the algorithm that follows; complete the algorithm in method add_front().

ItemNode* new_node = // generate a new ItemNode given the new_item

if  // the list is empty
    // the tail must be pointed to new_node
else // the list is not empty
     // new_node's next must be pointed to current head
// current head is replaced by new_node (whether empty or not)

Note: You might have realized that you don’t actually need the else in the algorithm above — if the list was empty, setting new_node’s next pointer to head is really just assigning a null pointer to an already null pointer; no harm is done. Feel free to make this change to reduce the overall length of your code if you find it easier to read.

Add the following lines to main( ) to check that you are able to add nodes without crashing:

ItemList inventory1;

inventory1.add_front( Item{"Stone Shield", 1} );
inventory1.add_front( Item{"Potion of Health", 1} );

Draw a diagram that illustrates the operations that your code has performed on this two-item list. Be sure to include a separate diagram for each step, starting from the empty list, and ending up with the list as it should exist after adding both of the values above.


Labcheckpoint.png FOR IN-LAB CREDIT: Show the diagrams and explain the steps to the lab instructor.


Note: You really don’t know whether your add methods are working correctly yet, since you haven’t tested them. You only know that there are no syntax or fatal runtime errors. We need to focus on being able to visualize the list next, so that we can test.

Writing a List

The list method write() needs to display each item in the linked list. The first item could be displayed by accessing pointer head. It should first be noted that when dereferencing the value stored in a pointer variable, a value of nullptr will cause a fatal runtime error. This is analogous to the situation in mathematical formulae containing division, square roots, or logarithms, each of which should be checked for legitimate operands before being carried out. Thus the first list node could be safely printed with the following.

Don’t add the following code snippets to your program, but trace them on paper to make sure you understand what they are doing. Ask for help if you aren’t sure.

if ( head != nullptr ) 
  fout << "1st node: " << *head << endl;

The second item is pointed to by the first item and so could be written as follows.

if ( head->get_next() != nullptr )
    fout << "2nd node: " << *( head->get_next() ) << endl;

The third item is subsequently accessed with the following.

if ( head->get_next()->get_next() != nullptr )
   fout << "3rd node: " << *( head->get_next()->get_next() ) << endl;

In similar fashion, the fourth item would be reached as follows.

if ( head->get_next()->get_next()->get_next() != nullptr )
   fout << "4th node: " << *( head->get_next()->get_next()->get_next() ) << endl;

Of course, printing in this fashion is both tedious and impractical; each line is longer than the last, and there is no regard given to how many nodes are actually in the list.

Instead, a loop should be constructed to move through the linked list, calling upon operator << for each game item node to display one name and number per line.

Method write() can begin by setting a pointer current to the head of the list. Use a loop to print a item’s data and then update pointer current to the current node’s next pointer. Printing occurs as long as the current pointer is not nullptr; the nullptr sentinel indicates the end of the list. Write this method now.

Overload operator << for the list so that it invokes method write().

Add the following lines to your main program to verify that the write method and stream insertion operator are working (remember, you already added two values above, both at the head of the list).

dbg << "inventory1 listings with 2 nodes (head: Potion of Health, tail: Stone Shield):\n"
    << inventory1 << "\n"
    << endl;

Verify that the output in the file looks like this:

inventory1 listings with 2 nodes (head: Potion of Health, tail: Stone Shield):                     
Potion of Health              1 ( Stone Shield )                                 
Stone Shield                  1 ( -------- )

Adding to the Tail of an Unordered List

Now consider adding to the list at the tail. Add the following prototype to the unordered list class definition.

void add_back( const Item& new_item );

The operation of adding at the tail of a list is analogous to adding at the head. Diagram non-empty and empty cases for adding at the tail and describe the steps needed.

Once you are comfortable with the steps revealed by the diagram, use the diagrams and steps to complete the body of method add_back.

ItemNode* new_node = // generate a new ItemNode given the new_item

if  // the list is empty
    // the head must be pointed to new_node
else // the list is not empty
     // current tail's next must be pointed to new_node
     // current tail is replaced by new_node (whether empty or not)

Add the following lines to function main(); execute the program to see that the list object methods and functions are working properly.

inventory1.add_back( Item{"Cap of Health", 2} );
inventory1.add_back( Item{"Captain's Pike",  1} );

dbg << "inventory1 listings with 4 nodes (head: Potion of Health, tail: Captain's Pike):\n"
    << inventory1 << endl;

ItemList inventory2;

inventory2.add_back( Item{"Ruby Wand", 1} );
inventory2.add_back( Item{"Greatsword"} );
inventory2.add_front( Item{"Cloak of Shadows", 3} );

dbg << "inventory2 listings with 3 nodes (head: Cloak of Shadows, tail: Greatsword):\n"
    << inventory2 << endl;

Verify that the output looks like the following:

inventory1 listings with 4 nodes (head: Potion of Health, tail: Captain's Pike):          
Potion of Health              1 ( Stone Shield )                     
Stone Shield                  1 ( Cap of Health )                     
Cap of Health                 2 ( Captain's Pike )                      
Captain's Pike                1 ( -------- )                  
                                                                      
inventory2 listings with 3 nodes (head: Cloak of Shadows, tail: Greatsword):         
Cloak of Shadows              3 ( Ruby Wand )                     
Ruby Wand                     1 ( Greatsword )                     
Greatsword                    0 ( -------- )


Labcheckpoint.png FOR IN-LAB CREDIT: Explain to the lab instructor how the displayed results reflect the sequence of head and tail additions above.


Removing from the Head of a List

Add a prototype for another method to the ItemList class.

Item remove_front ( );

Removing from the head of a list is, as one would expect, a matter of undoing an addition to the head of the list. The method to perform this task can return the value of the Item data removed from the head; in the event the list was empty to begin with, an exception is thrown to indicate failure. In the event the list was not empty prior to the request, the head is made to point to the node following the current head. If this pointer is found to be nullptr, the list has just become empty and the tail pointer should be updated to reflect same; if this next pointer is not nullptr, it should be changed to nullptr as the node has been removed from the list and should no longer be tied to it. The node being removed must be deleted to avoid leaking memory.

Complete the following algorithm for the remove_front() method.

if // the list is empty
    throw std::length_error{ "Cannot remove from an empty list." };
ItemNode* old_head = head;
Item      result   = // get the game item value at the front for later return
// move head pointer to the next item in the list
if // there was no "next item", the list is now going empty
    // so set tail to nullptr as well
// delete the old head node
// return the result value you stored earlier
  • Note:** You will need to include the <stdexcept> library in order to use std::length_error.

As an aid to verifying the correct operation of the remove_front() method, add a destructor to class ItemNode which displays the name stored in the node being destroyed.

Test the remove_front() method with the following addition to function main().

try {
    Item first = inventory1.remove_front( );

    dbg << "removed from head of inventory1:\n"
        << first << "\n"
        << "inventory1 now:\n"
        << inventory1 << endl;
} 
catch ( const std::length_error& e ) { 
    dbg << e.what( ) << "\n"; 
}

Your output file should have gained the following lines:

removed from head of inventory1:                                     
Potion of Health              1                               
inventory1 now:                                              
Stone Shield                  1 ( Cap of Health )                     
Cap of Health                 2 ( Captain's Pike )                      
Captain's Pike                1 ( -------- )

And you should have seen the following on the screen:

deleting node containing Potion of Health                                        
deleting node containing Potion of Fire Walking                                         
deleting node containing Amulet of Feasting

The line ending in “Potion of Health” was produced because we deleted that node when we removed from the front… Where did the other two lines come from?


Labcheckpoint.png FOR IN-LAB CREDIT: Answer the question above for the lab instructor, then explain to the lab instructor why there can be no highly efficient method for removing from the end of the list.


Erasing a List

It will often be handy to be able to erase the data that has been added to a list without disposing of the list itself. Add the following prototype to the unordered list class definition.

void erase ( );

This list class method will need to free up the memory associated with a list class, just as the destructor for the class should; in fact, the destructor for this class can simply call this method. This method can perform its task by repeatedly calling remove_front() as long as the list is not empty. Write this method now and test it with the following addition to function main().

inventory2.erase ();
dbg << "inventory2 listings after erase:\n" << inventory2 << "\n" << endl;

After testing the erase method, take this opportunity to implement the destructor for the class (just call erase from the destructor).


Labsubmitsinglefile.png FOR IN-LAB CREDIT: Zip up these files: All files needed for this laboratory.
Name the file oopiL-lists.zip and upload to CSCADE.