{"id":33,"date":"2024-08-01T18:35:48","date_gmt":"2024-08-01T18:35:48","guid":{"rendered":"https:\/\/bhiggs.x10hosting.com\/PracticalC%2B%2BProgramming\/?page_id=33"},"modified":"2025-01-20T20:43:53","modified_gmt":"2025-01-20T20:43:53","slug":"assignment-4","status":"publish","type":"page","link":"https:\/\/bhiggs.x10hosting.com\/PracticalCPlusPlusProgramming\/index.php\/assignments\/assignment-4\/","title":{"rendered":"Assignment 4"},"content":{"rendered":"\n

<\/span>Linked Lists<\/span><\/h3>\n\n\n\n

<\/span>What is a Linked List?<\/em><\/span><\/h4>\n\n\n\n

Linked lists are among the most useful data structures in Computer Science, and are therefore very heavily used in lots of different applications. For this assignment, we will concentrate on the doubly-linked list<\/em>, which is perhaps the most useful of all linked lists. Here’s what a doubly-linked list looks like:<\/p>\n\n\n\n

\"\"<\/figure>\n\n\n\n

As you can see, the linked list consists of a number of list items<\/em> linked together in both the forward direction and the reverse direction. The links are typically pointers, and that is what we will use to implement this kind of list.<\/p>\n\n\n\n

<\/span>Why are Linked Lists so Useful?<\/em><\/span><\/h4>\n\n\n\n

Linked lists are useful because they are very flexible. You can use a linked list as a collection<\/em> mechanism; that is, the linked list can collect together items which have something in common with each other. For example, perhaps you wish to collect together all the people who work in your office. Or all the people who work for a particular boss.<\/p>\n\n\n\n

Sometimes the order of items in a list is important, and sometimes it isn’t. It all depends on what your needs might be. Perhaps you don’t care about the order at all, in which case you could treat the items in a list as a set<\/em> of items (in the Mathematical sense), or a multi-set<\/em> of items (where the value of an item can be duplicated within the list).<\/p>\n\n\n\n

Alternatively, you might wish to maintain the items in the list in a particular order — perhaps alphabetically, or by employee number, or by salary.<\/p>\n\n\n\n

<\/span>Linked List Operations<\/em><\/span><\/h4>\n\n\n\n

There are obviously a number of useful operations that a linked list should support. For example:<\/p>\n\n\n\n

    \n
  1. Adding an item to a list<\/li>\n\n\n\n
  2. Removing an item from a list<\/li>\n\n\n\n
  3. Determining whether an item is currently in the list or not.<\/li>\n\n\n\n
  4. Determining how many items are currently in the list<\/li>\n\n\n\n
  5. Navigating through the list in order to access the items in a list<\/li>\n<\/ol>\n\n\n\n

    Depending on how you are using the list, you may need only the ability to add or remove an item at the end of a list, or at the front of a list, or to add or remove an item anywhere in the list. Similarly, you may need only to navigate the list from the start to the end, or you may need to move both in the forward direction or in the reverse direction. You may wish to start at the beginning of the list, at its end, or anywhere in between.<\/p>\n\n\n\n

    <\/span>Doubly-Linked Lists<\/em><\/span><\/h4>\n\n\n\n

    The doubly-linked list is very flexible in its ability to support the above features. Doubly-linked lists allow you to:<\/p>\n\n\n\n

      \n
    1. Add an item anywhere in the list<\/li>\n\n\n\n
    2. Remove an item from anywhere in the list<\/li>\n\n\n\n
    3. Navigate in any direction, from any starting point in the list<\/li>\n<\/ol>\n\n\n\n

      The doubly-linked list supports these features by using two pointers in each list item:<\/p>\n\n\n\n

        \n
      1. A next<\/em> pointer<\/li>\n\n\n\n
      2. A previous<\/em> pointer<\/li>\n<\/ol>\n\n\n\n

        In addition, it is very useful to add one more pointer in each list item:<\/p>\n\n\n\n

          \n
        1. A list<\/em> pointer — a pointer to the list in which the list item currently resides<\/li>\n<\/ol>\n\n\n\n

          The next<\/em> pointer, as its name suggests, points to the next list item in the list. The previous<\/em> pointer similarly points to the previous list item in the list. If a list item is the first one in the list, then its previous<\/em> pointer is NULL. If a list item is the last one in the list, then its next<\/em> pointer is NULL. In this way, we can navigate through the list and have a way of ensuring that we don’t “fall off” at either end of the list.<\/p>\n\n\n\n

          The list<\/em> pointer serves two purposes:<\/p>\n\n\n\n

            \n
          1. A flag indicating whether the list item is currently in a list (we assume that a list item is either in a single list, or it is in no list). If the list item is not currently in a list, then its list<\/em> pointer is NULL. If the list item is currently in a list, then the list pointer points to the owning list.<\/li>\n\n\n\n
          2. If the list item is in a list, then the list pointer provides convenient access to the owning list’s context, which the list item code will need for its purposes.<\/li>\n<\/ol>\n\n\n\n

            <\/span>Class Design<\/em><\/span><\/h4>\n\n\n\n

            To implement such a doubly-linked list, we will be implementing three classes:<\/p>\n\n\n\n

              \n
            • A List<\/strong> class, each instance of which represents a doubly-linked list<\/li>\n\n\n\n
            • A ListItem<\/strong> class, each instance of which represents an item that can exist in a List<\/strong><\/li>\n\n\n\n
            • A ListIterator<\/strong> class, which encapsulates the necessary context to allow multiple concurrent iterations (navigations) through a List<\/strong><\/li>\n<\/ul>\n\n\n\n

              What must each class provide to support the necessary features? <\/p>\n\n\n\n

              Well, let’s cut to the chase, and give you some code to start with:<\/p>\n\n\n\n

              \n
              \n
              <\/path><\/path><\/svg><\/span>
              \/\/<\/span><\/span>\n\/\/  List.h<\/span><\/span>\n\/\/  Assignment 4: Linked Lists<\/span><\/span>\n\/\/<\/span><\/span>\n\/\/  Created by Bryan Higgs on 10\/31\/24.<\/span><\/span>\n\/\/<\/span><\/span>\n<\/span>\n#ifndef<\/span> List_h<\/span><\/span>\n#define<\/span> List_h<\/span><\/span>\n<\/span>\n#include<\/span> <\/span><string><\/span><\/span>\nusing<\/span> <\/span>namespace<\/span> <\/span>std<\/span>;<\/span><\/span>\n<\/span>\n\/\/ Forward references<\/span><\/span>\n<\/span>\nclass<\/span> <\/span>ListItem<\/span>;<\/span><\/span>\n<\/span>\n\/\/ Class List<\/span><\/span>\n<\/span>\nclass<\/span> <\/span>List<\/span><\/span>\n{<\/span><\/span>\n  <\/span>friend<\/span> <\/span>class<\/span> <\/span>ListItem<\/span>;<\/span><\/span>\n<\/span>\npublic:<\/span><\/span>\n  <\/span>List<\/span>();<\/span>   \/\/ Constructor<\/span><\/span>\n  <\/span>~List<\/span>();<\/span>  \/\/ Destructor<\/span><\/span>\n<\/span>\n  \/\/ Access<\/span><\/span>\n  <\/span>ListItem<\/span> <\/span>*<\/span>GetFirst<\/span>() <\/span>const<\/span>;<\/span> \/\/ Returns ptr to first item in list<\/span><\/span>\n  <\/span>ListItem<\/span> <\/span>*<\/span>GetLast<\/span>() <\/span>const<\/span>;<\/span>  \/\/ Returns ptr to last item in list<\/span><\/span>\n  <\/span>int<\/span> <\/span>GetCount<\/span>() <\/span>const<\/span>;<\/span>       \/\/ Returns count of items in list<\/span><\/span>\n<\/span>\n  \/\/ Operations<\/span><\/span>\n  <\/span>void<\/span> <\/span>Append<\/span>(<\/span>ListItem<\/span> <\/span>&<\/span>item<\/span>);<\/span> \/\/ Appends an item to the end of the list<\/span><\/span>\n  <\/span>void<\/span> <\/span>Purge<\/span>();<\/span>                \/\/ Removes all items from the list<\/span><\/span>\n<\/span>\n  \/\/ Debugging member functions<\/span><\/span>\n  <\/span>void<\/span> <\/span>Dump<\/span>(<\/span>const<\/span> <\/span>string<\/span> <\/span>prefix<\/span> = <\/span>""<\/span>) <\/span>const<\/span>;<\/span><\/span>\n                              \/\/ Dump contents of list<\/span><\/span>\n                              \/\/ (prefix is a string that prefixes<\/span><\/span>\n                              \/\/  each line of the dumped output)<\/span><\/span>\n<\/span>\nprivate:<\/span><\/span>\n  \/\/ Disable copy constructor for List<\/span><\/span>\n  <\/span>List<\/span>(<\/span>const<\/span> <\/span>List<\/span> <\/span>&<\/span>);<\/span><\/span>\n  \/\/ Disable assignment for List<\/span><\/span>\n  <\/span>List<\/span> <\/span>&<\/span>operator=<\/span>(<\/span>const<\/span> <\/span>List<\/span> <\/span>&<\/span>);<\/span><\/span>\n<\/span>\n  \/\/ Data members<\/span><\/span>\n  ListItem *m_first;<\/span>    \/\/ Pointer to the first list item<\/span><\/span>\n  ListItem *m_last;<\/span>    \/\/ Pointer to the last list item<\/span><\/span>\n  <\/span>int<\/span> m_count;<\/span>         \/\/ Count of list items currently in list<\/span><\/span>\n};<\/span><\/span>\n<\/span>\n\/\/ Class ListItem<\/span><\/span>\n<\/span>\nclass<\/span> <\/span>ListItem<\/span><\/span>\n{<\/span><\/span>\npublic:<\/span><\/span>\n  <\/span>ListItem<\/span>(<\/span>void<\/span> <\/span>*<\/span>data<\/span>);<\/span>    \/\/ Constructor (associates with data)<\/span><\/span>\n  <\/span>~ListItem<\/span>();<\/span>            \/\/ Destructor<\/span><\/span>\n<\/span>\n  \/\/ Operations<\/span><\/span>\n  <\/span>void<\/span> <\/span>Add<\/span>(<\/span>List<\/span> <\/span>&<\/span>list<\/span>, <\/span>ListItem<\/span> <\/span>*<\/span>prevItem<\/span>);<\/span><\/span>\n                          \/\/ Add this ListItem to the specified list<\/span><\/span>\n                          \/\/ following the specified prevItem<\/span><\/span>\n                          \/\/ (if prevItem is NULL, place at front of list)<\/span><\/span>\n<\/span>\n  <\/span>void<\/span> <\/span>Remove<\/span>();<\/span>            \/\/ Remove this list item from the list it is in<\/span><\/span>\n<\/span>\n  \/\/ Access member functions<\/span><\/span>\n  <\/span>ListItem<\/span> <\/span>*<\/span>GetNext<\/span>() <\/span>const<\/span>;<\/span>     \/\/ Return ptr to next item in list<\/span><\/span>\n  <\/span>ListItem<\/span> <\/span>*<\/span>GetPrevious<\/span>() <\/span>const<\/span>;<\/span> \/\/ Return ptr to previous item in list<\/span><\/span>\n  <\/span>const<\/span> <\/span>List<\/span> <\/span>*<\/span>GetList<\/span>() <\/span>const<\/span>;<\/span>   \/\/ Return ptr to the list item's list<\/span><\/span>\n  <\/span>void<\/span> <\/span>*<\/span>GetData<\/span>();<\/span>               \/\/ Returns ptr to data for item<\/span><\/span>\n<\/span>\n  \/\/ Debugging member functions<\/span><\/span>\n  <\/span>void<\/span> <\/span>Dump<\/span>(<\/span>const<\/span> <\/span>string<\/span> <\/span>prefix<\/span> = <\/span>""<\/span>) <\/span>const<\/span>;<\/span><\/span>\n                              \/\/ Dump contents of list item<\/span><\/span>\n                              \/\/ (prefix is a string that prefixes<\/span><\/span>\n                              \/\/  each line of the dumped output)<\/span><\/span>\nprivate:<\/span><\/span>\n  \/\/ Disable copy constructor for ListItem<\/span><\/span>\n  <\/span>ListItem<\/span>(<\/span>const<\/span> <\/span>ListItem<\/span> <\/span>&<\/span>);<\/span><\/span>\n  \/\/ Disable assignment for ListItem<\/span><\/span>\n  <\/span>ListItem<\/span> <\/span>&<\/span>operator=<\/span>(<\/span>const<\/span> <\/span>ListItem<\/span> <\/span>&<\/span>);<\/span><\/span>\n<\/span>\n  \/\/ Data members<\/span><\/span>\n  ListItem  *m_next;<\/span>    \/\/ Pointer to next item in the list<\/span><\/span>\n  ListItem  *m_prev;<\/span>    \/\/ Pointer to previous item in the list<\/span><\/span>\n  List      *m_list;<\/span>    \/\/ Pointer to the list the item currently is in<\/span><\/span>\n  <\/span>void<\/span>      *m_data;<\/span>    \/\/ Pointer to data<\/span><\/span>\n};<\/span><\/span>\n<\/span>\n\/\/ Class ListIterator<\/span><\/span>\n<\/span>\nclass<\/span> <\/span>ListIterator<\/span><\/span>\n{<\/span><\/span>\npublic:<\/span><\/span>\n  <\/span>ListIterator<\/span>(<\/span>const<\/span> <\/span>List<\/span> <\/span>&<\/span>list<\/span>);<\/span>  \/\/ Constructor<\/span><\/span>\n  <\/span>~ListIterator<\/span>();<\/span>           \/\/ Destructor<\/span><\/span>\n<\/span>\n  \/\/ Access<\/span><\/span>\n  <\/span>const<\/span> <\/span>List<\/span> <\/span>*<\/span>GetList<\/span>() <\/span>const<\/span>;<\/span> \/\/ Return ptr to the iterator's list<\/span><\/span>\n  <\/span>ListItem<\/span> <\/span>*<\/span>GetCurrent<\/span>() <\/span>const<\/span>;<\/span>\/\/ Return ptr to current list item<\/span><\/span>\n  <\/span>ListItem<\/span> <\/span>*<\/span>GetNext<\/span>();<\/span>         \/\/ Move to next item and return ptr to it<\/span><\/span>\n  <\/span>ListItem<\/span> <\/span>*<\/span>GetPrevious<\/span>();<\/span>     \/\/ Move to previous item and return ptr to it<\/span><\/span>\n  <\/span>bool<\/span>  <\/span>AtFirst<\/span>() <\/span>const<\/span>;<\/span>       \/\/ return true if current item is first item<\/span><\/span>\n  <\/span>bool<\/span>  <\/span>AtLast<\/span>() <\/span>const<\/span>;<\/span>        \/\/ return true if current item is last item<\/span><\/span>\n<\/span>\nprivate:<\/span><\/span>\n  \/\/ Disable copy constructor for ListIterator<\/span><\/span>\n  <\/span>ListIterator<\/span>(<\/span>const<\/span> <\/span>ListIterator<\/span> <\/span>&<\/span>);<\/span><\/span>\n  \/\/ Disable assignment for ListIterator<\/span><\/span>\n  <\/span>ListIterator<\/span> <\/span>&<\/span>operator=<\/span>(<\/span>const<\/span> <\/span>ListIterator<\/span> <\/span>&<\/span>);<\/span><\/span>\n<\/span>\n  \/\/ Data<\/span><\/span>\n  <\/span>const<\/span> List *m_list;<\/span>       \/\/ The list we are iterating through<\/span><\/span>\n  ListItem   *m_current;<\/span>    \/\/ Points to the current item in the list<\/span><\/span>\n};<\/span><\/span>\n<\/span>\n#endif<\/span> \/* List_h *\/<\/span><\/span><\/code><\/pre><\/div>\n<\/div>\n\n\n\n
              \n
              \n
              Note<\/strong>: The above classes are incomplete, and show no implementation details. That’s your job!<\/p>\n<\/blockquote>\n\n\n\n
              \n
              Warning<\/strong>: Do not change any of these class members, their signatures, or their access (public or private). Furthermore, do not add any other data members or member functions. These classes will be used and modified in specific ways in later assignments, and if you change them here, you will have difficulty following the instructions in the later assignments. BEWARE<\/em><\/strong>!<\/p>\n<\/blockquote>\n<\/div>\n<\/div>\n\n\n\n
              <\/span>The <\/em>List<\/code> Class<\/em><\/span><\/h4>\n\n\n\n
              As you might guess, a doubly-linked list is represented by an instance of class List<\/strong>. Its primary purpose is to provide the necessary state of the list — specifically, to point at the first item in the list, and the last item in the list, so that we can start navigation at the appropriate places. It also keeps track of the number of items currently in the list.<\/p>\n\n\n\n
              Aside from the obvious access methods, the List class supports two operations:<\/p>\n\n\n\n
                \n
              • Append()<\/code><\/strong> — adds an item to the end of the List<\/strong><\/li>\n\n\n\n
              • Purge()<\/code><\/strong> — removes all items from the List<\/strong>.<\/li>\n<\/ul>\n\n\n\n
                \n
                Hint<\/strong>: Where, in particular, would you think the Purge()<\/code><\/strong> operation would be useful within the List class?<\/p>\n<\/blockquote>\n\n\n\n
                In addition, there is a Dump()<\/code><\/strong> member function, which is a convenient debugging tool.  It prints out the contents of the list in internal form — that is, the hexadecimal values of the List<\/code><\/strong>‘s private pointers, and also prints out the internal contents of each of the ListItem<\/code><\/strong>s in the List<\/code><\/strong>.<\/p>\n\n\n\n
                <\/span>The <\/em>ListItem<\/code> Class<\/em><\/span><\/h4>\n\n\n\n
                Not surprisingly, an item in a doubly-linked list is represented by an instance of class ListItem<\/code><\/strong>. Its primary purpose is to hold the three pointers we talked about above, and to support the basic operations on a ListItem<\/code><\/strong>:<\/p>\n\n\n\n
                  \n
                • ListItem()<\/code><\/strong>— the constructor associates data with the list item. Since we don’t know what you might want to put in a list, this is a void *<\/code><\/strong> pointer, which must be cast appropriately, once you retrieve the data from a list item.<\/li>\n\n\n\n
                • Add()<\/code><\/strong> — adds the item to a specified List<\/strong>, following the specified previous item. [Hint<\/strong>: What should this do if the item is already in a List<\/code><\/strong>?]<\/em><\/li>\n\n\n\n
                • Remove()<\/code><\/strong> — removes the item from the List<\/code><\/strong> it is in. [Hint<\/strong>: What should this do if the item is not in any List ?]<\/em><\/li>\n\n\n\n
                • Data()<\/code><\/strong>— this returns a void *<\/code><\/strong> pointer to the data the list item represents. Typically, this must be typecast to the proper type before you can use the pointer to access the data structure.  This implies that you must already know what is being held in the list item.<\/li>\n<\/ul>\n\n\n\n
                  \n
                  Hint<\/strong>: What should the ListItem<\/code><\/strong> destructor do? <\/strong><\/em><\/p>\n<\/blockquote>\n\n\n\n
                  As before, there is a Dump()<\/code><\/strong> member function, which is a convenient debugging tool.  It prints out the contents of the list item in internal form — that is, the hexadecimal values of the ListItem<\/code><\/strong>‘s private pointers.<\/p>\n\n\n\n
                  <\/span>The <\/em>ListIterator<\/code> Class<\/em><\/span><\/h4>\n\n\n\n
                  Whenever you wish to navigate through a doubly-linked list, you need to maintain some context — where you are currently positioned within the list. We could have maintained that context within the List<\/code><\/strong> class itself, but that would mean that we could only have a single navigation active against a specific list at a time. That is often quite restrictive, so instead we invent a class, ListIterator<\/code><\/strong>, which serves to maintain the necessary context, and in general encapsulates the necessary support for iterating (navigating) through a specific list.<\/p>\n\n\n\n
                  ListIterator<\/code><\/strong> supports the following operations:<\/p>\n\n\n\n
                    \n
                  • ListIterator()<\/code><\/strong> — the constructor is responsible for associating the ListIterator<\/code><\/strong> with the specified List<\/code><\/strong>, and for setting its starting position at the first item in that List<\/code><\/strong>.<\/li>\n\n\n\n
                  • GetList()<\/code><\/strong> — Returns a pointer to the associated List<\/code><\/strong>.<\/li>\n\n\n\n
                  • GetNext()<\/code><\/strong> — Moves the current position to the next item in the List<\/code><\/strong>. If there is no next item, does not change the current position, and returns NULL<\/strong><\/code>.<\/li>\n\n\n\n
                  • GetPrevious()<\/code><\/strong> — Moves the current position to the previous item in the List<\/code><\/strong>. If there is no previous item, does not change the current position, and returns NULL<\/code><\/strong>.<\/li>\n\n\n\n
                  • AtFirst()<\/code><\/strong> — returns a Boolean value indicating whether the current position is at the first item in the List<\/code><\/strong><\/li>\n\n\n\n
                  • AtLast()<\/code><\/strong> — returns a Boolean value indicating whether the current position is at the last item in the List<\/code><\/strong>.<\/li>\n\n\n\n
                  • GetCurrent()<\/code><\/strong> — This is merely an access method, and returns a pointer to the current item for the ListIterator<\/code><\/strong>. There should always be a current item for a ListIterator<\/code><\/strong> (i.e. it should never become NULL<\/strong><\/code>, nor should it point at anything other than a list item that is in the List<\/code><\/strong> being navigated by the ListIterator<\/code><\/strong>.).  There is only one exception to this: When the ListIterator<\/code><\/strong> is associated with a List<\/code> <\/strong>that is currently empty;  only in that case may the GetCurrent()<\/code><\/strong> member function return a null pointer.  (Note, however, that the ListIterator<\/code><\/strong> class should be able to handle the case where the association is made with an empty list, and subsequently the list has items added to it. See below<\/strong><\/em>.)<\/li>\n<\/ul>\n\n\n\n
                    <\/span>The Assignment<\/span><\/h3>\n\n\n\n
                    Your task is to implement the three classes, List<\/code><\/strong>, ListItem<\/code><\/strong> and ListIterator<\/code><\/strong>. Place the class declarations all in a single file, list.h (as shown in the above code), and their implementations in a single file, list.cpp.<\/p>\n\n\n\n
                    Here are some hints you will need to pay attention to:<\/p>\n\n\n\n
                      \n
                    • Since these classes refer to each other, we need to use one or more forward references<\/em> so that the classes will compile. Thus the need to specify the following line before<\/em> the List<\/strong> class declaration:<\/li>\n<\/ul>\n\n\n\n
                      class ListItem;<\/strong><\/code><\/pre>\n\n\n\n
                      This will forward declare the ListItem<\/strong> class so that the List<\/strong> class can refer to ListItem<\/strong> without the compiler complaining. Note that, since a forward declaration does not provide any information about a class other than its name, if you have code that refers to information about that class, such as its size or its members, your compiler will complain — sometimes with some very strange error messages!<\/p>\n\n\n\n
                        \n
                      • These three classes work together as a family of classes<\/em> to support a single piece of functionality. It is necessary to declare appropriate friendship relationships among the classes. I have already included the necessary friendship declarations;  try to keep these to a minimum — do not<\/strong><\/em> make every class a friend of every other class.  In fact, you do not need to make any additions of this kind for this assignment.<\/li>\n\n\n\n
                      • Since all of these classes contain data members which are pointers, we have disabled their copy constructors and assignment operators, by placing the declarations of those methods in the class’s private section.  You do not need to implement these member functions.<\/li>\n<\/ul>\n\n\n\n
                        Start by placing all your implementation code in the list.cpp<\/code><\/strong> file, and don’t worry about run-time efficiency. It’s much better to get the code working first, and then worry about how to make it fast — not the other way around. Later, if you have time, you can consider making the appropriate modifications to speed up the code — mostly making essential member functions inline<\/strong>.<\/p>\n\n\n\n
                        To give you a starting point, here is a start at the list.cpp<\/strong><\/code> file, with the Dump()<\/strong><\/code> member functions coded for you:<\/p>\n\n\n\n
                        \n
                        \n
                        <\/path><\/path><\/svg><\/span>
                        \/\/<\/span><\/span>\n\/\/  List.cpp<\/span><\/span>\n\/\/  Assignment 4: Linked Lists<\/span><\/span>\n\/\/<\/span><\/span>\n\/\/  Created by Bryan Higgs on 10\/31\/24.<\/span><\/span>\n\/\/<\/span><\/span>\n<\/span>\n#include<\/span> <\/span><iostream><\/span><\/span>\n#include<\/span> <\/span><cassert><\/span>  <\/span>\/\/ For assert() -- use encouraged!<\/span><\/span>\nusing<\/span> <\/span>namespace<\/span> <\/span>std<\/span>;<\/span><\/span>\n<\/span>\n#include<\/span> <\/span>"list.h"<\/span><\/span>\n<\/span>\n\/\/ List<\/span><\/span>\n<\/span>\nvoid<\/span> <\/span>List<\/span>::<\/span>Dump<\/span>(<\/span>const<\/span> <\/span>string<\/span> <\/span>prefix<\/span>) <\/span>const<\/span><\/span>\n{<\/span><\/span>\n  \/\/ Print List information<\/span><\/span>\n  cout << prefix << <\/span>"List at: "<\/span> << <\/span>this<\/span> << endl<\/span><\/span>\n       << prefix << <\/span>" Count:  "<\/span> << <\/span>GetCount<\/span>() << endl<\/span><\/span>\n       << prefix << <\/span>" First:  "<\/span> << <\/span>GetFirst<\/span>() << endl<\/span><\/span>\n       << prefix << <\/span>" Last:   "<\/span> << <\/span>GetLast<\/span>() << endl;<\/span><\/span>\n<\/span>\n  \/\/ Print all the ListItems<\/span><\/span>\n  <\/span>for<\/span> (ListItem *item = <\/span>GetFirst<\/span>();<\/span><\/span>\n       item != <\/span>0<\/span>;<\/span><\/span>\n       item = <\/span>item<\/span>-><\/span>GetNext<\/span>()<\/span><\/span>\n      )<\/span><\/span>\n  {<\/span><\/span>\n      <\/span>item<\/span>-><\/span>Dump<\/span>(prefix + <\/span>"  "<\/span>);<\/span><\/span>\n  }<\/span><\/span>\n}<\/span><\/span>\n<\/span>\n\/\/ ListItem<\/span><\/span>\n<\/span>\nvoid<\/span> <\/span>ListItem<\/span>::<\/span>Dump<\/span>(<\/span>const<\/span> <\/span>string<\/span> <\/span>prefix<\/span>) <\/span>const<\/span><\/span>\n{<\/span><\/span>\n  cout << prefix << <\/span>" ListItem: "<\/span> << <\/span>this<\/span> << endl<\/span><\/span>\n       << prefix << <\/span>"   Next:  "<\/span> << <\/span>GetNext<\/span>() << endl<\/span><\/span>\n       << prefix << <\/span>"   Prev:  "<\/span> << <\/span>GetPrevious<\/span>() << endl;<\/span><\/span>\n}<\/span><\/span>\n<\/span>\n\/\/ ListIterator<\/span><\/span>\n<\/span><\/code><\/pre><\/div>\n<\/div>\n\n\n\n
                        \n
                        Of course, there’s lots else for you to fill in in this file!<\/p>\n\n\n\n
                        \n
                        Hints:<\/strong><\/p>\n\n\n\n
                          \n
                        • Remember to use initializer lists whenever possible<\/li>\n\n\n\n
                        • Try to avoid duplicating code as much as possible.  For example, there should be one, and only one, place where you provide code to add an element to a list; there should be one, and only one, place where you provide code to remove an element from a list.<\/li>\n\n\n\n
                        • Think about your List::Append<\/strong> member function: How should you implement it with the least amount of effort? 
                          [Hint: My version of this function has a body consisting of a single statement.]<\/em><\/strong><\/li>\n\n\n\n
                        • Think about how to code using as simple algorithms as possible (but not too simple!).  For example, my code for the List::Purge<\/strong> member function contains of four lines of code within the body of the function — and two of those lines each consists of a single curly brace.<\/li>\n\n\n\n
                        • Use the Dump<\/strong> member functions during your debugging — there’s a reason why I provided them for you to use!<\/li>\n\n\n\n
                        • When you come to write the code for adding an item to a list, remember that there are basically three cases:
                          • When the item is to be inserted at the start of the list<\/li>
                          • When the item is to be inserted at the end of the list<\/li>
                          • When the item is to be inserted somewhere in the middle of the list.<\/li><\/ul>and remember that adding an item to an empty list is a special case of both of the first and second cases<\/em>.   Try to ensure that you have all the necessary cases covered, and that the various data members which are pointers to various items in the list are all properly updated in all of the cases.  It’s easy to forget one or two!  Try to develop consistent practices.  It’s often helpful to draw yourself a diagram of all the links, before, during, and after an item is added to a list.<\/li>\n\n\n\n
                          • Similar thinking applies to when you come to write the code to remove an item from a list.<\/li>\n\n\n\n
                          • It may appear at first glance that the ListIterator::GetCurrent()<\/strong> member function is trivial to implement.  It would be, if it were not for the following situation that I wish this iterator to handle:
                            • The iterator is created to be associated with a list that is empty.<\/li>
                            • Subsequently, items are added and removed from the list<\/li>
                            • The iterator is then used to iterate over the items in the list, based on the items that are actually in the list at that time.<\/li><\/ul>[Hint: What if the list was not empty when the iterator is created, but subsequently items are added to the beginning of the list before the iterator is used?   What should the iterator do then?]
                              This means that the code for GetCurrent<\/strong> is not quite as simple as you might think.  In particular, while GetCurrent<\/strong> is conceptually const, because it must handle the above case, you will have to code it in such a way that it is not<\/em> const.  See the slides on the web site for how to do this.<\/li>\n\n\n\n
                            • One more thing about GetCurrent<\/strong>:  It should only return with a NULL pointer under one condition:  if its associated list is currently empty<\/em>.  Under all other circumstances, it should return a valid pointer to the list item that is currently located at within its associated list.  In particular, attempting to move from the last item in the list to the (non-existent) next item, or attempting to move from the first item in the list to the (non-existent) previous item, should not affect the value of the current pointer at all.<\/li>\n<\/ul>\n<\/blockquote>\n<\/div>\n<\/div>\n\n\n\n
                              <\/span>Testing Your Implementation<\/span><\/h4>\n\n\n\n
                              I’ve discovered that some of my students seem to struggle to create a thorough test for their implementation.  So, to provide a (hopefully) good example of how to test, and to provide you with some guidance on what constitutes correct operation, here is a test program that tests just the basic List<\/code><\/strong>\/ListItem<\/code><\/strong>\/ListIterator<\/code><\/strong> class operations:<\/p>\n\n\n\n
                              \n
                              \n
                              <\/path><\/path><\/svg><\/span>
                              \/\/<\/span><\/span>\n\/\/  TestList.cpp<\/span><\/span>\n\/\/  Assignment 4: Linked Lists<\/span><\/span>\n\/\/<\/span><\/span>\n\/\/  Created by Bryan Higgs on 10\/31\/24.<\/span><\/span>\n\/\/<\/span><\/span>\n<\/span>\n#include<\/span> <\/span><iostream><\/span><\/span>\nusing<\/span> <\/span>namespace<\/span> <\/span>std<\/span>;<\/span><\/span>\n<\/span>\n#include<\/span> <\/span>"List.h"<\/span><\/span>\n<\/span>\n\/*<\/span><\/span>\n * Tests a ListIterator, by iterating forward through the list,<\/span><\/span>\n * then backward, then forward again.<\/span><\/span>\n *\/<\/span><\/span>\nvoid<\/span> <\/span>testIterator<\/span>(<\/span>ListIterator<\/span> <\/span>&<\/span>iter<\/span>)<\/span><\/span>\n{<\/span><\/span>\n  cout << <\/span>"The list contains "<\/span> << <\/span>iter<\/span>.<\/span>GetList<\/span>()-><\/span>GetCount<\/span>()<\/span><\/span>\n                               << <\/span>" items"<\/span> << endl;<\/span><\/span>\n  cout << <\/span>"The iterator is at the start of the list: "<\/span><\/span>\n                               << boolalpha << <\/span>iter<\/span>.<\/span>AtFirst<\/span>() << endl;<\/span><\/span>\n<\/span>\n  ListItem *item = <\/span>0<\/span>;<\/span><\/span>\n  cout << <\/span>"Iterating forward..."<\/span> << endl;<\/span><\/span>\n  <\/span>for<\/span> ( item = <\/span>iter<\/span>.<\/span>GetCurrent<\/span>(); item != <\/span>0<\/span>; item = <\/span>iter<\/span>.<\/span>GetNext<\/span>() )<\/span><\/span>\n  {<\/span><\/span>\n    <\/span>double<\/span> *d = (<\/span>double<\/span> *) <\/span>item<\/span>-><\/span>GetData<\/span>();<\/span><\/span>\n    cout << *d << endl;<\/span><\/span>\n  }<\/span><\/span>\n<\/span>\n  cout << <\/span>"The iterator is at the end of the list: "<\/span><\/span>\n       << boolalpha << <\/span>iter<\/span>.<\/span>AtLast<\/span>() << endl;<\/span><\/span>\n  cout << <\/span>"Iterating backward..."<\/span> << endl;<\/span><\/span>\n  <\/span>for<\/span> ( item = <\/span>iter<\/span>.<\/span>GetCurrent<\/span>(); item != <\/span>0<\/span>; item = <\/span>iter<\/span>.<\/span>GetPrevious<\/span>() )<\/span><\/span>\n  {<\/span><\/span>\n    <\/span>double<\/span> *d = (<\/span>double<\/span> *) <\/span>item<\/span>-><\/span>GetData<\/span>();<\/span><\/span>\n    cout << *d << endl;<\/span><\/span>\n  }<\/span><\/span>\n<\/span>\n  cout << <\/span>"The iterator is at the start of the list: "<\/span><\/span>\n       << boolalpha << <\/span>iter<\/span>.<\/span>AtFirst<\/span>() << endl;<\/span><\/span>\n  cout << <\/span>"Iterating forward again..."<\/span> << endl;<\/span><\/span>\n  <\/span>for<\/span> ( item = <\/span>iter<\/span>.<\/span>GetCurrent<\/span>(); item != <\/span>0<\/span>; item = <\/span>iter<\/span>.<\/span>GetNext<\/span>() )<\/span><\/span>\n  {<\/span><\/span>\n    <\/span>double<\/span> *d = (<\/span>double<\/span> *) <\/span>item<\/span>-><\/span>GetData<\/span>();<\/span><\/span>\n    cout << *d << endl;<\/span><\/span>\n  }<\/span><\/span>\n}<\/span><\/span>\n<\/span>\n\/*<\/span><\/span>\n * Main entry point to do a fairly complete test of the basic<\/span><\/span>\n * List\/ListItem\/ListIterator classes.<\/span><\/span>\n *\/<\/span><\/span>\nint<\/span> <\/span>main<\/span>(<\/span>int<\/span> <\/span>argc<\/span>, <\/span>const<\/span> <\/span>char<\/span> <\/span>*<\/span> <\/span>argv<\/span>[])<\/span><\/span>\n{<\/span><\/span>\n  List list;<\/span><\/span>\n  ListIterator <\/span>iter1<\/span>(list);<\/span><\/span>\n<\/span>\n  cout << <\/span>"---Testing iteration through an empty list---"<\/span> << endl;<\/span><\/span>\n  <\/span>testIterator<\/span>(iter1);<\/span><\/span>\n<\/span>\n  cout << <\/span>"---Initial list---"<\/span> << endl;<\/span><\/span>\n  <\/span>list<\/span>.<\/span>Dump<\/span>();<\/span><\/span>\n<\/span>\n  <\/span>double<\/span> d1 = <\/span>1.0<\/span>, d2 = <\/span>2.0<\/span>, d3 = <\/span>3.0<\/span>, d4 = <\/span>4.0<\/span>;<\/span><\/span>\n<\/span>\n  ListItem <\/span>item1<\/span>(&d1);<\/span><\/span>\n  cout << <\/span>"---Appending list item---"<\/span> << endl;<\/span><\/span>\n  <\/span>list<\/span>.<\/span>Append<\/span>(item1);<\/span><\/span>\n  <\/span>list<\/span>.<\/span>Dump<\/span>();<\/span><\/span>\n<\/span>\n  ListItem <\/span>item2<\/span>(&d2);<\/span><\/span>\n  cout << <\/span>"---Adding list item to front of list---"<\/span> << endl;<\/span><\/span>\n  <\/span>item2<\/span>.<\/span>Add<\/span>(list, <\/span>0<\/span>);<\/span><\/span>\n  <\/span>list<\/span>.<\/span>Dump<\/span>();<\/span><\/span>\n<\/span>\n  ListItem <\/span>item3<\/span>(&d3);<\/span><\/span>\n  cout << <\/span>"---Inserting list item in the middle of list---"<\/span> << endl;<\/span><\/span>\n  <\/span>item3<\/span>.<\/span>Add<\/span>(list, &item2);<\/span><\/span>\n  <\/span>list<\/span>.<\/span>Dump<\/span>();<\/span><\/span>\n<\/span>\n  ListItem <\/span>item4<\/span>(&d4);<\/span><\/span>\n  cout << <\/span>"---Adding list item to the end of list---"<\/span> << endl;<\/span><\/span>\n  <\/span>item4<\/span>.<\/span>Add<\/span>(list, &item1);<\/span><\/span>\n  <\/span>list<\/span>.<\/span>Dump<\/span>();<\/span><\/span>\n<\/span>\n  cout << <\/span>"---Testing iterator initialized against full list---"<\/span> << endl;<\/span><\/span>\n<\/span>\n  ListIterator <\/span>iter2<\/span>(list);<\/span><\/span>\n  <\/span>testIterator<\/span>(iter2);<\/span><\/span>\n<\/span>\n  cout << <\/span>"---Testing iterator initialized against empty list---"<\/span> << endl;<\/span><\/span>\n  <\/span>testIterator<\/span>(iter1);<\/span><\/span>\n<\/span>\n  cout << <\/span>"---Testing removal of item from end of list---"<\/span> << endl;<\/span><\/span>\n  <\/span>item4<\/span>.<\/span>Remove<\/span>();<\/span><\/span>\n  <\/span>list<\/span>.<\/span>Dump<\/span>();<\/span><\/span>\n<\/span>\n  cout << <\/span>"---Testing removal of item from middle of list---"<\/span> << endl;<\/span><\/span>\n  <\/span>item3<\/span>.<\/span>Remove<\/span>();<\/span><\/span>\n  <\/span>list<\/span>.<\/span>Dump<\/span>();<\/span><\/span>\n<\/span>\n  cout << <\/span>"---Testing removal of item from front of list---"<\/span> << endl;<\/span><\/span>\n  <\/span>item2<\/span>.<\/span>Remove<\/span>();<\/span><\/span>\n  <\/span>list<\/span>.<\/span>Dump<\/span>();<\/span><\/span>\n<\/span>\n  cout << <\/span>"---Testing removal of item alone in list---"<\/span> << endl;<\/span><\/span>\n  <\/span>item1<\/span>.<\/span>Remove<\/span>();<\/span><\/span>\n  <\/span>list<\/span>.<\/span>Dump<\/span>();<\/span><\/span>\n<\/span>\n  cout << <\/span>"---Adding items back to list---"<\/span> << endl;<\/span><\/span>\n  <\/span>list<\/span>.<\/span>Append<\/span>(item1);<\/span><\/span>\n  <\/span>list<\/span>.<\/span>Append<\/span>(item2);<\/span><\/span>\n  <\/span>list<\/span>.<\/span>Append<\/span>(item3);<\/span><\/span>\n  <\/span>list<\/span>.<\/span>Append<\/span>(item4);<\/span><\/span>\n  <\/span>list<\/span>.<\/span>Dump<\/span>();<\/span><\/span>\n<\/span>\n  cout << <\/span>"---Testing purge---"<\/span> << endl;<\/span><\/span>\n  <\/span>list<\/span>.<\/span>Purge<\/span>();<\/span><\/span>\n  <\/span>list<\/span>.<\/span>Dump<\/span>();<\/span><\/span>\n<\/span>\n  cout << <\/span>"---Ending main function---"<\/span> << endl;<\/span><\/span>\n  cout << <\/span>"***You should be testing the List destructor***"<\/span> << endl;<\/span><\/span>\n<\/span>\n  <\/span>return<\/span> <\/span>0<\/span>;<\/span><\/span>\n}<\/span><\/span><\/code><\/pre><\/div>\n<\/div>\n\n\n\n
                              <\/div>\n<\/div>\n\n\n\n
                              <\/span>Using Your Implementation<\/em><\/span><\/h4>\n\n\n\n
                              <\/span>Wines<\/span><\/h5>\n\n\n\n
                              To give you an idea how you might use these classes in a real situation, here’s an example.<\/p>\n\n\n\n
                              Naturally, when I thought of lists, the first thing that came into my mind was a wine list!  <\/p>\n\n\n\n
                              So here’s a very simple Wine<\/code><\/strong> class, some of which you will be filling in.  Then there is a test program to give our list implementation a reasonable degree of testing in a wine list situation.column<\/p>\n\n\n\n
                              \n
                              \n
                              <\/path><\/path><\/svg><\/span>
                              \/\/<\/span><\/span>\n\/\/  Wine.h<\/span><\/span>\n\/\/  Assignment 4: Linked Lists<\/span><\/span>\n\/\/<\/span><\/span>\n\/\/  Created by Bryan Higgs on 10\/31\/24.<\/span><\/span>\n\/\/<\/span><\/span>\n<\/span>\n#ifndef<\/span> Wine_h<\/span><\/span>\n#define<\/span> Wine_h<\/span><\/span>\n<\/span>\n#include<\/span> <\/span><string><\/span><\/span>\nusing<\/span> <\/span>namespace<\/span> <\/span>std<\/span>;<\/span><\/span>\n<\/span>\nclass<\/span> <\/span>Wine<\/span><\/span>\n{<\/span><\/span>\npublic:<\/span><\/span>\n  <\/span>Wine<\/span>(<\/span>const<\/span> <\/span>string<\/span> <\/span>&<\/span>name<\/span>, <\/span>int<\/span> <\/span>year<\/span>);<\/span><\/span>\n  <\/span>Wine<\/span>(<\/span>const<\/span> <\/span>Wine<\/span> <\/span>&<\/span>wine<\/span>);<\/span><\/span>\n  <\/span>~Wine<\/span>();<\/span><\/span>\n<\/span>\n  <\/span>const<\/span> <\/span>string<\/span> <\/span>&<\/span>Name<\/span>() <\/span>const<\/span><\/span>\n  {<\/span><\/span>\n    <\/span>return<\/span> m_name;<\/span><\/span>\n  }<\/span><\/span>\n<\/span>\n  <\/span>int<\/span> <\/span>Year<\/span>() <\/span>const<\/span><\/span>\n  {<\/span><\/span>\n    <\/span>return<\/span> m_year;<\/span><\/span>\n  }<\/span><\/span>\n<\/span>\n  \/\/ Assignment operator<\/span><\/span>\n  <\/span>Wine<\/span> <\/span>&<\/span>operator=<\/span>(<\/span>const<\/span> <\/span>Wine<\/span> <\/span>&<\/span>wine<\/span>);<\/span><\/span>\n<\/span>\n  <\/span>void<\/span> <\/span>Print<\/span>() <\/span>const<\/span>;<\/span><\/span>\n<\/span>\nprivate:<\/span><\/span>\n  \/\/ Data members<\/span><\/span>\n  string m_name;<\/span><\/span>\n  <\/span>int<\/span>    m_year;<\/span><\/span>\n};<\/span><\/span>\n<\/span>\n#endif<\/span> \/* Wine_h *\/<\/span><\/span><\/code><\/pre><\/div>\n<\/div>\n\n\n\n
                              \n
                              <\/path><\/path><\/svg><\/span>
                              \/\/<\/span><\/span>\n\/\/  Wine.cpp<\/span><\/span>\n\/\/  Assignment 4: Linked Lists<\/span><\/span>\n\/\/<\/span><\/span>\n\/\/  Created by Bryan Higgs on 10\/31\/24.<\/span><\/span>\n\/\/<\/span><\/span>\n<\/span>\n#include<\/span> <\/span><iostream><\/span><\/span>\nusing<\/span> <\/span>namespace<\/span> <\/span>std<\/span>;<\/span><\/span>\n<\/span>\n#include<\/span> <\/span>"Wine.h"<\/span><\/span>\n<\/span>\nWine<\/span>::<\/span>Wine<\/span>(<\/span>const<\/span> string &name, <\/span>int<\/span> year)<\/span><\/span>\n    : <\/span>m_name<\/span>(name), <\/span>m_year<\/span>(year)<\/span><\/span>\n{}<\/span><\/span>\n<\/span>\nvoid<\/span> <\/span>Wine<\/span>::<\/span>Print<\/span>() <\/span>const<\/span><\/span>\n{<\/span><\/span>\n    cout << <\/span>"Wine: "<\/span> << m_name << <\/span>", "<\/span> << m_year << endl;<\/span><\/span>\n}<\/span><\/span>\n<\/span>\n\/\/ You implement the remaining member functions of the Wine class<\/span><\/span>\n<\/span><\/code><\/pre><\/div>\n<\/div>\n<\/div>\n\n\n\n
                              Here’s a test program for this…<\/p>\n\n\n\n
                              \n
                              \n
                              <\/path><\/path><\/svg><\/span>
                              \/\/<\/span><\/span>\n\/\/  TestWine.cpp<\/span><\/span>\n\/\/  Assignment 4: Linked Lists<\/span><\/span>\n\/\/<\/span><\/span>\n\/\/  Created by Bryan Higgs on 10\/31\/24.<\/span><\/span>\n\/\/<\/span><\/span>\n<\/span>\n#include<\/span> <\/span><iostream><\/span><\/span>\nusing<\/span> <\/span>namespace<\/span> <\/span>std<\/span>;<\/span><\/span>\n<\/span>\n#include<\/span> <\/span>"List.h"<\/span><\/span>\n#include<\/span> <\/span>"Wine.h"<\/span><\/span>\n<\/span>\nstatic<\/span> <\/span>void<\/span> <\/span>display<\/span>(<\/span>List<\/span> <\/span>&<\/span>list<\/span>)<\/span><\/span>\n{<\/span><\/span>\n  cout << <\/span>"Contents of list:"<\/span> << endl;<\/span><\/span>\n  ListIterator <\/span>iter<\/span>(list);<\/span><\/span>\n  <\/span>for<\/span> (ListItem *item = <\/span>iter<\/span>.<\/span>GetCurrent<\/span>();<\/span><\/span>\n       item != <\/span>0<\/span>;<\/span><\/span>\n       item = <\/span>iter<\/span>.<\/span>GetNext<\/span>()<\/span><\/span>\n      )<\/span><\/span>\n  {<\/span><\/span>\n    Wine *wine = (Wine *)(<\/span>item<\/span>-><\/span>GetData<\/span>());<\/span><\/span>\n    <\/span>wine<\/span>-><\/span>Print<\/span>();<\/span><\/span>\n  }<\/span><\/span>\n<\/span>\n  cout << <\/span>"-----Dump------"<\/span> << endl;<\/span><\/span>\n  <\/span>list<\/span>.<\/span>Dump<\/span>();<\/span><\/span>\n  cout << <\/span>"---End Dump----"<\/span> << endl;<\/span><\/span>\n}<\/span><\/span>\n<\/span>\nstatic<\/span> <\/span>void<\/span> <\/span>ListWines<\/span>()<\/span><\/span>\n{<\/span><\/span>\n  Wine <\/span>beaujolais<\/span>(<\/span>"Beaujolais"<\/span>, <\/span>1970<\/span>);<\/span><\/span>\n  Wine <\/span>amontillado<\/span>(<\/span>"Amontillado"<\/span>, <\/span>1964<\/span>);<\/span><\/span>\n  Wine <\/span>riesling<\/span>(<\/span>"Riesling"<\/span>, <\/span>1980<\/span>);<\/span><\/span>\n  Wine <\/span>gewurztraminer<\/span>(<\/span>"Gewurztraminer"<\/span>, <\/span>1993<\/span>);<\/span><\/span>\n  Wine <\/span>shiraz<\/span>(<\/span>"Shiraz"<\/span>, <\/span>2003<\/span>);<\/span><\/span>\n  Wine <\/span>cabernet<\/span>(<\/span>"Cabernet Sauvignon"<\/span>, <\/span>2001<\/span>);<\/span><\/span>\n<\/span>\n  \/\/ Each item in the following list is an instance<\/span><\/span>\n  \/\/ of ListItem, each pointing to its corresponding<\/span><\/span>\n  \/\/ Wine instance.<\/span><\/span>\n  ListItem items[] = { &beaujolais, &amontillado,<\/span><\/span>\n                       &riesling,   &gewurztraminer,<\/span><\/span>\n                       &shiraz,     &cabernet };<\/span><\/span>\n<\/span>\n  ListItem *item;<\/span> \/\/ Item pointer used in several places<\/span><\/span>\n  Wine *wine;<\/span>     \/\/ Wine pointer used in many places<\/span><\/span>\n<\/span>\n  List list;<\/span>      \/\/ The list of wines<\/span><\/span>\n<\/span>\n  \/\/ The following List iterator is positioned so that<\/span><\/span>\n  \/\/ the list it associates with is empty at the time<\/span><\/span>\n  \/\/ of the association.<\/span><\/span>\n  ListIterator <\/span>iter<\/span>(list);<\/span><\/span>\n<\/span>\n  \/\/ Start testing<\/span><\/span>\n<\/span>\n  cout << <\/span>"Empty list..."<\/span> << endl;<\/span><\/span>\n  <\/span>display<\/span>(list);<\/span><\/span>\n<\/span>\n  cout << <\/span>"Testing Append"<\/span> << endl;<\/span><\/span>\n  cout << <\/span>" Appending: "<\/span>;<\/span><\/span>\n  wine = (Wine *)(<\/span>items<\/span>[<\/span>0<\/span>].<\/span>GetData<\/span>());<\/span><\/span>\n  <\/span>wine<\/span>-><\/span>Print<\/span>();<\/span><\/span>\n  <\/span>list<\/span>.<\/span>Append<\/span>(<\/span>items<\/span>[<\/span>0<\/span>]);<\/span><\/span>\n  <\/span>display<\/span>(list);<\/span><\/span>\n<\/span>\n  cout << <\/span>"Testing a second Append"<\/span> << endl;<\/span><\/span>\n  cout << <\/span>" Appending: "<\/span>;<\/span><\/span>\n  wine = (Wine *)(<\/span>items<\/span>[<\/span>4<\/span>].<\/span>GetData<\/span>());<\/span><\/span>\n  <\/span>wine<\/span>-><\/span>Print<\/span>();<\/span><\/span>\n  <\/span>list<\/span>.<\/span>Append<\/span>(<\/span>items<\/span>[<\/span>4<\/span>]);<\/span><\/span>\n  <\/span>display<\/span>(list);<\/span><\/span>\n<\/span>\n  cout << <\/span>"Testing Add to front"<\/span> << endl;<\/span><\/span>\n  cout << <\/span>" Adding: "<\/span>;<\/span><\/span>\n  wine = (Wine *)(<\/span>items<\/span>[<\/span>1<\/span>].<\/span>GetData<\/span>());<\/span><\/span>\n  <\/span>wine<\/span>-><\/span>Print<\/span>();<\/span><\/span>\n  <\/span>items<\/span>[<\/span>1<\/span>].<\/span>Add<\/span>(list, <\/span>0<\/span>);<\/span><\/span>\n  <\/span>display<\/span>(list);<\/span><\/span>\n<\/span>\n  cout << <\/span>"Testing Add to end"<\/span> << endl;<\/span><\/span>\n  cout << <\/span>" Adding: "<\/span>;<\/span><\/span>\n  wine = (Wine *)(<\/span>items<\/span>[<\/span>2<\/span>].<\/span>GetData<\/span>());<\/span><\/span>\n  <\/span>wine<\/span>-><\/span>Print<\/span>();<\/span><\/span>\n  <\/span>items<\/span>[<\/span>2<\/span>].<\/span>Add<\/span>(list, <\/span>list<\/span>.<\/span>GetLast<\/span>());<\/span><\/span>\n  <\/span>display<\/span>(list);<\/span><\/span>\n<\/span>\n  cout << <\/span>"Testing Add to middle"<\/span> << endl;<\/span><\/span>\n  cout << <\/span>" Adding: "<\/span>;<\/span><\/span>\n  wine = (Wine *)(<\/span>items<\/span>[<\/span>3<\/span>].<\/span>GetData<\/span>());<\/span><\/span>\n  <\/span>wine<\/span>-><\/span>Print<\/span>();<\/span><\/span>\n  <\/span>items<\/span>[<\/span>3<\/span>].<\/span>Add<\/span>(list, &<\/span>items<\/span>[<\/span>1<\/span>]);<\/span><\/span>\n  <\/span>display<\/span>(list);<\/span><\/span>\n<\/span>\n  cout << <\/span>"------------Iterator testing------------"<\/span> << endl;<\/span><\/span>\n  cout << <\/span>"Testing iterator originally set on empty list..."<\/span> << endl;<\/span><\/span>\n  <\/span>for<\/span> (item = <\/span>iter<\/span>.<\/span>GetCurrent<\/span>();<\/span><\/span>\n       item != <\/span>0<\/span>;<\/span><\/span>\n       item = <\/span>iter<\/span>.<\/span>GetNext<\/span>()<\/span><\/span>\n      )<\/span><\/span>\n  {<\/span><\/span>\n    Wine *wine = (Wine *)(<\/span>item<\/span>-><\/span>GetData<\/span>());<\/span><\/span>\n    <\/span>wine<\/span>-><\/span>Print<\/span>();<\/span><\/span>\n  }<\/span><\/span>\n<\/span>\n  cout << <\/span>"Now reversing direction on iterator..."<\/span> << endl;<\/span><\/span>\n  <\/span>for<\/span> (item = <\/span>iter<\/span>.<\/span>GetCurrent<\/span>();<\/span><\/span>\n       item != <\/span>0<\/span>;<\/span><\/span>\n       item = <\/span>iter<\/span>.<\/span>GetPrevious<\/span>()<\/span><\/span>\n      )<\/span><\/span>\n  {<\/span><\/span>\n    Wine *wine = (Wine *)<\/span>item<\/span>-><\/span>GetData<\/span>();<\/span><\/span>\n    <\/span>wine<\/span>-><\/span>Print<\/span>();<\/span><\/span>\n  }<\/span><\/span>\n<\/span>\n  cout << <\/span>"Reversing direction again..."<\/span> << endl;<\/span><\/span>\n  <\/span>for<\/span> (item = <\/span>iter<\/span>.<\/span>GetCurrent<\/span>();<\/span><\/span>\n       item != <\/span>0<\/span>;<\/span><\/span>\n       item = <\/span>iter<\/span>.<\/span>GetNext<\/span>()<\/span><\/span>\n      )<\/span><\/span>\n  {<\/span><\/span>\n    Wine *wine = (Wine *)<\/span>item<\/span>-><\/span>GetData<\/span>();<\/span><\/span>\n    <\/span>wine<\/span>-><\/span>Print<\/span>();<\/span><\/span>\n  }<\/span><\/span>\n  cout << <\/span>"--------End Iterator testing------------"<\/span> << endl;<\/span><\/span>\n<\/span>\n  cout << <\/span>"Testing removal from middle"<\/span> << endl;<\/span><\/span>\n  cout << <\/span>" Removing: "<\/span>;<\/span><\/span>\n  wine = (Wine *)(<\/span>items<\/span>[<\/span>3<\/span>].<\/span>GetData<\/span>());<\/span><\/span>\n  <\/span>wine<\/span>-><\/span>Print<\/span>();<\/span><\/span>\n  <\/span>items<\/span>[<\/span>3<\/span>].<\/span>Remove<\/span>();<\/span><\/span>\n  <\/span>display<\/span>(list);<\/span><\/span>\n<\/span>\n  cout << <\/span>"Testing removal from end"<\/span> << endl;<\/span><\/span>\n  cout << <\/span>" Removing: "<\/span>;<\/span><\/span>\n  wine = (Wine *)(<\/span>items<\/span>[<\/span>2<\/span>].<\/span>GetData<\/span>());<\/span><\/span>\n  <\/span>wine<\/span>-><\/span>Print<\/span>();<\/span><\/span>\n  <\/span>items<\/span>[<\/span>2<\/span>].<\/span>Remove<\/span>();<\/span><\/span>\n  <\/span>display<\/span>(list);<\/span><\/span>\n<\/span>\n  cout << <\/span>"Testing removal from front"<\/span> << endl;<\/span><\/span>\n  cout << <\/span>" Removing: "<\/span>;<\/span><\/span>\n  wine = (Wine *)(<\/span>items<\/span>[<\/span>1<\/span>].<\/span>GetData<\/span>());<\/span><\/span>\n  <\/span>wine<\/span>-><\/span>Print<\/span>();<\/span><\/span>\n  <\/span>items<\/span>[<\/span>1<\/span>].<\/span>Remove<\/span>();<\/span><\/span>\n  <\/span>display<\/span>(list);<\/span><\/span>\n<\/span>\n  cout << <\/span>"Testing removal from end"<\/span> << endl;<\/span><\/span>\n  cout << <\/span>" Removing: "<\/span>;<\/span><\/span>\n  wine = (Wine *)(<\/span>items<\/span>[<\/span>4<\/span>].<\/span>GetData<\/span>());<\/span><\/span>\n  <\/span>wine<\/span>-><\/span>Print<\/span>();<\/span><\/span>\n  <\/span>items<\/span>[<\/span>4<\/span>].<\/span>Remove<\/span>();<\/span><\/span>\n  <\/span>display<\/span>(list);<\/span><\/span>\n<\/span>\n  cout << <\/span>"Testing removal of last item"<\/span> << endl;<\/span><\/span>\n  cout << <\/span>" Removing: "<\/span>;<\/span><\/span>\n  wine = (Wine *)(<\/span>items<\/span>[<\/span>0<\/span>].<\/span>GetData<\/span>());<\/span><\/span>\n  <\/span>wine<\/span>-><\/span>Print<\/span>();<\/span><\/span>\n  <\/span>items<\/span>[<\/span>0<\/span>].<\/span>Remove<\/span>();<\/span><\/span>\n  <\/span>display<\/span>(list);<\/span><\/span>\n<\/span>\n  \/\/ Finally, we test the actions of the List destructor<\/span><\/span>\n<\/span>\n  \/\/ First, go through the items to check that they are not in<\/span><\/span>\n  \/\/ a list...<\/span><\/span>\n  cout << <\/span>"Checking that removed items do not appear to be in a list"<\/span> << endl;<\/span><\/span>\n  <\/span>int<\/span> len = <\/span>sizeof<\/span>(items)\/<\/span>sizeof<\/span>(<\/span>items<\/span>[<\/span>0<\/span>]);<\/span><\/span>\n  <\/span>int<\/span> elem;<\/span><\/span>\n  <\/span>int<\/span> errors = <\/span>0<\/span>;<\/span><\/span>\n  <\/span>for<\/span> (elem = <\/span>0<\/span>; elem < len; elem++)<\/span><\/span>\n  {<\/span><\/span>\n    <\/span>if<\/span> (<\/span>items<\/span>[elem].<\/span>GetList<\/span>() != <\/span>0<\/span>)<\/span><\/span>\n    {<\/span><\/span>\n      errors++;<\/span><\/span>\n      cerr << <\/span>"Element "<\/span> << elem << <\/span>" still in a list"<\/span> << endl;<\/span><\/span>\n  }<\/span><\/span>\n    <\/span>if<\/span> (<\/span>items<\/span>[elem].<\/span>GetNext<\/span>() != <\/span>0<\/span>)<\/span><\/span>\n    {<\/span><\/span>\n      errors++;<\/span><\/span>\n      cerr << <\/span>"Element "<\/span> << elem << <\/span>" still has a next ptr"<\/span> << endl;<\/span><\/span>\n  }<\/span><\/span>\n    <\/span>if<\/span> (<\/span>items<\/span>[elem].<\/span>GetPrevious<\/span>() != <\/span>0<\/span>)<\/span><\/span>\n    {<\/span><\/span>\n      errors++;<\/span><\/span>\n      cerr << <\/span>"Element "<\/span> << elem << <\/span>" still has a previous ptr"<\/span> << endl;<\/span><\/span>\n    }<\/span><\/span>\n  }<\/span><\/span>\n  <\/span><\/span>\n  \/\/ Now, create the list and populate it from the items<\/span><\/span>\n  cout << <\/span>"Checking addition and removal to a dynamic list"<\/span> << endl;<\/span><\/span>\n  List *dynList = <\/span>new<\/span> <\/span>List<\/span>();<\/span><\/span>\n  <\/span>for<\/span> (elem = len-<\/span>1<\/span>; elem >= <\/span>0<\/span>; elem--)<\/span><\/span>\n  {<\/span><\/span>\n    <\/span>dynList<\/span>-><\/span>Append<\/span>(<\/span>items<\/span>[elem]);<\/span><\/span>\n  }<\/span><\/span>\n  <\/span><\/span>\n  \/\/ Display the list for validation<\/span><\/span>\n  <\/span>display<\/span>(*dynList);<\/span><\/span>\n<\/span>\n  \/\/ Now destroy the list and examine the state of each<\/span><\/span>\n  \/\/ of the items that were in the list<\/span><\/span>\n  cout << <\/span>"Destroying dynamic list"<\/span> << endl;<\/span><\/span>\n  <\/span>delete<\/span> dynList;<\/span><\/span>\n<\/span>\n  cout << <\/span>"Checking that removed items do not appear to be in a list"<\/span> << endl;<\/span><\/span>\n  <\/span>for<\/span> (elem = <\/span>0<\/span>; elem < len; elem++)<\/span><\/span>\n  {<\/span><\/span>\n    <\/span>if<\/span> (<\/span>items<\/span>[elem].<\/span>GetList<\/span>() != <\/span>0<\/span>)<\/span><\/span>\n    {<\/span><\/span>\n      errors++;<\/span><\/span>\n      cerr << <\/span>"Element "<\/span> << elem << <\/span>" still in a list"<\/span> << endl;<\/span><\/span>\n    }<\/span><\/span>\n    <\/span>if<\/span> (<\/span>items<\/span>[elem].<\/span>GetNext<\/span>() != <\/span>0<\/span>)<\/span><\/span>\n    {<\/span><\/span>\n      errors++;<\/span><\/span>\n      cerr << <\/span>"Element "<\/span> << elem << <\/span>" still has a next ptr"<\/span> << endl;<\/span><\/span>\n    }<\/span><\/span>\n    <\/span>if<\/span> (<\/span>items<\/span>[elem].<\/span>GetPrevious<\/span>() != <\/span>0<\/span>)<\/span><\/span>\n    {<\/span><\/span>\n      errors++;<\/span><\/span>\n      cerr << <\/span>"Element "<\/span> << elem << <\/span>" still has a previous ptr"<\/span> << endl;<\/span><\/span>\n    }<\/span><\/span>\n  }<\/span><\/span>\n  cout << errors << <\/span>" errors detected"<\/span> << endl;<\/span><\/span>\n}<\/span><\/span>\n<\/span>\nint<\/span> <\/span>main<\/span>(<\/span>int<\/span> <\/span>argc<\/span>, <\/span>const<\/span> <\/span>char<\/span> <\/span>*<\/span> <\/span>argv<\/span>[])<\/span><\/span>\n{<\/span><\/span>\n  <\/span>ListWines<\/span>();<\/span><\/span>\n<\/span>\n  <\/span>return<\/span> <\/span>0<\/span>;<\/span><\/span>\n}<\/span><\/span><\/code><\/pre><\/div>\n<\/div>\n\n\n\n
                              <\/div>\n<\/div>\n\n\n\n
                              <\/span>Persons<\/span><\/h5>\n\n\n\n
                              Now, let’s look at an alternative approach to using such List<\/code><\/strong>s, ListItem<\/code><\/strong>s, etc.<\/p>\n\n\n\n
                              You may notice that it’s a little clumsy to separate a ListItem<\/strong> from the data it represents. Here’s another, slightly different, approach that makes things a little easier:<\/p>\n\n\n\n
                              \n
                              \n
                              <\/path><\/path><\/svg><\/span>
                              \/\/<\/span><\/span>\n\/\/  Person.h<\/span><\/span>\n\/\/  Assignment 4: Linked Lists<\/span><\/span>\n\/\/<\/span><\/span>\n\/\/  Created by Bryan Higgs on 10\/31\/24.<\/span><\/span>\n\/\/<\/span><\/span>\n<\/span>\n#ifndef<\/span> Person_h<\/span><\/span>\n#define<\/span> Person_h<\/span><\/span>\n<\/span>\n#include<\/span> <\/span><string><\/span><\/span>\nusing<\/span> <\/span>namespace<\/span> <\/span>std<\/span>;<\/span><\/span>\n<\/span>\n#include<\/span> <\/span>"List.h"<\/span><\/span>\n<\/span>\nclass<\/span> <\/span>Person<\/span><\/span>\n{<\/span><\/span>\npublic:<\/span><\/span>\n  <\/span>Person<\/span>(<\/span>const<\/span> <\/span>string<\/span> <\/span>&<\/span>name<\/span>);<\/span><\/span>\n  <\/span>Person<\/span>(<\/span>const<\/span> <\/span>Person<\/span> <\/span>&<\/span>person<\/span>);<\/span><\/span>\n  <\/span>~Person<\/span>();<\/span><\/span>\n<\/span>\n  <\/span>const<\/span> <\/span>string<\/span> <\/span>&<\/span>Name<\/span>() <\/span>const<\/span><\/span>\n  {<\/span><\/span>\n      <\/span>return<\/span> m_name;<\/span><\/span>\n  }<\/span><\/span>\n<\/span>\n  <\/span>void<\/span> <\/span>Add<\/span>(<\/span>List<\/span> <\/span>&<\/span>list<\/span>, <\/span>Person<\/span> <\/span>*<\/span>prevPerson<\/span>);<\/span><\/span>\n  <\/span>void<\/span> <\/span>Remove<\/span>();<\/span><\/span>\n<\/span>\n  <\/span>void<\/span> <\/span>Print<\/span>() <\/span>const<\/span>;<\/span><\/span>\n<\/span>\n  \/\/ Assignment operator<\/span><\/span>\n  <\/span>Person<\/span> <\/span>&<\/span>operator=<\/span>(<\/span>const<\/span> <\/span>Person<\/span> <\/span>&<\/span>person<\/span>);<\/span><\/span>\n<\/span>\n  \/\/ Conversion function to ListItem &<\/span><\/span>\n  <\/span>operator<\/span> <\/span>ListItem<\/span> <\/span>&<\/span>()<\/span><\/span>\n  {<\/span><\/span>\n      <\/span>return<\/span> m_item;<\/span><\/span>\n  }<\/span><\/span>\n<\/span>\nprivate:<\/span><\/span>\n  ListItem  m_item;<\/span><\/span>\n  string    m_name;<\/span><\/span>\n};<\/span><\/span>\n<\/span>\n#endif<\/span> \/* Person_h *\/<\/span><\/span><\/code><\/pre><\/div>\n<\/div>\n\n\n\n
                              \n
                              <\/path><\/path><\/svg><\/span>
                              \/\/<\/span><\/span>\n\/\/  Person.cpp<\/span><\/span>\n\/\/  Assignment 4: Linked Lists<\/span><\/span>\n\/\/<\/span><\/span>\n\/\/  Created by Bryan Higgs on 10\/31\/24.<\/span><\/span>\n\/\/<\/span><\/span>\n<\/span>\n#include<\/span> <\/span><iostream><\/span><\/span>\nusing<\/span> <\/span>namespace<\/span> <\/span>std<\/span>;<\/span><\/span>\n<\/span>\n#include<\/span> <\/span>"Person.h"<\/span><\/span>\n<\/span>\nPerson<\/span>::<\/span>Person<\/span>(<\/span>const<\/span> string &name)<\/span><\/span>\n    : <\/span>m_item<\/span>(<\/span>this<\/span>), <\/span>m_name<\/span>(name)<\/span><\/span>\n{}<\/span><\/span>\n<\/span>\nvoid<\/span> <\/span>Person<\/span>::<\/span>Print<\/span>() <\/span>const<\/span><\/span>\n{<\/span><\/span>\n  cout << <\/span>"Person: "<\/span> << m_name << endl;<\/span><\/span>\n}<\/span><\/span>\n<\/span>\n\/\/ You implement the remaining member functions of the Person class<\/span><\/span>\n<\/span><\/code><\/pre><\/div>\n<\/div>\n<\/div>\n\n\n\n
                              … and here’s a test program for Persons:<\/p>\n\n\n\n
                              \n
                              \n
                              <\/path><\/path><\/svg><\/span>
                              \/\/<\/span><\/span>\n\/\/  TestPerson.cpp<\/span><\/span>\n\/\/  Assignment 4: Linked Lists<\/span><\/span>\n\/\/<\/span><\/span>\n\/\/  Created by Bryan Higgs on 10\/31\/24.<\/span><\/span>\n\/\/<\/span><\/span>\n<\/span>\n#include<\/span> <\/span><iostream><\/span><\/span>\nusing<\/span> <\/span>namespace<\/span> <\/span>std<\/span>;<\/span><\/span>\n<\/span>\n#include<\/span> <\/span>"List.h"<\/span><\/span>\n#include<\/span> <\/span>"Person.h"<\/span><\/span>\n<\/span>\nstatic<\/span> <\/span>void<\/span> <\/span>display<\/span>(<\/span>List<\/span> <\/span>&<\/span>list<\/span>)<\/span><\/span>\n{<\/span><\/span>\n  cout << <\/span>"Contents of list:"<\/span> << endl;<\/span><\/span>\n  ListIterator <\/span>iter<\/span>(list);<\/span><\/span>\n  <\/span>for<\/span> (ListItem *item = <\/span>iter<\/span>.<\/span>GetCurrent<\/span>();<\/span><\/span>\n       item != <\/span>0<\/span>;<\/span><\/span>\n       item = <\/span>iter<\/span>.<\/span>GetNext<\/span>()<\/span><\/span>\n      )<\/span><\/span>\n  {<\/span><\/span>\n    Person *person = (Person *)(<\/span>item<\/span>-><\/span>GetData<\/span>());<\/span><\/span>\n    <\/span>person<\/span>-><\/span>Print<\/span>();<\/span><\/span>\n  }<\/span><\/span>\n<\/span>\n  cout << <\/span>"-----Dump------"<\/span> << endl;<\/span><\/span>\n  <\/span>list<\/span>.<\/span>Dump<\/span>();<\/span><\/span>\n  cout << <\/span>"---End Dump----"<\/span> << endl;<\/span><\/span>\n}<\/span><\/span>\n<\/span>\nstatic<\/span> <\/span>void<\/span> <\/span>ListPersons<\/span>()<\/span><\/span>\n{<\/span><\/span>\n  Person <\/span>fred<\/span>(<\/span>"Fred"<\/span>);<\/span><\/span>\n  Person <\/span>mary<\/span>(<\/span>"Mary"<\/span>);<\/span><\/span>\n  Person <\/span>joe<\/span>(<\/span>"Joe"<\/span>);<\/span><\/span>\n  Person <\/span>clive<\/span>(<\/span>"Clive"<\/span>);<\/span><\/span>\n  Person <\/span>nigel<\/span>(<\/span>"Nigel"<\/span>);<\/span><\/span>\n  Person <\/span>nostradamus<\/span>(<\/span>"Nostradamus"<\/span>);<\/span><\/span>\n  Person <\/span>einstein<\/span>(<\/span>"Einstein"<\/span>);<\/span><\/span>\n<\/span>\n  Person *items[] = { &fred, &mary, &joe, &clive,<\/span><\/span>\n                      &nigel, &nostradamus, &einstein };<\/span><\/span>\n<\/span>\n  ListItem *item;<\/span><\/span>\n<\/span>\n  List list;<\/span>      \/\/ The list of people<\/span><\/span>\n<\/span>\n  \/\/ The following List iterator is positioned so that<\/span><\/span>\n  \/\/ the list it associates with is empty at the time<\/span><\/span>\n  \/\/ of the association.<\/span><\/span>\n  ListIterator <\/span>iter<\/span>(list);<\/span><\/span>\n  <\/span><\/span>\n  \/\/ Start testing<\/span><\/span>\n<\/span>\n  cout << <\/span>"Empty list..."<\/span> << endl;<\/span><\/span>\n  <\/span>display<\/span>(list);<\/span><\/span>\n<\/span>\n  cout << <\/span>"Testing Append"<\/span> << endl;<\/span><\/span>\n  cout << <\/span>" Appending: "<\/span>;<\/span><\/span>\n  <\/span>fred<\/span>.<\/span>Print<\/span>();<\/span><\/span>\n  <\/span>list<\/span>.<\/span>Append<\/span>(fred);<\/span><\/span>\n  <\/span>display<\/span>(list);<\/span><\/span>\n<\/span>\n  cout << <\/span>"Testing a second Append"<\/span> << endl;<\/span><\/span>\n  cout << <\/span>" Appending: "<\/span>;<\/span><\/span>\n  <\/span>nigel<\/span>.<\/span>Print<\/span>();<\/span><\/span>\n  <\/span>list<\/span>.<\/span>Append<\/span>(nigel);<\/span><\/span>\n  <\/span>display<\/span>(list);<\/span><\/span>\n<\/span>\n  cout << <\/span>"Testing Add to front"<\/span> << endl;<\/span><\/span>\n  cout << <\/span>" Adding: "<\/span>;<\/span><\/span>\n  <\/span>mary<\/span>.<\/span>Print<\/span>();<\/span><\/span>\n  <\/span>mary<\/span>.<\/span>Add<\/span>(list, <\/span>0<\/span>);<\/span><\/span>\n  <\/span>display<\/span>(list);<\/span><\/span>\n<\/span>\n  cout << <\/span>"Testing Add to end"<\/span> << endl;<\/span><\/span>\n  cout << <\/span>" Adding: "<\/span>;<\/span><\/span>\n  <\/span>joe<\/span>.<\/span>Print<\/span>();<\/span><\/span>\n  <\/span>joe<\/span>.<\/span>Add<\/span>(list, (Person *)(<\/span>list<\/span>.<\/span>GetLast<\/span>()));<\/span><\/span>\n  <\/span>display<\/span>(list);<\/span><\/span>\n<\/span>\n  cout << <\/span>"Testing Add to middle"<\/span> << endl;<\/span><\/span>\n  cout << <\/span>" Adding: "<\/span>;<\/span><\/span>\n  <\/span>clive<\/span>.<\/span>Print<\/span>();<\/span><\/span>\n  <\/span>clive<\/span>.<\/span>Add<\/span>(list, &mary);<\/span><\/span>\n  <\/span>display<\/span>(list);<\/span><\/span>\n<\/span>\n  cout << <\/span>"------------Iterator testing------------"<\/span> << endl;<\/span><\/span>\n  cout << <\/span>"Testing iterator originally set on empty list..."<\/span> << endl;<\/span><\/span>\n  <\/span>for<\/span> (item = <\/span>iter<\/span>.<\/span>GetCurrent<\/span>();<\/span><\/span>\n       item != <\/span>0<\/span>;<\/span><\/span>\n       item = <\/span>iter<\/span>.<\/span>GetNext<\/span>())<\/span><\/span>\n  {<\/span><\/span>\n    Person *person = (Person *)(<\/span>item<\/span>-><\/span>GetData<\/span>());<\/span><\/span>\n    <\/span>person<\/span>-><\/span>Print<\/span>();<\/span><\/span>\n  }<\/span><\/span>\n<\/span>\n  cout << <\/span>"Now reversing direction on iterator..."<\/span> << endl;<\/span><\/span>\n  <\/span>for<\/span> (item = <\/span>iter<\/span>.<\/span>GetCurrent<\/span>();<\/span><\/span>\n       item != <\/span>0<\/span>;<\/span><\/span>\n       item = <\/span>iter<\/span>.<\/span>GetPrevious<\/span>()<\/span><\/span>\n      )<\/span><\/span>\n  {<\/span><\/span>\n    Person *person = (Person *)(<\/span>item<\/span>-><\/span>GetData<\/span>());<\/span><\/span>\n    <\/span>person<\/span>-><\/span>Print<\/span>();<\/span><\/span>\n  }<\/span><\/span>\n<\/span>\n  cout << <\/span>"Reversing direction again..."<\/span> << endl;<\/span><\/span>\n  <\/span>for<\/span> (item = <\/span>iter<\/span>.<\/span>GetCurrent<\/span>();<\/span><\/span>\n       item != <\/span>0<\/span>;<\/span><\/span>\n       item = <\/span>iter<\/span>.<\/span>GetNext<\/span>()<\/span><\/span>\n      )<\/span><\/span>\n  {<\/span><\/span>\n    Person *person = (Person *)(<\/span>item<\/span>-><\/span>GetData<\/span>());<\/span><\/span>\n    <\/span>person<\/span>-><\/span>Print<\/span>();<\/span><\/span>\n  }<\/span><\/span>\n  cout << <\/span>"--------End Iterator testing------------"<\/span> << endl;<\/span><\/span>\n<\/span>\n  cout << <\/span>"Testing removal from middle"<\/span> << endl;<\/span><\/span>\n  cout << <\/span>" Removing: "<\/span>;<\/span><\/span>\n  <\/span>clive<\/span>.<\/span>Print<\/span>();<\/span><\/span>\n  <\/span>clive<\/span>.<\/span>Remove<\/span>();<\/span><\/span>\n  <\/span>display<\/span>(list);<\/span><\/span>\n<\/span>\n  cout << <\/span>"Testing removal from end"<\/span> << endl;<\/span><\/span>\n  cout << <\/span>" Removing: "<\/span>;<\/span><\/span>\n  <\/span>joe<\/span>.<\/span>Print<\/span>();<\/span><\/span>\n  <\/span>joe<\/span>.<\/span>Remove<\/span>();<\/span><\/span>\n  <\/span>display<\/span>(list);<\/span><\/span>\n<\/span>\n  cout << <\/span>"Testing removal from front"<\/span> << endl;<\/span><\/span>\n  cout << <\/span>" Removing: "<\/span>;<\/span><\/span>\n  <\/span>mary<\/span>.<\/span>Print<\/span>();<\/span><\/span>\n  <\/span>mary<\/span>.<\/span>Remove<\/span>();<\/span><\/span>\n  <\/span>display<\/span>(list);<\/span><\/span>\n<\/span>\n  cout << <\/span>"Testing removal from end"<\/span> << endl;<\/span><\/span>\n  cout << <\/span>" Removing: "<\/span>;<\/span><\/span>\n  <\/span>nigel<\/span>.<\/span>Print<\/span>();<\/span><\/span>\n  <\/span>nigel<\/span>.<\/span>Remove<\/span>();<\/span><\/span>\n  <\/span>display<\/span>(list);<\/span><\/span>\n<\/span>\n  cout << <\/span>"Testing removal of last item"<\/span> << endl;<\/span><\/span>\n  cout << <\/span>" Removing: "<\/span>;<\/span><\/span>\n  <\/span>fred<\/span>.<\/span>Print<\/span>();<\/span><\/span>\n  <\/span>fred<\/span>.<\/span>Remove<\/span>();<\/span><\/span>\n  <\/span>display<\/span>(list);<\/span><\/span>\n<\/span>\n  \/\/ Finally, we test the actions of the List destructor<\/span><\/span>\n<\/span>\n  \/\/ First, go through the items to check that they are not in<\/span><\/span>\n  \/\/ a list...<\/span><\/span>\n  cout << <\/span>"Checking that removed items do not appear to be in a list"<\/span> << endl;<\/span><\/span>\n  <\/span>int<\/span> len = <\/span>sizeof<\/span>(items)\/<\/span>sizeof<\/span>(<\/span>items<\/span>[<\/span>0<\/span>]);<\/span><\/span>\n  <\/span>int<\/span> elem;<\/span><\/span>\n  <\/span>int<\/span> errors = <\/span>0<\/span>;<\/span><\/span>\n  <\/span>for<\/span> (elem = <\/span>0<\/span>; elem < len; elem++)<\/span><\/span>\n  {<\/span><\/span>\n    ListItem &item = *(<\/span>items<\/span>[elem]);<\/span><\/span>\n    <\/span>if<\/span> (<\/span>item<\/span>.<\/span>GetList<\/span>() != <\/span>0<\/span>)<\/span><\/span>\n    {<\/span><\/span>\n      errors++;<\/span><\/span>\n      cerr << <\/span>"Element "<\/span> << elem << <\/span>" still in a list"<\/span> << endl;<\/span><\/span>\n    }<\/span><\/span>\n    <\/span>if<\/span> (<\/span>item<\/span>.<\/span>GetNext<\/span>() != <\/span>0<\/span>)<\/span><\/span>\n    {<\/span><\/span>\n      errors++;<\/span><\/span>\n      cerr << <\/span>"Element "<\/span> << elem << <\/span>" still has a next ptr"<\/span> << endl;<\/span><\/span>\n  }<\/span><\/span>\n    <\/span>if<\/span> (<\/span>item<\/span>.<\/span>GetPrevious<\/span>() != <\/span>0<\/span>)<\/span><\/span>\n    {<\/span><\/span>\n      errors++;<\/span><\/span>\n      cerr << <\/span>"Element "<\/span> << elem << <\/span>" still has a previous ptr"<\/span> << endl;<\/span><\/span>\n    }<\/span><\/span>\n  }<\/span><\/span>\n  <\/span><\/span>\n  \/\/ Now, create the list and populate it from the items<\/span><\/span>\n  cout << <\/span>"Checking addition and removal to a dynamic list"<\/span> << endl;<\/span><\/span>\n  List *dynList = <\/span>new<\/span> <\/span>List<\/span>();<\/span><\/span>\n  <\/span>for<\/span> (elem = len-<\/span>1<\/span>; elem >= <\/span>0<\/span>; elem--)<\/span><\/span>\n  {<\/span><\/span>\n    <\/span>dynList<\/span>-><\/span>Append<\/span>(*(<\/span>items<\/span>[elem]));<\/span><\/span>\n  }<\/span><\/span>\n  <\/span><\/span>\n  \/\/ Display the list for validation<\/span><\/span>\n  <\/span>display<\/span>(*dynList);<\/span><\/span>\n<\/span>\n  \/\/ Now destroy the list and examine the state of each<\/span><\/span>\n  \/\/ of the items that were in the list<\/span><\/span>\n  cout << <\/span>"Destroying dynamic list"<\/span> << endl;<\/span><\/span>\n  <\/span>delete<\/span> dynList;<\/span><\/span>\n<\/span>\n  cout << <\/span>"Checking that removed items do not appear to be in a list"<\/span> << endl;<\/span><\/span>\n  <\/span>for<\/span> (elem = <\/span>0<\/span>; elem < len; elem++)<\/span><\/span>\n  {<\/span><\/span>\n    ListItem &item = *(<\/span>items<\/span>[elem]);<\/span><\/span>\n    <\/span>if<\/span> (<\/span>item<\/span>.<\/span>GetList<\/span>() != <\/span>0<\/span>)<\/span><\/span>\n    {<\/span><\/span>\n      errors++;<\/span><\/span>\n      cerr << <\/span>"Element "<\/span> << elem << <\/span>" still in a list"<\/span> << endl;<\/span><\/span>\n    }<\/span><\/span>\n    <\/span>if<\/span> (<\/span>item<\/span>.<\/span>GetNext<\/span>() != <\/span>0<\/span>)<\/span><\/span>\n    {<\/span><\/span>\n      errors++;<\/span><\/span>\n      cerr << <\/span>"Element "<\/span> << elem << <\/span>" still has a next ptr"<\/span> << endl;<\/span><\/span>\n    }<\/span><\/span>\n    <\/span>if<\/span> (<\/span>item<\/span>.<\/span>GetPrevious<\/span>() != <\/span>0<\/span>)<\/span><\/span>\n    {<\/span><\/span>\n        errors++;<\/span><\/span>\n        cerr << <\/span>"Element "<\/span> << elem << <\/span>" still has a previous ptr"<\/span> << endl;<\/span><\/span>\n    }<\/span><\/span>\n  }<\/span><\/span>\n  cout << errors << <\/span>" errors detected"<\/span> << endl;<\/span><\/span>\n}<\/span><\/span>\n<\/span>\nint<\/span> <\/span>main<\/span>()<\/span><\/span>\n{<\/span><\/span>\n  <\/span>ListPersons<\/span>();<\/span><\/span>\n<\/span>\n  <\/span>return<\/span> <\/span>0<\/span>;<\/span><\/span>\n}<\/span><\/span><\/code><\/pre><\/div>\n<\/div>\n\n\n\n
                              <\/div>\n<\/div>\n\n\n\n
                              <\/span>Testing Your Implementation<\/em><\/span><\/h4>\n\n\n\n
                              You will need to do a reasonable amount of testing to ensure that your implementation of these classes actually works correctly. The above TestWine.cpp<\/strong><\/code> and TestPerson.cpp<\/strong><\/code> files do some reasonable amount of testing, but don’t feel restricted by them.  <\/p>\n\n\n\n
                              \n
                              If you do add your own tests, please create your own test main program — it’s much easier for me to separate out your efforts from mine!<\/p>\n<\/blockquote>\n\n\n\n
                              I strongly suggest that you freely instrument<\/em> your code so that you can turn on tracing and debugging information when convenient and\/or necessary. Adding a line like:<\/p>\n\n\n\n
                              cout << \"Adding item at \" << this << \" after item at \" << prevItem\n     << \" and before item at \" << nextItem << endl;<\/strong><\/code><\/pre>\n\n\n\n
                              at the appropriate place in your code can really help you figure out what’s going on.  However, I don’t need to see all these lines of code, so just use them for your debugging, and then clean them out so I can read your code.<\/p>\n\n\n\n
                              Note that the calls to the Dump()<\/code><\/strong> member functions may give you as much information as you need, but then again, if you need to do your own tracing, you need to do it.<\/p>\n\n\n\n
                              \n
                              It is important that you have tested the program sufficiently. Since you will be using and enhancing these classes in later assignments, it’s to your advantage to make sure that they work, now!<\/p>\n<\/blockquote>\n","protected":false},"excerpt":{"rendered":"
                              Linked Lists What is a Linked List? Linked lists are among the most useful data structures in Computer Science, and are therefore very heavily used in lots of different applications. For this assignment, we will concentrate on the doubly-linked list, which is perhaps the most useful of all linked lists. Here’s what a doubly-linked list looks […]<\/p>\n","protected":false},"author":1,"featured_media":0,"parent":29,"menu_order":0,"comment_status":"closed","ping_status":"closed","template":"","meta":{"footnotes":""},"class_list":["post-33","page","type-page","status-publish","hentry"],"blocksy_meta":[],"_links":{"self":[{"href":"https:\/\/bhiggs.x10hosting.com\/PracticalCPlusPlusProgramming\/index.php\/wp-json\/wp\/v2\/pages\/33","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/bhiggs.x10hosting.com\/PracticalCPlusPlusProgramming\/index.php\/wp-json\/wp\/v2\/pages"}],"about":[{"href":"https:\/\/bhiggs.x10hosting.com\/PracticalCPlusPlusProgramming\/index.php\/wp-json\/wp\/v2\/types\/page"}],"author":[{"embeddable":true,"href":"https:\/\/bhiggs.x10hosting.com\/PracticalCPlusPlusProgramming\/index.php\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/bhiggs.x10hosting.com\/PracticalCPlusPlusProgramming\/index.php\/wp-json\/wp\/v2\/comments?post=33"}],"version-history":[{"count":6,"href":"https:\/\/bhiggs.x10hosting.com\/PracticalCPlusPlusProgramming\/index.php\/wp-json\/wp\/v2\/pages\/33\/revisions"}],"predecessor-version":[{"id":1690,"href":"https:\/\/bhiggs.x10hosting.com\/PracticalCPlusPlusProgramming\/index.php\/wp-json\/wp\/v2\/pages\/33\/revisions\/1690"}],"up":[{"embeddable":true,"href":"https:\/\/bhiggs.x10hosting.com\/PracticalCPlusPlusProgramming\/index.php\/wp-json\/wp\/v2\/pages\/29"}],"wp:attachment":[{"href":"https:\/\/bhiggs.x10hosting.com\/PracticalCPlusPlusProgramming\/index.php\/wp-json\/wp\/v2\/media?parent=33"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}