---
# System prepended metadata

title: Untitled

---

﻿﻿# Week 3 - Linked Lists

## Team

Team name:One irection
Date: 03.03.2022

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

## 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       |  000000000000002A | 42 |
| ptr         |  000000000061FE14 | 42 |
| pptr        |  000000000061FE08 | 42 |
| ppptr       |  000000000061FE00 | 42 |

![](https://i.imgur.com/f2GVA6e.png)

 ppptr is a pointer to a pointer to a pointer...


### Activity 2: Chaining pointers

```c
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);
}
```
![](https://i.imgur.com/ajTyPCX.png)


### Activity 3: Traversal

```c
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 (/*init*/; /*condition*/; /*advance*/) {
		printf("%d\n", /*current value*/);
	}
}
```


Record your answer here
```
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 currentNode = first;
    for (int i = 0; i<5; i++) {
        node prevNode = currentNode;
        printf("value: %d\n", currentNode.value);
        currentNode = *prevNode.next;
    }
}



first: 2
second: 3
third: 7
fourth: 42
```
### Activity 4: Linked list deallocation

Record your answer here

The given code is not correct is because it deletes the list but not the elements inside. With this we go through each next element starting at head element and free it until tail - 1. The tail is then freed outside the while with the list itself.
```c
//deallocates a list structure
//deallocates a list structure
void list_free(list ** plist) {
    node *currentNode = (*plist)->head;
    while (currentNode->next != NULL) {
        node *prevNode = currentNode;
        printf("value: %d\n", currentNode->value);
        currentNode = prevNode->next;
        free(prevNode);
    }

    free((*plist)->tail);

    free(*plist);
    *plist = NULL;
}

```

### Activity 5: Prepending

Record your answer here

We take the current tail and set it's .next to a new tail.
```c
void list_prepend(list * plist, int value){
    node newTail ={.value = value, .next = NULL};
    *plist->tail->next = newTail;
}
```

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

Record your answer here

The time complexity of append and prepent is O(1) because we do 1 single operation, which is just attaching a node at the end of a list, the size of the list is irrelevant because we only need the last value.

### Activity 7: Access by index

Record your answer here: 

We go through each element until we reach index. 

```c
// returns the node at index 'index' in the list referred to by pList
const node *list_at(const list *plist, int index) {
    node *cNode = plist->head;
    for ( int i = 0; i < index; i++) {
        cNode = cNode->next;
    }
    return cNode;
}
```

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

the time complexity is O(n-1). It goes though each element but starting from 0. 


### Activity 9: A bad for-loop

Record your answer here: 

The for loop is bad because it goes through each element for each i. Meaning that for any index, the operational time is the alphanumerical sum of numbers until that index, so if we had to count until 5, we would have 1+2+3+4+5 number of operations so the time complexity is O((n(n+1))/2).

Example 1000 would need 1 + 2 + 3 + 4 + ... + 998 + 999 + 1000 = 500000 number of operations. so for each 
![](https://i.imgur.com/L4hlgSv.png)



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

Record your answer here

```c
void list_remove_last(list * plist) {
    node *cNode = plist->head;
    int listLength = 1;
    while (cNode->next != NULL) {
        cNode = cNode->next;
        listLength++;
    }
    list_at(plist, listLength-1)->next = NULL;
    free(plist->tail);

    node_free(&plist->tail);
}
```

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

// heap-allocates and initializes a list structure
void list_init(list ** plist) {
    list * ptr = malloc(sizeof(list));
    if (ptr != NULL) {
        ptr->head = ptr->tail = NULL;
    }
    *plist = ptr;
}

```

### Activity 12: Code update - II
```C
void list_prepend(list * plist, int value){
    node newHead ={.value = value, .prev = NULL};
    *plist->head->prev = newHead;
}
```
### Activity 13: Implementation of removal

Record your answer here

The code went wrong because the prev and next were NULL for the first and last elements, so they couldn;t be used. This new code makes it so the previous/next elements become null and then deletes them.

```c
// 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) {
        pnode->next->prev = NULL;
        node_free(pnode);
    } else if (pnode->next == NULL) {
        pnode->prev->next = NULL;
        node_free(pnode);
    } else {
    pnode->prev->next = pnode->next;
    pnode->next->prev = pnode->prev;
    pnode->next = pnode->prev = NULL;
    node_free(pnode);
    }
}
```

### 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) {
    
}
```

### Activity 15: Time complexities

Record your answer here

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

*assuming that the inserion and removal are separate operations from finding their location, in which case it would be O(n).
code: 

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



// heap-allocates and initializes a list structure
void list_init(list ** plist) {
    list * ptr = malloc(sizeof(list));
    if (ptr != NULL) {
        ptr->head = ptr->tail = NULL;
    }
    *plist = ptr;
}

// deallocates a node structure
void node_free(node ** ptr) {
    free(*ptr);
    *ptr = NULL;
}

//deallocates a list structure
void list_free(list ** plist) {
    node *currentNode = (*plist)->head;
    while (currentNode->next != NULL) {
        node *prevNode = currentNode;
        printf("value: %d\n", currentNode->value);
        currentNode = prevNode->next;
        free(prevNode);
    }

    free((*plist)->tail);

    free(*plist);
    *plist = NULL;
}

void list_prepend(list * plist, int value){
    node newHead ={.value = value, .prev = NULL};
    *plist->head->prev = newHead;
}
void list_append(list * plist, int value){
    node newTail ={.value = value, .next = NULL};
    *plist->tail->next = newTail;
}

node *list_at(list *plist, int index) {
    node *cNode = plist->head;
    for ( int i = 0; i < index; i++) {
        cNode = cNode->next;
    }
    return cNode;
}

void list_remove_last(list * plist) {
    node *cNode = plist->head;
    int listLength = 1;
    while (cNode->next != NULL) {
        cNode = cNode->next;
        listLength++;
    }
    list_at(plist, listLength-1)->next = NULL;
    free(plist->tail);

    node_free(&plist->tail);
}

// 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) {
        pnode->next->prev = NULL;
        node_free(pnode);
    } else if (pnode->next == NULL) {
        pnode->prev->next = NULL;
        node_free(pnode);
    } else {
    pnode->prev->next = pnode->next;
    pnode->next->prev = pnode->prev;
    pnode->next = pnode->prev = NULL;
    node_free(pnode);
    }
}

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

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};
    list *list;
    list_prepend(list, 2);
    list_prepend(list, 3);
    list_prepend(list, 7);
    list_prepend(list, 42);
    list_prepend(list, 69);
    list_prepend(list, 94);
    for (int i = 0; i<5; i++) {
        printf("%d\n", list_at(list, i)->value);
    }
}
```

## Looking back

### What we've learnt

What linked lists are and how to use them

### What were the surprises

That such a way of naviagation through a list works.

### What problems we've encountered

Hard time figuring out the concepts of next and prev.

### What was or still is unclear

understanding Real Time Complexity

### How did the group perform?

We did well, all collaborated together with the codeTogether app in CLion in rael time.





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