# Week 3 - Linked Lists

## Team

Team name: Cross-dressing SIMPS
Date: (01/03/2022)
ye (25%)

Members
Dawid: Dawid Swietlinski (518337)
Cristi: Cristian Cimpeanu (524091)
Vlad: Vladislav Serafimov(509761)
Steve: Stephen Cruz Wright(521476)

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

## 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

| Variable | Address | Value |
| ----------- | --------------------- | ---------------- |
| value | 000000000061FE1C | 42 |
| ptr | 000000000061FE10 | 000000000061FE1C |
| pptr | 000000000061FE08 | 000000000061FE10 |
| ppptr | 000000000061FE00 | 000000000061FE08 |

The ```ppptr``` variable stores the memory address of the ```pptr``` which stores ```ptr``` which is a pointer to the ```value``` variable.

### Activity 2: Chaining pointers

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

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};
	
	for(node *f_node = &first; f_node != NULL ; f_node = f_node->next) {
        printf("%d\n", f_node->value);
    }
}

### Activity 4: Linked list deallocation

The previous code only deallocated the list and not its nodes, which means that most of the memory used is not ```free```d.

void list_free(list ** plist) {
    Node *temp = new Node();
    
    while (plist.head!=NULL)
    {
        temp = plist->head;
        plist->head = plist->head->next;
        free(temp);
    }
    free(*plist);
    *plist = NULL;
}

### Activity 5: Prepending

void list_prepend(list *plist, int val){
    //if list is empty add new head 
    if (plist->head == NULL){
        node_init(&plist->head, value);
        plist->tail = plist->head;
    } else{ 
        //else point to head and make head pointer point to new node 
        node *head;
        node_init(&head, value);
        if (head!=NULL){
            head->next = plist->head;
            plist->head = head;
        }
    }
    
}

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

It's O(1) for both because they always create only one node and set the next/previous of the tail/head respectively point to it.
### Activity 7: Access by index

// returns the node at index 'index' in the list referred to by pList
const node *list_at(const list *plist, int index){
    node *curr = plist->head;
    //skip first
    for (int i = 1; i < index; ++i) {
        if (curr->next != NULL)
            curr = curr->next;
        else
            return NULL;
    }
    return curr;
}

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

The complexity is O(n). For the function to return the value all of the nodes in the list before the index need to be accessed.

### Activity 9: A bad for-loop

The code below is bad because it executes two embedded ```for``` loops under the hood. This takes a toll on the performance, especially when the list is big. The time complexity is $O(n^2)$

for (int i = 0; i < COUNT; i++) {
printf("%d\n", list_at(list, i)->value);
}

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

void list_remove_last(list * plist) {
    node *new_tail = plist->head;
    while (new_tail->next != NULL){
        if (new_tail->next == plist->tail){
            plist->tail = new_tail;
            node_free(&new_tail->next);
        }
        else
            new_tail = new_tail->next; 
    }
}

### Activity 11: Code update - I

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

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

### Activity 12: Code update - II

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

### Activity 13: Implementation of removal

// updates the list by removing the node referred to by pnode from the list
void list_remove(list *plist, node *pnode) {
	
    //if tail
    if(pnode == plist->tail){
        pnode->prev->next = NULL;
        plist->tail = pnode->prev;
        
    } /*if head*/else if(pnode == plist->head){
        plist->head = pnode->next;
        pnode->next = NULL;
    } else {
        //  make prev and enxt point to eachother
        pnode->prev->next = pnode->next;
        pnode->next->prev = pnode->prev;
        
        //dereference 
        pnode->next = NULL;
        pnode->prev = NULL;
    }
    
    
    
}

### Activity 14: Implementing insertion

// 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;
}

### Activity 15: Time complexities

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

## Looking back

### What we've learnt

Linked list are pretty pog unless you're trying to find an element by index.

### What were the surprises

We didn't do it last second (I hope).

### What problems we've encountered

Pointers to pointers gave me a headache.

### What was or still is unclear

Whether Cristi will show up (Elden Ring).

### How did the group perform?
Perfectly

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