In this lab, you will implement certain methods on linked lists. Linked lists are a fundamental data structure in programming, irrespective of the language. Not only are they very popular in their own right, they often serve as the basis for other data structures. After completing this lab, you should:
You may work with a partner for this lab. If you choose a partner, both members must contribute to the same work. That is, you cannot simply divide the lab in half, as everyone is responsible for all the content. Instead, you should use a pair programming style. In pair programming, one person acts as a driver, who takes control of the keyboard. The other person acts as a navigator, who reviews what the driver writes and offers advice. Oftentimes, the driver is occupied with details of the problem (e.g., variables, control flow, etc.), whereas the navigator is concerned with bigger-picture problems (e.g., functions, design, interactions). This works well for problems which are simply too large to fit into one person's head. If you're unfamiliar with the concept of pair programming, you may wish to watch this video on the topic.
With pair programming, oftentimes it works best if both participants are of approximately the same skill level. Generally, if the disparity in skill is large, the end result is frustrating for both parties - it really only works when both parties operate at approximately the same speed. With this in mind, you should select someone of approximately the same skill level.
Chapter 3 of the Dale book is relevant, specifically with the discussion of the Unsorted List ADT. In the fifth edition, this corresponds to pages 132-138 and 158-186.
Two list implementations are provided, which we recommend looking at.
You may want to open the separate files in a browser, especially for
the linked list implementation. These are also provided on the main
course page in zip files. You may take code from these.
-bash-4.2$ cd -bash-4.2$ pwd /cs/student/yourusername -bash-4.2$ cd cs24 -bash-4.2$ pwd /cs/student/yourusername/cs24 -bash-4.2$ mkdir lab4 -bash-4.2$ cd lab4 -bash-4.2$ pwd /cs/student/yourusername/cs24/lab4
Now copy over the files for this week.
They are kept in the directory: /cs/student/kyledewey/cs24/labs/4
-bash-4.2$ cp /cs/student/kyledewey/cs24/labs/4/* .
Note that there is a '.' at the end of that line. cp means copy.
/cs/student/kyledewey/cs24/labs/4/* means all of the files contained
in the directory /cs/student/kyledewey/cs24/labs/4. The '.' means to
copy from that location to the current location.
Now check to make sure the copy worked correctly:
-bash-4.2$ ls
You should see a set of files listed that will be used for this warm-up.
The file reading_questions.txt contains a series of questions
you must answer. More instructions are in that file.
We have provided the following files which are relevant to this portion:
LinkedList.h: Header file containing a partial
linked-list implementation
main.cpp: Uses LinkedList.h, and
can be used for testing it.
testaddhead.txt: Simple test file which, when run
with the provided main.cpp, should result in
the following output:
[] [7, 5, 4] [1, 3] [2] [7, 1, 8, 5]
You will be spending the bulk of your time creating a new file
named LinkedList.cpp, which implements the interface
defined in LinkedList.h. The main
function defined in main.cpp can be used along with
a file containing lists (such as the one in testaddhead.txt)
for testing your code. We encourage you to add your own tests;
with testaddhead.txt, very little of the actual code
you will write is tested.
Node
Notice that the Node constructors defined in
LinkedList.h have no implementation defined.
Go ahead and define these in a new file, LinkedList.cpp.
Be sure to add in any other necessary components to the file,
such as #includes, etc. In the
constructors, be sure to initialize any instance variables.
If an instance variable's intended variable isn't provided, then
use 0 for instance variables of type int
and NULL for any instance variables of a pointer type.
LinkedList
Implement the constructor for LinkedList in LinkedList.cpp.
There is only one instance variable which needs to be initialized here.
Think carefully about what this should be initialized to.
printList
The printList method simply prints the contents of
the list to the terminal. For example, if the list is empty, it
should print [], and if the list contains the
elements 1, 2, 3, then it should print [1, 2, 3].
The trick here is to traverse the list with a Node*.
The provided example code should prove invaluable here.
addHead
The addHead mutator method should add an element to the front
of a list. For example, if we have the list:
[1, 2, 3]
...and we call list.addHead(0), then the resulting list
should be:
[0, 1, 2, 3]
The implementation will require
you to change the head field in the object, so that the
head node in the list holds onto the item added along with the
original head of the list.
At this point, a variety of methods still need to be implemented,
which are preventing you from being able to compile and test your
code properly. Go ahead and write stubs for these remaining
components, which are the most basic bits of code necessary to get
through compilation. For methods that return void,
these should simply have an empty body. For methods that return
int, these should return 0, and for bool they
should return false.
With stubs in hand, you should be able to compile and run your code, like so:
-bash-4.2$ clang++ LinkedList.cpp main.cpp -bash-4.2$ ./a.out testaddhead.txt
Assuming everything works with this, now would be a good point to make a backup of what you have, as with:
-bash-4.2$ cp LinkedList.cpp LinkedList.cpp.backup
If you're interested, there are far better, more streamlined ways of doing this sort of backup via revision control systems. However, these can come with a high learning curve, and they are beyond this class' materal.
Each one of these parts is mostly independent of each other.
We recommend that you test each of these thoroughly in main.cpp, perhaps even with specialized versions of main.cpp.
The bulk of the work is in implementing these methods, and so
the bulk of the grade is here, too.
length
The length accessor method should return the number
of nodes which are contained in the list.
For testing purposes, you should be most interested in empty lists and
non-empty lists.
deleteFourth
The deleteFourth method should delete the fourth
element in a linked list, if applicable. If the list contains
fewer then four elements, then it should do nothing and
simply return false. If the list contains four
or more elements, then it should delete the fourth element and
return true.
We're using a technique called the generalization technique. What we really want to learn is how to delete any node from a linked list. We're starting with implementing a specific node before generalizing to implementing any node. For this lab, you won't be implementing this more generic routine, but you'll be setup to implement it in the future.
Before you start coding, draw a picture of a linked list containing at least four nodes. Draw the linked list before you remove the fourth node and then modify the pointeres to show the linked list after you remove the fourth node. That will tell you what statements you need to write to remove the node. Then, remember that you need to delete the node's memory. You cannot delete the node's memory until after the last instruction accessing the node.
As for tests, think about the border conditions for this method. A list of length 4 is one such test, but there are several other possible tests which could be considered border conditions.
addAmountToEach
The addAmountToEach method should add a given integer
to each element of the list. For example, if we have a list:
[1, 2, 3, 1, 2, 3]
...then list.addAmountToEach(4)
should result in a list:
[5, 6, 7, 5, 6, 7]
Note that this method doesn't change the structure of the list in any way, only the contents.
LinkedList Destructor
The destructor for linked lists must delete each node in the list.
Keep in mind that once you delete a node it is gone.
You cannot, for example, ask a deleted node what the next node is, since the deleted
node no longer exists. If you do this, undefined behavior results. It may
even appear to work, but there is absolutely no guarantee of this.
deleteAllLessThan
This is arguably the most complex method in this assignment.
This method should delete all nodes which contain a value
less than a given int parameter. For example, given the list:
[7, 1, 2, 3, 4, 5, 6]
A call to list.deleteAllLessThan(3) should result in:
[7, 3, 4, 5, 6]
This method can substantially alter the list, depending on the list's contents. For example, consider the following list:
[1, 2, 3]
A call to list.deleteAllLessThan(3) would result in:
[3]
...which moves the head of the list.
Some psuedocode has been provided below which implements
deleteAllLessThan(int). You do not have to adhere strictly
to this if you have another method in mind for solving this problem.
def deleteAllLessThan(cutoff):
previous = Empty
current = head
while current isn't Empty:
tempNext = the node after current
if the data in the current node is less than the cutoff:
delete the current node
if the current node is the head:
current = head = tempNext
else:
set the next node of the previous node to be tempNext
current = tempNext
else:
previous = current
current = tempNext
First, fill out the required fields in the provided README.txt file.
Once you have filled this in, you may submit everything with the following command:
-bash-4.2$ turnin lab4@cs24 README.txt LinkedList.h LinkedList.cpp main.cpp reading_questions.txt
Most content was graciously provided by Professor Diana Franklin, with formatting-related adaptations and some additional problems.