# 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 |000000000061FE14|42 |
| ptr |000000000061FE14| 42 |
| pptr |000000000061FE08| 42|
| ppptr |000000000061FE00| 42|
### 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);
}
```
````c
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*/);
}
}
```
````c
for (node i = first; next; i = *i.next) {
printf("%d\n", i.value);
if(i.next == NULL){
next = false;
}
}
````
### Activity 4: Linked list deallocation
```c
void list_free(list ** plist) {
free(*plist);
*plist = NULL;
}
```
```c
while(list1.head != NULL) {
node *tmp = list1.head;
list1.head = list1.head->next;
node_free(&tmp);
}
```
### 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 *newHead;
node_init(&newHead, value);
newHead->next = plist->head;
plist->head = newHead;
}
}
```
```c
void list_prepend(list * plist, int value);
```
### Activity 6: Time complexity of prepend and append
o(1) omdat de tijd altijd even lang duurt
als je de tail niet zou bijhouden zou het o(n) zijn omdat je door elk element heen gaat.
### Activity 7: Access by index
```c
const node *list_at(const list *plist, int index){
bool next = true;
int count = 0;
for (node i = *plist->head; next; i = *i.next) {
if (count == index){
printf("%d\n", i.value);
}
count++;
if (i.next == NULL) {
next = false;
}
}
}
```
```c
// returns the node at index 'index' in the list referred to by pList
const node *list_at(const list *plist, int index);
```
### Activity 8: Time complexity of accessing by index
o(n) omdat naar mate de lijst groter wordt de functie langer duurt.
### Activity 9: A bad for-loop
Dit is een slechte forloop omdat de typecomplexety o(x^2) is. Omdat elke keer door de hele lijst wordt heen gegaan.
### Activity 10: Removal in a singly-linked list
```c=
void list_remove_last(list *plist) {
node *last = plist->tail;
node *secondLast;
bool next = true;
for (node *i = plist->head; next; i = i->next) {
if (i->next == last) {
secondLast = i;
next = false;
}
if (i->next == NULL) {
next = false;
}
}
secondLast->next = NULL;
plist->tail = secondLast;
free(last);
}
```
```c
void list_remove_last(list * plist) {
node_free(&list->tail);
}
```
### Activity 11: Code update - I
```c=
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->next = NULL;
p->value = value;
p->prev = NULL;
}
*ptr = p;
}
```
### 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 *newHead;
node_init(&newHead, value);
plist->head->prev = newHead;
newHead->next = plist->head;
plist->head = newHead;
}
}
```
### Activity 13: Implementation of removal
Record your answer here
```c
// updates the list by removing the node referred to by pnode from the list
void list_remove(list *plist, node *pnode) {
pnode->prev->next = pnode->next;
pnode->next->prev = pnode->prev;
pnode->next = pnode->prev = NULL;
}
```
### 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 | | |
| Append | | |
| Insert | | |
| Remove | | |
## 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/).
Sign in with Wallet
Connect another wallet