# Week 3 - Linked Lists

## Team

Team Name: Banana Technologies
Date: Wednesday 3 March 2022
|----------------------------------------------------------------------------|
Members:
Nafizul Habib Redwan
Siebe de Bruijn
Naomi Verschuur
Yazan Tayeh

| Role | Name |
|-----|-----|
| **Facilitator** keeps track of time, assigns tasks and makes sure all the group members are heard and that decisions are agreed upon.|Siebe de Bruijn |
| **Spokesperson** communicates group’s questions and problems to the teacher and talks to other teams; presents the group’s findings.|Nafizul Habib Redwan|
| **Reflector** observes and assesses the interactions and performance among team members. Provides positive feedback and intervenes with suggestions to improve groups’ processes. |Yazan Tayeh|
| **Recorder** guides consensus building in the group by recording answers to questions. Collects important information and data.|Naomi Verschuur|

## 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
@Nafiz
Record your answer here:

| Variable | Address | Value |
| ----------- | --------------------- | ----------- |
| value | | |
| ptr | | |
| pptr | | |
| ppptr | | |

### Activity 2: Chaining pointers
@Nafiz

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

Record your answer here:

### Activity 3: Traversal
@Nafiz

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:

### Activity 4: Linked list deallocation
@sdbruijn
Record your answer here:

void list_free(list ** plist) {
	free(*plist);
	*plist = NULL;
}

### Activity 5: Prepending
@yazantayeh

void list_prepend(list * plist, int value) {
    if (plist->head == NULL) {
        node_init(&plist->head, value);
        plist->tail = plist->head;
    }
    else {
        struct node_t *temp = plist->head;
        node_init(&plist->head, value);
        plist->head->next = temp;
    }
 }

### Activity 6: Time complexity of prepend and append
@NaomiVerschuur
Record your answer here:

What is the time complexity of appending a new element, and why? Give your answer in Big O notation.
- The time complexity for insertion is O(1) while deletion is O(n) (in the worst case) for a single operation. The amortized costs for both are O(1) since having to delete n elements from the queue still takes O(n) time.

What would the time complexity of appending be if we would not keep track of the tail in the list structure?
- For Time Complexity to insert element at front is O(1) in Singly Linked List but it is O(√N) for Doubly Linked List as we have to access the next element to set its previous address to the new element.

### Activity 7: Access by index
@sdbruijn
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);

### Activity 8: Time complexity of accessing by index
@Nafiz
Record your answer here:

### Activity 9: A bad for-loop
@NaomiVerschuur
Record your answer here:

A for-loop is almost exclusively used to traverse the contents of a sequence that provides random access, such as an array. But given the function list_at that you’ve just implemented, we could just as well traverse the contents of a linked list in the very same way, as shown below.
Why is this approach a bad idea? Motivate your answer by giving the time complexity of the loop shown below.
- In a Linked list traversal is more time-consuming as compared to an array. Direct access to an element is not possible in a linked list as in an array by index. For accessing a node at position n, one has to traverse all the nodes before it.

for(inti=0;i<COUNT;i++)
{
    printf("%d\n", list_at(list, i)->value);
}

### Activity 10: Removal in a singly-linked list
@sdbruijn
Record your answer here:

In order to remove the last element in our linked list, we can’t simply call **node_free** on the tail pointer, as there may be a second-to-last node that points to it - leaving a dangling pointer. You will need to traverse the list to find the node that comes before the last node.
Implement the **list_remove_last** function shown below. You may assume that the list← argument **plist** is not empty.

void list_remove_last(list * plist) {
	node_free(&list->tail);
}

### Activity 11: Code update - I

@yazantayeh

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

void node_init(node ** ptr, node *prev, int value) {
     node *p = (node*) malloc(sizeof(node));
     if (p != NULL) {
         p->next = NULL;
         p->value = value;
         p->prev = prev;
     }
     *ptr = p;
 }

### Activity 12: Code update - II
@sdbruijn
Record your answer here:

### Activity 13: Implementation of removal
@yazantayeh

 void list_remove(list *plist, node *pnode) {
    if(pnode->prev == NULL){
        plist->head = pnode->next;
        plist->head->prev = NULL;
    }else if(pnode->next == NULL){
        plist->tail = pnode->prev;
        plist->tail->next = NULL;
    }else{
        pnode->prev->next = pnode->next;
        pnode->next->prev = pnode->prev;
    }
     pnode->next = pnode->prev = NULL;
}

### Activity 14: Implementing insertion
@yazantayeh
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
@NaomiVerschuur
Record your answer here:

The (dynamic) array and the linked list both offer a similar set of operations:
- **Access by "index"** looks up and returns the value or node stored at the given index or position in the data structure.
- **Appending** adds a new value to the end of the sequence.
- **Insertion** adds a new node or value to the sequence, before a given position, referred to by either index or node pointer.
- **Removal** removes a new node or value from the sequence, specified by either index or node pointer.
- Give the (amortized) time complexities for these four operations, using Big O notation, in terms of the number of elements, n, in the sequence.

| Operation | Array | Linked List |
| --------------- | -------------------------- | ----------- |
| Access | O(1) |The get() method of the LinkedList class is used to access an element from the LinkedList. An element can be searched in a list by going through each element and checking it against the required element. As the element Nodes can only be accessed linearly, only a linear search can be performed.|
| Append | O(n) |To append to a singly-linked list, Traverse the linked list till the end. Store the location of the last node into current_node. 1. Create a new_node to be appended. 2. Update the next link of the current_node by pointing it to the new_node. |
| Insert | n+1 |To insert into a singly-linked list, we need to know the node after which we need to insert a new_node. 1. Traverse the linked list and store the location of the node after which a new_node is to be inserted. 2. If the current_node is not Null then; Create a new_node that is to be insertedl; Store the location of the node that is next to the current_node; Update the next link of the current_node by pointing it to the new_node; Point the new_node’s next link to next_node.|
| Remove| free() for freeing memory allocated for the node to be deleted | You can delete either from the beginning, end or from a particular position.the first method is to delete from beginning you have to point head to the second node The second one is to delete from end you first has to traverse to second last element; so Change its next pointer to null.struct Then lastly it is to delete from middle. So you have to traverse to element before the element to be deleted. Then change next pointers to exclude the node from the chain|

## 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/).