# Week 3 - Linked Lists

## Team

Team name: D&Z
Date:2022-02-21

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

## 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 value of the variable ppptr represents the adress of pptr which points to the adress of ptr which points to the adres of value. Thats why all the values are the same
| Variable | Address | Value |
| ----------- | --------------------- | ----------- |
| value |000000000061FE1C| 42 |
| ptr |000000000061FE10| 42 |
| pptr |000000000061FE08| 42 |
| ppptr |000000000061FE00| 42 |

### Activity 2: Chaining pointers

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

int main(void) {

    node * first= (struct node *)malloc(sizeof(node));
    node * second= (struct node *)malloc(sizeof(node));
    node * third= (struct node *)malloc(sizeof(node));
    node * fourth= (struct node *)malloc(sizeof(node));

    first->value=2;
    first->next=second;
    second->value=3;
    second->next=third;
    third->value=7;
    third->next=fourth;
    fourth->value=42;
    fourth->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);

Record your answer here

### Activity 3: Traversal

int main(void) {

    node *first = (struct node *) malloc(sizeof(node));
    node *second = (struct node *) malloc(sizeof(node));
    node *third = (struct node *) malloc(sizeof(node));
    node *fourth = (struct node *) malloc(sizeof(node));

    first->value = 2;
    first->next = second;
    second->value = 3;
    second->next = third;
    third->value = 7;
    third->next = fourth;
    fourth->value = 42;
    fourth->next = NULL;
        //innit           //condition    //advance
    for (node *temp=first; temp!=NULL; temp=temp->next) {
        printf("%d\n", temp->value);
    }

}

Record your answer here

### Activity 4: Linked list deallocation

Record your answer here

void list_free(list * plist) {
      
    free(plist);
     plist->head = NULL;
     plist->tail = NULL;
     }
}

### Activity 5: Prepending

Record your answer here

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

        new->next=plist->head;
        plist->head=new;
    }
}

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

The time complexity of appending a new element is O(n) because you only add an element at the end of the linked list. It increases linearly.

The time complexity of appending if we would not keep track of the tail is O(1). because you can add it as a head and in that way the time complexity is constant
### Activity 7: Access by index

Record your answer here

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

            }
            //printf("%d\n",index_search->value);
        }
    }
    printf("%d\n",index_search->value);
    return index_search;
}

int main(void) {
    list plist; // pointer to list
    list_init(&plist);
    list_append(&plist, 1);
    list_append(&plist, 2);
    list_prepend(&plist, 0);
    const node *test = list_at(&plist,2);
    printf("%d\n", test->value);

}

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

O(n) because you check every element in the linked list one by one. so the run time increase liniair with the input size.
### Activity 9: A bad for-loop

It is bad because you use 2 "for loops" to find and print each value. that approach takes too much time. The time complexity is O(n)

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

Record your answer here

void list_remove_last(list *plist) {
    int length=0;
    node *plist2=plist->head;
    while(plist2->next!=NULL){
        plist2=plist2->next;
        length++;
    }

    for (int i = 0; i < length; ++i) {
        if (i == 0) {
            plist2 = plist->head;
        } else {
            plist2 = plist2->next;

        }
        //printf("%d\n",index_search->value);
    }
    plist2->next=NULL;
    node_free(&plist->tail);
    plist->tail=plist2;
}

### Activity 11: Code update - I

// heap-allocates and initializes a node structure
void node_init(node **ptr, int value) {
    node *p = (node *) malloc(sizeof(node));
    if (p != NULL) {
        p->next = NULL;
        p->prev = NULL;
        p->value = value;
    }
    *ptr = p;
}

Record your answer here

### Activity 12: Code update - II

void list_remove_last(list *plist) {
    // save address of last node
    node *last = plist->tail;
    // let predecessor of last point to nothing
    if (last->prev != NULL) last->prev->next = NULL;
        // or set list to empty if there's no predecessor
    else plist->head = NULL;
    // update tail of the list
    plist->tail = last->prev;
    // free the node
    node_free(&last);
}

Record your answer here

### Activity 13: Implementation of removal

Record your answer here

// updates the list by removing the node referred to by pnode from the list
// 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){//head
        plist->head = pnode->next;
        pnode->next->prev = NULL;
    }
    else 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

Record your answer here

// updates the list by inserting value before the node referred to by pInsertionPoint
int main(void) {
    list plist; // pointer to list
    list_init(&plist);
    list_append(&plist, 1);
    list_append(&plist, 2);
    list_prepend(&plist, 0);

    node *p = (node *) malloc(sizeof(node));
    p->next = NULL;
    p->prev = NULL;
    p->value = 999;


    list_insert(&plist,plist.head,p);


}

### Activity 15: Time complexities

Record your answer here

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

## Looking back

### What we've learnt

The point of using linked list instead of arrays in certain moments. for example when you need to add an unknow number of elements.

### What were the surprises

The use of pointers in combination with the linked list functions.

### What problems we've encountered

We had a difficult time with the use of pointers. Because we needed to use it a lot in this weeks assignments

### What was or still is unclear

//

### 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/).