# Week 3 - Linked Lists

## Team

Team name: Totally Useless Inc.
Date: 2022-03-03

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. | Justas |
| **Spokesperson** communicates group’s questions and problems to the teacher and talks to other teams; presents the group’s findings. |Tautvydas|
| **Reflector** observes and assesses the interactions and performance among team members. Provides positive feedback and intervenes with suggestions to improve groups’ processes. | Adelina |
| **Recorder** guides consensus building in the group by recording answers to questions. Collects important information and data. | Ines |

## 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
The ppptr value represents the address of the pptr.

| Variable | Address | Value |
| ----------- | --------------------- | ----------- |
| value | 0x7fff4108fd9c | 42 |
| ptr | 0x7fff4108fda0 | 0x7fff4108fd9c |
| pptr | 0x7fff4108fda8 | 0x7fff4108fda0 |
| ppptr | 0x7fff4108fdb0 | 0x7fff4108fda8 |

### 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};
	node *head = &first;
    
	for (int i = 0; i < 4; i++) {
        printf("%d\n", head->value);
        head = head->next;
    }
}

### Activity 4: Linked list deallocation

Initially list_free function only freed the pointers pointing to the begging and the ending of the nodes. Therefore, it is not linked in either way and as a result, when freeing those pointers the nodes ar not freed. As a result, it is needed to free each node by looping.

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

### Activity 5: Prepending

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

### Activity 6: Time complexity of prepend and append
The time complexity of appending is O(1) because all it takes to append is just create a new node and initialize it with a value and a pointer NULL in case there is no more nodes.
The time complexity of appending if we did not keep track of the tail would be O(n).

### 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) {
    int count = 0;
    node *node_t =plist->head;

    while (node_t != NULL) {
        if (count == index) {
            printf("%d", node_t->value);
            return (node_t);
        }
        count ++;
        node_t = node_t->next;
    }

    return NULL;
}

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

The time complexity of accessing by index is O(n). The reason behind this that it has to go from the first node till the index that is needed.

### Activity 9: A bad for-loop

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

This approach adds an unnecessary step of calling list_at, which has an additional loop in itself. The example above will have a time complexity of O(n^2).

An alternative to printing all the values of the linked list would be as follows:

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

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

void list_remove_last(list * plist) {
    node *newTail = plist->head;

    if (newTail == NULL) {
        node_free(&plist->tail);
        plist->head = NULL;
    }else {
        while(newTail != NULL) {
            if(newTail->next->next == NULL) {
                newTail->next = NULL;
                node_free(&plist->tail);
                plist->tail = newTail;
                break;
            }
            newTail = newTail->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 *p = (node*) malloc(sizeof(node));
    if(p != NULL){
        p->prev = NULL;
        p->next = NULL;
        p->value = value;
    }
    *ptr = p;
}

### Activity 12: Code update - II

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

### 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(pnode->prev == NULL){
    plist->head = pnode->next;
  }
  if(pnode->next == NULL){
    plist->tail = pnode->prev;
    pnode->prev->next = NULL; 
  }
  else{
    pnode->prev->next = pnode->next;
    pnode->next->prev = pnode->prev;
  }
  pnode->next = pnode->prev = NULL;
  
}

### Activity 14: Implementing insertion

//This is the code used to test the insertion of nodes on to the linked list
#include <stdio.h>
#include <stdlib.h>

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

void list_free(list * plist);
void list_init(list ** plist);
void node_init(node ** ptr, int value);
void list_insert(list *plist, node *pbefore, node *pnode);
void list_append(list * plist, int value);
int main(void) {
    list * plist;
    node * pnode;
    list_init(&plist);
    list_append(plist, 1);
    list_append(plist, 2);
    list_append(plist, 3);
    list_append(plist, 4);
    list_append(plist, 5);
    //testing the insertion of nodes onto the linked list
    node_init(&pnode, 100);
    list_insert(plist, plist->head, pnode);
    node_init(&pnode, 1000);
    list_insert(plist, plist->tail, pnode);
    list_free(plist);

    return 0;
}

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

}

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

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

void list_append(list * plist, int value) {
  if (plist->head == NULL) {
    node_init(&plist->head, value);
    plist->tail = plist->head;
  }
  else {
    node_init(&plist->tail->next, value);
    if (plist->tail->next != NULL) {
      // let new node point back to current tail
      plist->tail->next->prev = plist->tail;
      // update tail
      plist->tail = plist->tail->next;
    }
  }
}

void list_remove (list *plist, node *pnode){
  if(pnode->prev == NULL){
    plist->head = pnode->next;
  }
  if(pnode->next == NULL){
    plist->tail = pnode->prev;
    pnode->prev->next = NULL;
  }
  else{
    pnode->prev->next = pnode->next;
    pnode->next->prev = pnode->prev;
  }
  pnode->next = pnode->prev = NULL;
}

### Activity 15: Time complexities

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

## Looking back

### What we've learnt

We gained confidence with dealing with pointers.
We understood how to create singly and doubly linked lists.

### What were the surprises

How many pointers we needed to handle.

### What problems we've encountered

We had troubles understanding doubly linked lists.

### What was or still is unclear

How to work with doubly linked lists.

### How did the group perform?

The group is still having problems with choosing the ideal method for dividing the tasks and with people being busy with other courses it's difficult to meet up and work on the assignments together.

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