# 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 |
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);
}
```
### 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
### 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/).
Sign in with Wallet
Connect another wallet