**Lab 16: Linked lists** | COMP1633 @ MRU

Setup

There’s a new git issue that’s popping up - we’re running in to file limit quota issues! Before starting this lab, do the following:

cd into your labs repo
Run the following command:
```
$ git gc
```
gc stands for garbage collection - this will tell git to consolidate a bunch of small files into a larger object
Fetch your new changes as usual with git pull or git pull --no-rebase, depending on whatever elves are in your particular instance.

Finally, cd into the linkedlist folder to begin.

Linked List basics

The following Node structure is defined in linkedlist.h:

struct Node {
    int data;
    Node *next;
};

If you want to experiment with typedef and see if that makes things more clear, you could also define the following:
typedef Node * NodePtr;
and then use NodePtr in place of Node * everywhere.

Important: In order to test the functions required for this lab you will need to have one or more lists. Check out the examples from class (e.g. /library/students/comp1633/sample_code/charlotte/mar13 (yes, a long name - good practice for tab completion!). You should write a main program that creates a list (or lists) and then calls the specific function using this list.

Implement a function with the following prototype:
```
void write_list(Node *head);
```
The function receives the head pointer to a linked list and writes the given linked list to the output in the following format:
- the list is enclosed in square brackets
- each element is followed by a comma, except the last
For example, various outputs might look like:
```
[10,20,30]
[3]                 (a singleton list)
[]                  (the empty list)
[6,2,17,-11,0,2]
```
Check for memory leaks using valgrind and fix any issues that you find.

Write a function called even_count that takes a pointer to a list and returns the number of even values in the list. Don’t forget consider edge cases!
When you are happy with your implementation, test it from your main program with various lists. Then, cd up to the main labs directory and run the provided tests with:
```
$ make lab=linkedlist
```

Write a function called is_equal that takes pointers to two lists and returns a bool indicating whether the contents of the list are equal (same elements and same order).

Bonus Exercises

Implement a function specified by the following prototype:
```
void append(Node *&head, Node *&head2);
```
This function appends the second list onto the end of the first. The head2 pointer is set to NULL once the second list is appended onto the end of the first. Note that the function appends the original lists together, and does not make a copy of either one.
Why must the arguments be passed by reference?
Write a function called find. This function must take a list and a target value as input and return a pointer to the first node containing the value. If the value is not found, the function must return NULL.
Write a function called reverse. This function must take a list as input, and return a new list which is the reverse of the original (the original must not be affected). Your solution must perform only one traversal of the input list.
Hint: as you visit each node of the input list, insert a new duplicate node into the result list.