Lab Linked Lists
- Due Feb 6, 2022 by 10p.m.
- Points 1
Assignment Description
In part 1 of this lab, you will do some pointer exercises. In part 2 of this lab, you implement some linked list methods, and check for any memory leaks using Valgrind. Optionally, you will use Valgrind to debug a deque method.
You can get the files for this lab by downloading lab_linkedlists.zip Download lab_linkedlists.zip.
Part 1
Get out a pen and some paper, and write the values of x, y, p1, and p2 after each statement in the following program. Instead of writing out the full hexadecimal value of memory addresses, you can use some shorthand to indicate “address of x” and “address of y.”
int main () {
int x = 5, y = 15;
int * p1, *p2;
// value of x y p1 p2
// 5 15 uninit uninit
p1 = &x; // (1)
p2 = &y; // (2)
*p1 = 6; // (3)
*p1 = *p2; // (4)
p2 = p1; // (5)
*p1 = *p2+10; // (6)
return 0;
}
After you’re done, you may change directories into the part 1
directory of lab_linkedlists
, compile the program using make
and run the program using ./pointers
to check your work.
Part 2
This second part of the lab deals with a recursive data structure called the Linked List. CD into the part2 subfolder of lab_linkedlists. You can compile the code using make lists
and do an initial test run using ./lists
Complete the following methods in linked_list.cpp
:
void delete_last_element( Node*& head );
void remove( Node*& head, int oldKey);
void insert_after( Node* head, int oldKey, int newKey );
Node* interleave( Node* list1, Node* list2 );
Drawing pictures of the possible configurations that must be handled in each method will help. When you complete the functions correctly, you should see the following output:
<A> list1: [3, 2, 1]
<B> list2: [6, 7, 8, 9, 10]
<C> delete_last_element(list1): [3, 2]
<D> delete_last_element(list1): [3]
<E> delete_last_element(list1): []
<F> list1: [5, 10, 15]
<F> remove(list1,10): [5, 15]
<F> remove(list1,15): [5]
<F> remove(list1,5): []
<G> list1: [11]
<G> insert_after(list1,11,12): [11, 12]
<H> insert_after(list1,13,14): [11, 12]
<I> insert_after(list1,11,12): [11, 12, 12]
<J> delete_last_element(list1): [11, 12]
<K> interleave(list1,list2): [11, 6, 12, 7, 8, 9, 10]
<L> interleave(list2,list2): [6, 6, 7, 7, 8, 8, 9, 9, 10, 10]
<M> interleave(list1,NULL): [11, 12]
<N> interleave(NULL,list2): [6, 7, 8, 9, 10]
<O> interleave(NULL,NULL): []
Note: You may find the diff
command and shell redirection useful for checking your output.
Background on Valgrind
Valgrind is a free utility for memory debugging, memory leak detection, and profiling. It runs only on Linux systems. In order to test your linked list program with Valgrind you should use the following command:
valgrind ./lists
To instruct valgrind to also check for memory leaks, run:
valgrind --leak-check=full ./lists
If your program has no memory leaks, you will see something similar to the following output:
HEAP SUMMARY:
in use at exit: 0 bytes in 0 blocks
total heap usage: 140 allocs, 140 frees, 75,164 bytes allocated
All heap blocks were freed -- no leaks are possible
If your program does have memory leaks, you will see a report about all found mistakes or inconsistencies. Each row of the report starts with the process ID (the process ID is a number assigned by the operating system to a running program). Each error has a description, a stack trace (showing where the error occurred), and other data about the error. It is important to eliminate errors in the order that they occur during execution, since a single error early could cause others later on.
Here is a list of some of the errors that Valgrind can detect and report.
-
Invalid read/write errors. This error will happen when your code reads or writes to a memory address which you did not allocate. Sometimes this error occurs when an array is indexed beyond its boundary, which is referred to as an “overrun” error. Unfortunately, Valgrind is unable to check for locally-allocated arrays (i.e., those that are on the stack.) Overrun checking is only performed for dynamic memory.
int * arr = new int[6]; arr[10] = -5;
- Use of an uninitialized value. This type of error will occur when your code uses a declared variable before any kind of explicit assignment is made to the variable.
int x; cout << x << endl;
-
Invalid free error. This occurs when your code attempts to delete allocated memory twice, or delete memory that was not allocated with
new
.int * x = new int; delete x; delete x;
- Mismatched
free() / delete / delete []
. Valgrind keeps track of the method your code uses when allocating memory. If it is deallocated with different method, you will be notified about the error.int * x = new int[6]; delete x;
- Memory leak detection - Valgrind can detect three sources of memory leakage:
- A still reachable block happens when you forget to delete an object, the pointer to the object still exists, and the memory for object is still allocated.
- A lost block is a little tricky. A pointer to some part of the block of memory still exists, but it is not clear whether it is pointing to the block or is independent of it.
- A definitely lost block occurs when the block is not deleted but no pointer to it is found.
More information about the Valgrind utility can be found at the following links:
- http://www.valgrind.org/docs/manual/quick-start.html Links to an external site.
- http://www.valgrind.org/docs/manual/faq.html#faq.reports Links to an external site.
- http://www.valgrind.org/docs/manual/manual.html Links to an external site.
After you’ve gotten the expected output for linked lists and used Valgrind is check that you don’t have any memory leaks, you can move on to part 3 of this lab.
Part 3 (optional)
Note: This portion of the lab is optional. You do not need to complete this part to complete the lab, but this would be great practice for improving your skills with pointers!
Change into the part3 directory of lab_linkedlists
. The deque.cpp
program implements a deque ADT with a doubly linked list. A doubly linked list is similar to a regular linked list in that nodes have a data field and a field for a pointer to the next node, but nodes in a doubly linked list also have a field for a pointer to the previous node.
This program implements the function removeDuplicates()
. Compile deque.cpp
by running make
and ./deque
. Observe that the program works correctly: it first enqueues strings into Deque so that it contains the following strings: ba,ba,ab,ab,ab,ab,ba,ba. It then runs removeDuplicates()
and pop/prints the remaining elements: ba,ab,ba. Notice that this function removes consecutive duplicates only.
However, the program causes memory leaks. Modify the program to plug any memory leaks. Use Valgrind.
valgrind --leak-check=full ./deque
to check that your modified code works correctly.
Marking Your Work
You will let us know you’ve worked on the lab by submitting your work to the autograder. We will run a very few simple test cases on your code, and if you pass any of them, you will get credit for the programming portion of the lab. (It’s a low bar.)
Submitting the lab is as simple as dragging your completed code into the PrairieLearn interface for the lab_linkedlists
assignment.
Please submit the following file:
linked_list.cpp