# Week 3 - Linked Lists

## Team

Team name:BeastFromTheEast
Date:14/03/2022

Members
Casian Ionescu, Nikola Zahariev, Attila Poldan, Alexandra Melei
| 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.
Assignments done:
Nikola Zahariev: 1-3

### Activity 1: Pointers to pointers

Record your answer here:

| Variable | Address | Value |
| ----------- | --------------------- | ----------- |
| value | 000000000000002A | 42 |
| ptr | 000000000061FE14 | 6422036 |
| pptr | 000000000061FE08 | 6422024 |
| ppptr | 000000000061FE00 | 6422016 |

 int main(void)
 {
  int value = 42;
  int *ptr = &value;
  int **pptr = &ptr;
  int ***ppptr = &pptr;
  printf("The address of the variable '%s' is: %p and the value stored inside equals %d.\n", getName(value), value, value);
  printf("The address of the variable '%s' is: %p and the value stored inside equals %d. \n", getName(ptr), ptr, ptr);
  printf("The address of the variable '%s' is: %p and the value stored inside equals %d.\n", getName(pptr), pptr, pptr);
  printf("The address of the variable '%s' is: %p and the value stored inside equals %d.\n", getName(ppptr), ppptr, ppptr);
 }

In order to get the value stored in a pointer we have to dereference it. So if we make a pointer to a variable we dereference the pointer and we get the value stored inside. But if we have pointers that point to other pointers in order to get the value we need to dereference it as many times as we have it "referenced". Or in other words as many times as the amount of pointers pointing to other pointers we have.

This is the correct way to print all the values:

 int main(void)
 {
  int value = 42;
  int *ptr = &value;
  int **pptr = &ptr;
  int ***ppptr = &pptr;
  printf("The address of the variable '%s' is: %p and the value stored inside equals %d.\n", getName(value), value, value);
  printf("The address of the variable '%s' is: %p and the value stored inside equals %d. \n", getName(ptr), ptr, *ptr);
  printf("The address of the variable '%s' is: %p and the value stored inside equals %d.\n", getName(pptr), pptr, **pptr);
  printf("The address of the variable '%s' is: %p and the value stored inside equals %d.\n", getName(ppptr), ppptr, ***ppptr);
 }

And we get is:
The address of 'value' is: 000000000000002A and it equals 42.
The address of 'ptr' is: 000000000061FE14 and it equals 42.
The address of 'pptr' is: 000000000061FE08 and it equals 42.
The address of 'ppptr' is: 000000000061FE00 and it equals 42.
### Activity 2: Chaining pointers

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

int main(void)
{
	//node fourth = {.value = 42, .next = NULL};
	node four;
	four.value = 42; four.next = NULL;
	//node third = {.value = 7, .next = &fourth};
	node three;
	three.value = 7; three.next= &four;
	//node second = {.value = 3, .next = &third};
	node two;
	two.value = 3; two.next = &three;
	node first = {.value = 2, .next = &two};
	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

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};  
   for (node * now = &first; now != NULL ; now = now->next)
   {
  	printf("node data: %d\n", now->value);
   }
 }

Record your answer here

### Activity 4: Linked list deallocation

Record your answer here

void list_free(list ** plist)
{

  for (list *plist = &plist ; plist->tail != NULL ; plist->tail = plist->tail->next)
	{
	  free(plist->head);
	  plist->head = 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 *p;
        node_init(&p,value);
        p->next=plist->head;
        plist->head=p;
    }
}

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

Prepending time complexity: O(1)
Indifferent of the size of the linked list (be it empty or even nonexistent) appending will always be done in one single step, making it quite efficient.
Appending time complexity: O(n) with or without keeping track of the tail because in singly linked lists there is no quick way to get to the tail position. Doubly linked lists can have a tail pointer that can be referenced and used just like the head pointer here, in which case the time complexity would change to O(1).

### 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 * current=plist->head;
     for(int i = 0; i <= index; i++){
         if(i == index || current == NULL) return current;
         else{
             current=current->next;
         }
     }
     return current;
}
//test
int main() {
   list *ptr;
    list_init(&ptr);
    list_append(ptr,1);
    list_append(ptr,2);
    list_prepend(ptr,3);
    list_append(ptr,4);
    printf("%d  %d  %d  %d\n",ptr->head->value, ptr->head->next->value,ptr->head->next->next->value,ptr->head->next->next->next->value);
    printf("%d \n", list_at(ptr,2)->value);
    printf("%p \n", list_at(ptr,5));
    return 0;

output:
3 1 2 4
2
0000000000000000
### Activity 8: Time complexity of accessing by index

Record your answer here
The time complexity of the "at" function is O(n).
Its time complexity is linear because the operation time grows linearly based on the number of elements in the list.

### Activity 9: A bad for-loop

Record your answer here
This is a bad idea because the at function already runs through the list to find the element which we are searching for [O(n)]. Adding an other for loop outside of the function will square the time complexity. This is due to the fact we run through the list each time we want to access a value. O(n^2)

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

Record your answer here

void list_remove_last(list * plist) {
    node* current=plist->head;
    while(current->next!=plist->tail)
    {
        current=current->next;
    }
    node_free(&plist->tail);
    plist->tail=current;
    plist->tail->next=NULL;

}

### Activity 11: Code update - I

Record your answer here

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->prev= NULL;
        p->next = NULL;
        p->value = value;
    }
    *ptr = p;
}

### Activity 12: Code update - II

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_init(&plist->head->prev,value);
        plist->head->prev->next=plist->head;
        plist->head=plist->head->prev;
    }
}

### Activity 13: Implementation of removal

Record your answer here

// updates the list by removing the node referred to by pnode from the list
void list_remove(list *plist, node *pnode) {

    if(pnode->next==NULL) {
        plist->tail = pnode->prev;
        plist->tail->next=NULL;
    }
    else
        pnode->next->prev = pnode->prev;

    if(pnode->prev==NULL) {
        plist->head = pnode->next;
        plist->head->prev=NULL;
    }
    else
        pnode->prev->next = pnode->next;
     
    node_free(&pnode);
     }

### Activity 14: Implementing insertion

Record your answer here

// 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;
     }

### 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(n) |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?