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:

==873== HEAP SUMMARY:
==873== in use at exit: 0 bytes in 0 blocks
==873== total heap usage: 137 allocs, 137 frees, 75,692 bytes allocated
==873==
==873== All heap blocks were freed -- no leaks are possible
==873==
==873== For lists of detected and suppressed errors, rerun with: -s
==873== ERROR SUMMARY: 0 errors from 0 contexts (suppressed: 0 from 0)

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.

Submission

// linked_list.cc -- functions for linked_list lab (cs221)

#include "linked_list.h"

/**
 * Inserts a new Node (with key=newKey) at the head of the linked_list.
 * PRE: head is the first node in a linked_list (if NULL, linked_list is empty)
 * PRE: newKey is the value for the key in the new Node
 * POST: the new Node is now the head of the linked_list
 */
void insert(Node *&head, int newKey) {
  Node *curr = new Node(newKey, head);
  head = curr;
}

/**
 * Print the keys of a linked_list in order, from head to tail
 * PRE: head is the first node in a linked_list (if NULL, linked_list is empty)
 */
void print(Node *head) {
  std::cout << "[";
  for (Node *curr = head; curr != NULL; curr = curr->next) {
    std::cout << curr->key;
    if (curr->next != NULL)
      std::cout << ", ";
  }
  std::cout << "]" << std::endl;
}

/**
 * Returns the size (number of Nodes) of the linked_list
 * PRE: head is the first node in a linked_list (if NULL, linked_list is empty)
 */
int size(Node *head) {
  if (!head)
    return 0;
  return 1 + size(head->next);
}

/**
 * Copies the keys in a linked list to a vector.
 * PRE: head is the first node in a linked_list (if NULL, linked_list is empty)
 * POST: a new vector<int> containing the keys in the correct order has been
 * returned.
 */
std::vector<int> to_vector(Node *head) {
  std::vector<int> result;
  for (Node *curr = head; curr != NULL; curr = curr->next) {
    result.push_back(curr->key);
  }
  return result;
}

/**
 * Delete the last Node in the linked_list
 * PRE: head is the first Node in a linked_list (if NULL, linked_list is empty)
 * POST: the last Node of the linked_list has been removed
 * POST: if the linked_list is now empty, head has been changed
 * POST: else head remains the first Node in the linked_list
 */
void delete_last_element(Node *&head) {
  if (head == nullptr)
    return;

  if (head->next == nullptr) {
    delete head;
    head = nullptr;

    return;
  }

  if (head->next->next != nullptr) {
    delete_last_element(head->next);

    return;
  }

  delete head->next;
  head->next = nullptr;
}

/**
 * Removes an existing Node (with key=oldKey) from the linked_list.
 * PRE: head is the first node in a linked_list (if NULL, linked_list is empty)
 * PRE: oldKey is the value of the key in the Node to be removed
 * PRE: if no Node with key=oldKey exists, the linked_list has not changed
 * POST: if a Node with key=oldKey was found, then it was deleted
 * POST: other Nodes with key=oldKey might still be in the linked_list
 * POST: head is the new first Node of the linked_list, if updated
 */
void remove(Node *&head, int oldKey) {
  // ******** WRITE YOUR CODE HERE ********
  if (head == nullptr)
    return;

  if (head->key == oldKey) {
    Node *temp = head;
    head = head->next;
    
    delete temp;

    return;
  }

  if (head->next != nullptr && head->next->key != oldKey) {
    remove(head->next, oldKey);

    return;
  }

  Node *temp = head->next;

  if (temp == nullptr)
    return;

  head->next = temp->next;
  delete temp;
}

/**
 * Insert a new Node (with key=newKey) after an existing Node (with key=oldKey)
 * If there is no existing Node with key=oldKey, then no action.
 * PRE: head is the first Node in a linked_list (if NULL, linked_list is empty)
 * PRE: oldKey is the value to look for (in the key of an existing Node)
 * PRE: newKey is the value of the key in the new Node (that might be inserted)
 * POST: if no Node with key=oldKey was found, then the linked_list has not
 * changed POST: else a new Node (with key=newKey) is right after the Node with
 * key = oldKey.
 */
void insert_after(Node *head, int oldKey, int newKey) {
  // ******** WRITE YOUR CODE HERE ********
  if (head == nullptr)
    return;

  if (head->key == oldKey) {
    Node *newNode = new Node(newKey, head->next);
    head->next = newNode;
  }

  if (head->next == nullptr)
    return;

  insert_after(head->next, oldKey, newKey);
}

/**
 * Create a new linked_list by merging two existing linked_lists.
 * PRE: list1 is the first Node in a linked_list (if NULL, then it is empty)
 * PRE: list2 is the first Node in another linked_list (if NULL, then it is
 * empty) POST: A new linked_list is returned that contains new Nodes with the
 * keys from the Nodes in list1 and list2, starting with the key of the first
 * Node of list1, then the key of the first Node of list2, etc. When one list is
 * exhausted, the remaining keys come from the other list. For example: [1, 2]
 * and [3, 4, 5] would return [1, 3, 2, 4, 5]
 */
Node *interleave(Node *list1, Node *list2) {
  // ******** WRITE YOUR CODE HERE ********

  if (list1 == nullptr && list2 == nullptr)
    return nullptr;

  if (list1 == nullptr)
    return new Node(list2->key, interleave(nullptr, list2->next));

  if (list2 == nullptr)
    return new Node(list1->key, interleave(list1->next, nullptr));

  Node *left = list1->next;
  Node *right = list2->next;

  Node *secondElement = new Node(list2->key, interleave(left, right));
  Node *firstElement = new Node(list1->key, secondElement);

  return firstElement;
}