CPSC 221 201/202/203 2021W2
Lab Linked Lists
Skip To Content
Dashboard
  • Login
  • Dashboard
  • Calendar
  • Inbox
  • History
  • Help
Close
  • My Dashboard
  • CPSC 221 201/202/203 2021W2
  • Assignments
  • Lab Linked Lists
2021W2
  • Home
  • Zoom
  • PrairieLearn 2021W2
  • Modules
  • Assignments
  • Syllabus
  • Media Gallery
  • My Media

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

Good luck!

1644213600 02/06/2022 10:00pm
Please include a description
Additional Comments:
Rating max score to > pts
Please include a rating title

Rubric

Find Rubric
Please include a title
Find a Rubric
Title
You've already rated students with this rubric. Any major changes could affect their assessment results.
 
 
 
 
 
 
 
     
Can't change a rubric once you've started using it.  
Title
Criteria Ratings Pts
This criterion is linked to a Learning Outcome Description of criterion
threshold: 5 pts
Edit criterion description Delete criterion row
5 to >0 pts Full Marks blank
0 to >0 pts No Marks blank_2
This area will be used by the assessor to leave comments related to this criterion.
pts
  / 5 pts
--
Additional Comments
This criterion is linked to a Learning Outcome Description of criterion
threshold: 5 pts
Edit criterion description Delete criterion row
5 to >0 pts Full Marks blank
0 to >0 pts No Marks blank_2
This area will be used by the assessor to leave comments related to this criterion.
pts
  / 5 pts
--
Additional Comments
Total Points: 5 out of 5