---
# System prepended metadata

title: Untitled

---

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

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

```c
    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:
```c=
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


```c
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



```c
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

```c
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

```c
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
```c
 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
```c
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

```c
// 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

```c
// 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/).
