UML diagram
Go up to the Labs table of contents page
This laboratory introduces you to some advanced class development in C++, creating and using iterators, manipulating pointers, and linked data structures. It also addresses some issues involving testing and software development.
The linked list is a basic data structure from which one can implement stacks, queues, sets, and many other data structures. Lists may be singly- or doubly-linked. In this lab we will implement a doubly-linked list.
In this lab, you will have to make a choice as to which debugger to use; this will affect which tutorial you carry out. You can choose the gdb debugger (you would then complete Tutorial 2: GDB) or the lldb debugger (you would then complete Tutorial 2: LLDB). The source code provided for each tutorial is exactly the same, and the deliverable (i.e., what you turn in) is likewise the exact same.
The lldb debugger is preferred, as it was built with the clang++ compiler that we are using. HOWEVER, it does not work with the Ubuntu VirtualBox image. You can see here for the bug tracker about this issue. So if you are using the provided Ubuntu VirtualBox image, then you MUST choose gdb.
Ultimately, either one is fine to choose; they were designed to be very similar and have essentially identical functionality. If you have only one installed on your machine (which may be the case for those using Mac OS X), then choose that one. Both are installed on the lab computers. So it's not all that critical a decision. Just remember which one you choose, as you will end up using that debugger throughout this course. And if you ever have to switch between them, you can use our GDB vs LLDB page to see the (relatively few) commands that are different between the two.
So this is a low stress choice. Pick one and don't worry about making the "right" or "wrong" decision.
Linked lists are described in the online Readings.
You will be implementing a doubly linked list, and you will be using "dummy" nodes as well. You will want two dummy nodes -- one for the head and one for the tail. A benefit of doing your implementation using dummy nodes is that there are fewer special cases to check for -- for example you never have to update the head pointer on an insertBefore() or a remove() -- the head pointer always points to the dummy header node. A dummy tail pointer would help out in the same respect. The downside is that you use two extra "empty" nodes.
For this lab you will need to implement three classes:
For simplicity we will just create a list that holds integers (your code could easily later be templated (i.e. made generic) to allow it to contain objects of other types). You must use the method names listed below in your code.
Below are the class definitions for each, which should be kept in header files with the respective file names.
We have provided a test harness for testing your whole implementation: ListTest.cpp (src) The classes you implement must work with this test harness.
Below is a UML diagram showing how these classes interact with each other.
UML diagram
This diagram shows a list containing two elements, the integers 3 and 7. Note that there are more methods in the List and ListItr classes than what is shown above. The head and tail pointers in the List class point to dummy nodes -- they are put there to make inserting elements into the list easier. It doesn't matter what the value of the dummy notes is set to, as it won't be used. Each ListNode points to the nodes before and after it (although the dummy nodes each have one pointer pointing to NULL).
Thus, our doubly linked list will have only one List object and many ListNode objects (2 more than the number of elements in the list). A ListItr is a separate object, which points to one element in the list (possibly a dummy node). As you call the various methods in ListItr to move the iterator forward and backward, the node that it points to will change.
A ListNode contains an integer value, as well as next and previous pointers to other ListNodes. View the ListNode.h (src) code for details.
This class represents the list data structure containing ListNodes. It has a pointer to the first (head) and last (tail) ListNodes of the list, as well as a count of the number of ListNodes in the List. View the List.h (src) code for details.
List() is the default constructor. It should initialize all private data members. Pointers are often initialized to NULL.~List() is the destructor. It should make the list empty and reclaim the memory allocated in the constructor for head and tailList& operator=(const List& source) is the copy assignment operator. It is called when code such as the following is encountered: lhs = rhs. The copy assignment operator that you implement will copy the contents of every ListNode in source into this (the reference to the calling List object itself)List(const List& source) is the copy constructor. This will create a new list of ListNodes whose contents are the same values as the ListNodes in source.bool isEmpty() This member function returns true if the list is empty, else falsevoid makeEmpty() removes/reclaims all items from a list, except the dummy head and tail nodes.ListItr first() returns an iterator that points to the ListNode in the first position. This is the element after the head ListNode (even on an empty list!)ListItr last() returns an iterator that points to the ListNode in the last position. This is the element before the tail node (even on an empty list!)void insertAfter(int x, ListItr position) inserts x after the current iterator position position.void insertBefore(int x, ListItr position) inserts x before the current iterator position position.void insertAtTail(int x) inserts x at tail of list.void remove(int x) removes the first occurrence of x.ListItr find(int x) returns an iterator that points to the first occurrence of x. When the parameter is not in the list, return a ListItr object, where the current pointer points to the dummy tail node. This makes sense because you can test the return from find() to see if isPastEnd() is true.int size() returns the number of elements in the list.In addition, you must implement this non-List member function: void printList(List& theList, bool forward) is a non-member function that prints a list either forwards (by default -- from head to tail) when forward is true, or backwards (from tail to head) when forward is false. You must use your ListItr class to implement this function.
The code for the copy constructor and the operator=() method in the List class are shown below. Although we are providing you with this code, you must understand how it works by the end of the lab, as you will have to implement these types of methods on future labs and exams.
List::List(const List& source) { // Copy Constructor
head=new ListNode;
tail=new ListNode;
head->next=tail;
tail->previous=head;
count=0;
ListItr iter(source.head->next);
while (!iter.isPastEnd()) { // deep copy of the list
insertAtTail(iter.retrieve());
iter.moveForward();
}
}
List& List::operator=(const List& source) { //Equals operator
if (this == &source)
return *this;
else {
makeEmpty();
ListItr iter(source.head->next);
while (!iter.isPastEnd()) {
insertAtTail(iter.retrieve());
iter.moveForward();
}
}
return *this;
}Note that these two methods are correctly implemented. However, they depend on the other methods working properly. If you are seeing crashes in these methods, it is likely because some of the other supporting methods are not working properly. One common issue is to ensure that makeEmpty() has head->next pointing to tail, and tail->previous pointing to head. If they are causing a crash in your program, then it is likely being caused by one of the methods that they invoke.
Your ListItr should maintain a pointer to a current position in a List. Your iterator class should look like the class definition in the source code. See the ListItr.h (src) code for details.
Your ListItr class should implement at least the following public methods:
bool isPastEnd(): Returns true if the iterator is currently pointing past the end position in the list (i.e., it's pointing to the dummy tail)bool isPastBeginning(): Returns true if the iterator is currently pointing past(before) the first position in list (i.e., it's pointing to the dummy head)void moveForward(): Advances the current pointer to the next position in the list (unless already past the end of the list)void moveBackward(): Move current back to the previous position in the list (unless already past the beginning of the list)int retrieve(): Returns the value of the item in the current position of the listThere are a few things that always cause students some headache. We've tried to explain some of them here, in an effort to lessen the frustration it causes.
When compiling your code, you must remember to compile all of your .cpp files in one line:
clang++ List.cpp ListItr.cpp ListNode.cpp ListTest.cppThere are ways to compile these programs in pieces, but we will see this later in the semester.
Some students have had problems with the copy constructor and operator=() methods defined above -- they would cause a crash (segmentation fault). The methods above work fine in our solution, but require that all the called functionality work properly as well. If it is causing a crash in your code, run it through the debugger to see where it crashes -- it's probably a problem with one of your other methods.
To start, create the .cpp file (List.cpp, ListNode.cpp, ListItr.cpp) that just have empty method bodies (with a dummy return value for non-void methods), and get that to compile. Then start implementing one method at a time, testing as you go.
These are the same steps from the lab procedure section, above.
These are the same steps from the lab procedure section, above.