# Week 3 - Linked Lists

## Team

Team name:
Date:

Members

| Role | Name |
|-------------------------------------------------------------------------------------------------------------------------------------------------------------------------------|------|
| **Facilitator** keeps track of time, assigns tasks and makes sure all the group members are heard and that decisions are agreed upon. | |
| **Spokesperson** communicates group’s questions and problems to the teacher and talks to other teams; presents the group’s findings. | |
| **Reflector** observes and assesses the interactions and performance among team members. Provides positive feedback and intervenes with suggestions to improve groups’ processes. | |
| **Recorder** guides consensus building in the group by recording answers to questions. Collects important information and data. | |

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

Set up a project in CLion to write the small programs needed in some of the activities.

### Activity 1: Pointers to pointers

Record your answer here

| Variable | Address | Value |
| ----------- | --------------------- | ----------- |
| value | 00000092667ffa8c | |42
| ptr | 00000092667ffa80 | |42
| pptr | 00000092667ffa78 | |42
| ppptr | 00000092667ffa70 | |42

Variable ppptr represents that the variable is pointed to pptr, which is pointed to ptr, which is pointed to value, which is equal with 42.

### Activity 2: Chaining pointers

#include <stdio.h>

typedef struct node_t {
    int value;
    struct node_t * next;
} node;

int main(void) {
    node fourth = {.value = 42, .next = NULL};
    node third = {.value = 7, .next = &fourth};
    node second = {.value = 3, .next = &third};
    node first = {.value = 2, .next = &second};

    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 3: Traversal

    node fourth = {.value = 42, .next = NULL};
    node third = {.value = 7, .next = &fourth};
    node second = {.value = 3, .next = &third};
    node first = {.value = 2, .next = &second};


for ( node * i = &first; i !=NULL; i= i->next ){
        printf("%d\n", i->value);
    }

For an array, we would do something like:

int values[10];
for (int i = 0; i < 10; i++) printf("%d\n", value[i]);

Starting point: first index: `i = 0`
Linked list: starting point = memory address of the first node.

Record your answer here

### Activity 4: Linked list deallocation

void list_free(list ** plist){
    node *i = (*plist)->head;
    node * next;
    while(i!=NULL){
        next=i->next;
        node_free(&i);
        i = next;
    }
    free(*plist);
    *plist= NULL;
}

### Activity 5: Prepending

void list_prepend(list * plist, int value){
    if (plist->head == NULL) {
        node_init(&plist->head, value);
        plist->tail = plist->head;
    }
    else{
        node * temp;
        node_init(&temp, value);
        temp->next=plist->head;
        plist ->head->prev = temp;
        plist->head=temp;
    }
}

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

Each insert operation should take O(1), so the total will be O(n) (where n is the count of numbers we want to insert), because our append function will call also the node init function after every step.

### Activity 7: Access by index

Record your answer here

const node *list_at(const list *plist, int index){
    node* current = plist;

    int count = 0;
    while (current != NULL) {
        if (count == index)
            return (current->value);
        count++;
        current = current->next;
    }
}

### Activity 8: Time complexity of accessing by index

The time complexity of the list_at function is O(n), because it depends on the number of elements of the list.

### Activity 9: A bad for-loop

I think the complexity of the for loop in which it also calls the list_at function would be O(n^2), therefore it will be a bad implementation.

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

Record your answer here

void list_remove_last(list * plist) {
    if(plist->head != NULL) {
        if(plist->head->next == NULL) {
            plist->head = NULL;
        } else {
            node* temp = plist->head;
            while(temp->next->next != NULL)
                temp = temp->next;
            node* lastNode = temp->next;
            temp->next = NULL;
            free(lastNode);
        }
    }
}

### Activity 11: Code update - I

Record your answer here

 typedef struct node_t {
 int value;
 struct node_t *next;
 struct node_t *prev;
 } node;
// the node_t stays the same as it has prev, next and the value

void node_init(node ** ptr, int value) {
 node *p = (node*) malloc(sizeof(node));
 if (p != NULL) {
 p->next = NULL;
 p->value = value;
 p->prev = NULL;
 }   
 }


### Activity 12: Code update - II

void list_prepend(list * plist, int value){
if (plist->head == NULL) {
node_init(&plist->head, value);
plist->tail = plist->head;
}
else{
node * temp;
node_init(&temp, value);
temp->next=plist->head;
plist->head=temp;
temp->prev = NULL;

}
}

### Activity 13: Implementation of removal

Record your answer here

// updates the list by removing the node referred to by pnode from the list
// needs fixing
void list_remove(list *plist, node *pnode) {
    //if the node is not the head or the tail
    if(plist ->head != pnode || plist-> tail != pnode ){
        // list has no head AND no tail -> list is empty, can't remove anything
        pnode->prev->next = pnode->next; //segmentation fault
        pnode->next->prev = pnode->prev;
        pnode->next = pnode->prev = NULL;
    }
    if(pnode == plist -> head){
        // won't work
        //2nd node will now be the head
        plist ->head ->next ->prev = NULL;
        plist ->head = pnode -> next;
        free(pnode);
        //2nd node prev will now point to null

    }
    if(plist->tail == pnode){
        // won't work
        // tail.prev == tail
        //tail.prev.next == NULL
        // free pnode

        plist -> tail = pnode ->prev;
        plist -> tail -> prev ->next = NULL;
        free(pnode);
    }
}
Code to test:
int main(void) {
    list * plist;
    list_init(&plist);
    list_prepend(plist, 4);
    list_prepend(plist, 3);
    list_prepend(plist, 2);
    list_prepend(plist, 1);
    
    list_remove(plist, plist->head->next);    // remove value 2
    for (node * ptr = plist->head; ptr != NULL; ptr = ptr->next) {
        printf("%d\n", ptr->value);
    }
}

//Process finished with exit code 139 (interrupted by signal 11: SIGSEGV)

### Activity 14: Implementing insertion

Record your answer here

// updates the list by inserting value before the node referred to by pInsertionPoint
void list_insert(list *plist, node *pbefore, node *pnode) {
    pnode->next = pbefore;
    pnode->prev = pbefore->prev;
    if (pbefore->prev != NULL) pbefore->prev->next = pnode;
    else plist->head = pnode;
    pbefore->prev = pnode;
}

list_insert(plist, plist->head, node)

### Activity 15: Time complexities

Record your answer here

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

## Looking back

### What we've learnt

Formulate at least one lesson learned.

### What were the surprises

Fill in...

### What problems we've encountered

Fill in...

### What was or still is unclear

Fill in...

### How did the group perform?

How was the collaboration? What were the reasons for hick-ups? What worked well? What can be improved next time?

> Written with [StackEdit](https://stackedit.io/).