# Week 3 - Linked Lists

## Team

>Members:
>
>- Tom Rutjes
>- David Cigri
>
> Date: 05 maart 2024

## Provided code

The `zip` file on Blackboard contains the C code for this week.
The project contains two *targets*: `singly_linked_lists` and `doubly_linked_lists`.
The first eight activities apply to the singly linked lists project, activities nine, ten, and eleven apply to the doubly linked lists project.

Make sure to test your code!
There are several `test_list_` functions provided in the `test_list.c` source and `test_list.h` header files.
These functions perform tests of your implementations by using the `assert` macro.
In case an assertion fails, your program will stop, and the failed assertion will be indicated in the console.

If you're on Windows, then run your code on WSL.
This allows you to use the *address sanitizer*, which will help you to locate bugs related to memory management.
To enable it, add the `-DUSE_ASAN=True` option to your CMake profile (Settings > Build, Execution, Deployment > CMake > CMake options).

## Activities

Make sure to have the activities signed off regularly to ensure progress is tracked.

### Activity 1: Chaining pointers

Use the following code in your `main` function.
Replace all pointer dereferences (e.g., `*pointer`) with the arrow operator.

node_t first = { .value = 1,
    .next = &(node_t) { .value = 2,
        .next = &(node_t) { .value = 3,
            .next = &(node_t) { .value = 4,
                .next = NULL}}}};

printf("first: %d\n", first.value);
printf("second: %d\n", (first.next)->value);
printf("third: %d\n", first.next->next->value);
printf("fourth: %d\n", first.next->next->next->value);

### Activity 2: Traversal

Implement the function `print_nodes`, so that the two calls from the `main` function give the expected results.

void print_nodes(const node_t * first)
{
    void print_nodes(const node_t *first) {
        for (const node_t* i = first; i != NULL; i = i->next) {
            printf("%d", i->value);
        }
    }
}

int main(void) {
    node_t first = { .value = 1,
	    .next = &(node_t) { .value = 2,
    		.next = &(node_t) { .value = 3,
	    		.next = &(node_t) { .value = 4,
		    		.next = NULL}}}};
	
	// expected output: 1, 2, 3, 4
	print_nodes(&first);
	
	// expected output: 3, 4
	print_nodes(first.next->next);
}

### Activity 3: Linked list deallocation

Implement the `list_destroy` function, such that the code does not contain a memory leak.
Use the address sanitizer to check if your code runs without memory problems.

void list_destroy(list_t *plist) {
    node_t* current;
    node_t* next;

    for (current = plist->head; current != NULL; current = next)
    {
        next = current->next;
        free(current);
    }

    plist->head = NULL;
}

### Activity 4: Appending to a singly linked list

Implement the `list_append` function.
Use the `test_list_append` function to test your implementation.

void list_append(list_t *plist, int value) {
    (void) plist;
    (void) value;
    // TODO: append value to the list by adding a new node after the last node (Activity 4)
    if(plist->head == NULL)
    {
        plist->head = node_create(value);
        return;
    }

    node_t* current = plist->head;
    while(current->next != NULL) current = current->next; //Sets current to last instance
    current->next = node_create(value);
}

### Activity 5: Time complexity of prepend and append

adding elements to a linked list has a time complexity of O(1). because the new element does not need to be chained with the last element of the linked list, so it does not need to copy anything.

### Activity 6: Access by index

Implement the `list_at` function.
Use the `test_list_at` function to test your implementation.

const node_t * list_at(const list_t *plist, size_t index) {
    size_t i = 0;
    if(plist->head == NULL) return NULL;

    node_t* current = plist->head;
    while(current->next != NULL && i<index) {current = current->next; i++;}
    
    return i < index ? NULL : current;
}

### Activity 7: A bad for-loop

With each call of list_at(), the whole list is traversed. This takes really long if the list is very long. A better solution is something like print_nodes does (the list is only traversed once).

### Activity 8: Removal in a singly-linked list

Implement the `list_remove_last` function.
Use the `test_list_remove_last` function to test your implementation.

bool list_remove_last(list_t *plist) {
    if(plist->head == NULL) return false;
    if(plist->head->next == NULL) return list_remove_first(plist);

    node_t* previous;
    node_t* current = plist->head;
    while(current->next != NULL)
    {
        previous = current;
        current = current->next;
    }
    previous->next = NULL;
    free(current);

    return current != NULL;
}

### Activity 9: Appending to a doubly linked list

Implement the `list_append` function for the doubly linked list.
Make sure to select the proper "run configuration" in CLion.
Use the `test_list_append` function to test your implementation.

void list_append(list_t *plist, int value) {
    if(plist->head == NULL)
    {
        plist->head = node_create(value);
        plist->tail = plist->head;
        return;
    }

    node_t* current = plist->head;
    while(current->next != NULL) current = current->next; //Sets current to last instance
    current->next = node_create(value);
    current->next->prev = current;
    plist->tail = current->next;
}

### Activity 10: Removal from a doubly linked list

Provide the correct implementation for the `list_remove` function.
Use the `test_list_remove` function to test your implementation.

// updates the list by removing the node referred to by node from the list
void list_remove(list_t *plist, node_t *pnode) {
    if(plist->head == plist->tail)
    {
        plist->head = NULL;
        plist->tail = NULL;
    }
    else if(plist->head == pnode)
    {
        plist->head = pnode->next;
        pnode->next->prev = NULL;
    }
    else if(plist->tail == pnode)
    {
        plist->tail = pnode->prev;
        pnode->prev->next = NULL;
    }
    else
    {
        pnode->prev->next = pnode->next;
        pnode->next->prev = pnode->prev;
    }
    free(pnode);
}

### Activity 11: Insertion in a doubly linked list

Implement the `list_insert` function for the doubly linked list.
Use the `test_list_insert` function to test your implementation.

// updates the list by inserting value before the node referred to by before
void list_insert_before(list_t *plist, node_t *pnode, int value) {
    node_t* new = node_create(value);
    new->prev = pnode->prev;
    new->next = pnode;
    if(new->prev == NULL) plist->head = new;
    else new->prev->next = new;
    pnode->prev = new;
}

### Activity 12: Time complexities

Fill in the table with the correct big-O expressions.

| Operation | Array | Linked List |
| --------------- | -------------------------- | ----------- |
| Access | O(1) | O(n) |
| Append | O(1) | O(1)/O(n) |
| Insert | O(n) | O(1) |
| Remove | O(n) | O(1) |

## Looking back

### What we've learnt

what linked list and double linked lists are.
how to use a double linked list and how it works within a big-O notation

### What were the surprises

NONE :dark_sunglasses:

### What problems we've encountered

inserting in a double linked list

### What was or still is unclear

NONE :flag-nl:

### How did the group perform?

we preformed well there were some bumps with these assignements but we crossed them :thumbsup: