# Week 2 - Linked Lists

## Team

Team name: Group 4

Date: 19/2/2021

Members:
Pedro Sousa Garcia, Bogdan Iliescu, Zahir Josefina, Max Thielen
| Role | Name |
|-------------------------------------------------------------------------------------------------------------------------------------------------------------------------------|------|
| **Facilitator** keeps track of time, assigns tasks and makes sure all the group members are heard and that decisions are agreed upon. | Bogdan Iliescu |
| **Spokesperson** communicates group’s questions and problems to the teacher and talks to other teams; presents the group’s findings. | Max Thielen |
| **Reflector** observes and assesses the interactions and performance among team members. Provides positive feedback and intervenes with suggestions to improve groups’ processes. |Pedro Sousa Garcia|
| **Recorder** guides consensus building in the group by recording answers to questions. Collects important information and data. | Zahir Josefina |

## Activities

### Activity 1: Linked lists versus arrays

Retrievel:
* Array = array elements can be accessed randomly using the array index.
* Linked lists = random accessing is not possible in linked lists. The elements needs to be accessed sequentially.

Appending:
* Array = no built in function exists for appending an array in C. To append an array keep the pointer to your last inserted index in the array and move it forward until you reach the end of the array.
* Linked lists = you can add a node at the beginning of a linked list, after a given node and at the end of a linked list. Adding a node at the front is a 4 strep process. Adding a node after a given node is a 5 step process. Adding a node at the end is a 6 step process. Time complexity is 0(n) where n is the number of nodes in the linked list. You can optimise the method to make it work in 0(1) by keeping an extra pointer to tail of the linked list.

Instertion and deletion:
* Linked lists are better for insertion and deletion. Inserting a new element in an array of elemnts is expensive because a room has to be created for the new element which requires the shifting of other elements. Deletion in arrays can be expensive deleting one element leads to the moving of everything after that element. On the other hand insertion and deleition operations are fast and easy in linked lists.

Linked list over array:
* Implementation of hash tables

### Activity 2: Linked list initialization
And that's how you insert code blocks:

typedef struct LLNode {
    int value;
    struct LLNode* pPrevious;
    struct LLNode* pNext;
} LinkedListNode;

typedef struct {
    LinkedListNode *pHead;
    LinkedListNode *pTail;
    int count;
} LinkedList;

void linkedlist_init(LinkedList *pList){
    *pList = (LinkedList){ .pHead = NULL, .pTail=NULL, .count=0};
}

### Activity 3: Adding nodes & memory

The structure should be kept on the heap because stack is temporary storage. When the task is complete the memory of the variable will be automatically erased.

### Activity 4: Appending and prepending elements

void linkedlist_append(LinkedList *pList, int value){
    LinkedListNode *newNode = (LinkedListNode *) malloc(sizeof(LinkedListNode));
    newNode->value = value;
    newNode->pNext = pList->pTail;

    if(pList->count==0) {
        pList->pHead = newNode;
        newNode->pPrevious = NULL;
    }
    else {
        LinkedListNode *temp = pList->pHead;

        while (temp->pNext != NULL) {
            temp = temp->pNext;
        }
        temp->pNext = newNode;
        newNode->pPrevious = temp;
    }
    ++pList->count;
}
// prepends value to the list referred to by pList
void linkedlist_prepend(LinkedList *pList, int value){
    //create new node
    LinkedListNode *newNode = (LinkedListNode*)malloc(sizeof(LinkedListNode));
    newNode->value = value;

    pList->pHead->pPrevious = newNode;
    newNode->pNext = pList->pHead;
    newNode->pPrevious = NULL;
    pList->pHead = newNode;

    ++pList->count;
}

### Activity 5: Print the contents of a linked list

void linkedlist_print(const LinkedList *pList)
{
    LinkedListNode *pCurrent = pList->pHead;
    printf("[");
    if (pCurrent != NULL)
    {
        printf("%d", pCurrent->value);
        pCurrent = pCurrent->pNext;

        while (pCurrent != NULL)
        {
            printf(", %d", pCurrent->value);
            pCurrent = pCurrent->pNext;
        }
    }
    printf("] ");
    printf("count: %d\n", pList->count);
}

int main()
{
LinkedList list;
linkedlist_init(&list);

linkedlist_append(&list, 2);
linkedlist_append(&list, 3);
linkedlist_print(&list);

linkedlist_prepend(&list, 1);
linkedlist_append(&list, 4);
linkedlist_print(&list);


linkedlist_append(&list, 5);
linkedlist_prepend(&list, 0);
linkedlist_append(&list, 6);
linkedlist_print(&list);

return 0;
}

### Activity 6: Element retrieval

const LinkedListNode *linkedlist_get(const LinkedList *pList, int index){
    //check if index is valid
    if(index>=0) {
        //check if list is initialized and contains values
        if(pList->count==0) {return NULL;}
        else{
            //create temporary node
            LinkedListNode *temp = pList->pHead;

            //loop to desired index
            for (int i = 0; i < index; i++) {
                temp = temp->pNext;
            }

            //return LinkListNode
            return temp;
        }
    }
    return NULL;
}

### Activity 7: The const keyword

A const can be applied to any variable so that its value will not be changed. In the function const will not allow for the user to change the value of the entity pointed using a pointer.

### Activity 8: Time complexity of retrieval
Since the time for link-list retival is defined as O(n) a list with size 2N versus a list of size N would take twice as long to retrive a variable.

### Activity 9: Implementing insertion

// updates the list by inserting value before the node referred to by pInsertionPoint
void linkedlist_insert(LinkedList *pList, LinkedListNode *pInsertionPoint, int value){
    //create new node
    LinkedListNode *newNode = (LinkedListNode *) malloc(sizeof(LinkedListNode));
    //check if prepend is applicable
    if(pInsertionPoint == pList->pHead){
        linkedlist_prepend(pList, value);
    }
    else{
        //set value
        newNode->value = value;
        //set pointers
        newNode->pPrevious = pInsertionPoint->pPrevious;
        newNode->pNext = pInsertionPoint;
        //integrate in list
        pInsertionPoint->pPrevious->pNext = newNode;
        pInsertionPoint->pPrevious = newNode;
    }
}

### Activity 10: Linked lists and memory management

Must linkelist_remove release the memory?
* No because the release of the memory can become troublesome if the goal of the user is to simply move the linked list node. If the data is imidiatly freed then the users loses the ablity to reuse the same Node.

Suppose that the linkedlist_remove function would not release the memory, whose responsibility is it then to release this memory?
* If linkedlist_remove does not release memory than linkedlist_insert could be the one responsible for this

### Activity 11: Implementation of removal

// updates the list by removing the node referred to by pNode from the list
void linkedlist_remove(LinkedList *pList, LinkedListNode *pNode){
    if(pList->count>=3){
        if(pNode==pList->pHead){
            pList->pHead = pNode->pNext ;
            pList->pHead->pPrevious = NULL;
        }
        else if(pNode==pList->pTail){
            pList->pTail = pNode->pPrevious;
            pList->pTail->pNext = NULL;
        }
        else {
            pNode->pPrevious->pNext = pNode->pNext;
            pNode->pNext->pPrevious = pNode->pPrevious;
        }
        pNode = NULL;
    }
    else if(pList->count==2){
        if(pNode==pList->pHead){
            pList->pTail->pPrevious = NULL;
            pList->pHead=pList->pTail;
        }
        else if(pNode==pList->pTail){
            pList->pHead->pNext = NULL;
            pList->pTail=pList->pHead;
        }
    }
    else{
        pList->pHead = NULL;
        pList->pTail = NULL;
    }
    free(pNode);
    --pList->count;
}

### Activity 12: Implementing merge

// merges the contents of pListB into pListA
// on return, pListB will be empty.
void linkedlist_merge(LinkedList *pListA, LinkedList *pListB){
    for(int i = 0; i<pListA->count; i++) {
        while(linkedlist_get(pListA, i)->value >= pListB->pHead->value){
            linkedlist_insert(pListA, linkedlist_get(pListA, i), pListB->pHead->value);
            linkedlist_remove(pListB, pListB->pHead);
        }
    }
    while(pListB->count>0) {
        linkedlist_append(pListA, pListB->pHead->value);
        linkedlist_remove(pListB, pListB->pHead);
    }
}

### Activity 13: Time complexity of merge

The time complexity of this function would remain N since there technically are no nested loops. The function is simply running through LinkedListA and removing the head of LinkedListB while the head of B is smaller or equal to the index of A. The last while loop simply brings over the remaining nodes from LinkedListB.

### Activity 14: Implementing sorted insert

// inserts value into pList, such that pList remains sorted
void linkedlist_sorted_insert(LinkedList *pList, int value){
    for(int i = 0; i<pList->count; i++) {
        if(pList->pTail->value<=value){
            linkedlist_append(pList, value);
            break;
        }
        else if (linkedlist_get(pList, i)->value <= value && linkedlist_get(pList, i)->pNext->value >= value) {
            linkedlist_insert(pList, linkedlist_get(pList, i)->pNext, value);
            break;
        }
    }
}

### Activity 15: Time complexity of sorted insert
The time complexity of this function would remain N as well since there definitly are no nested loops here. The function is simply running through the LinkedList and and finding the point of insertion with two if statements.

### Activity 16: Extra (sort of useless code)

//moves a node at a specified index to the destination index
void linkedlist_move(LinkedList *pList, int index, int destination){
    LinkedListNode *var1 = linkedlist_get(pList, index);
    linkedlist_remove(pList, var1);
    if(destination==pList->count){
        linkedlist_append(pList, var1->value);
    }
    else if(destination == 0){
        linkedlist_prepend(pList, var1->value);
    }
    else{
        LinkedListNode *var2 = linkedlist_get(pList, destination);
        linkedlist_insert(pList, var2, var1->value);

    }
}

//swaps the nodes at the specified indexes
void linkedlist_swap(LinkedList *pList, int index1, int index2){
    if(index1<index2){
        linkedlist_move(pList, index1, index2);
        linkedlist_move(pList, index2-1, index1);
    }
    else{
        linkedlist_move(pList, index2, index1);
        linkedlist_move(pList, index1-1, index2);
    }
}

//sorts the given pList from smallest to largest value
void linkedlist_sort(LinkedList *pList){
    int i;
    for(int k=0; k<pList->count; k++){
        i=0;
        while(i<pList->count-1) {
            if (linkedlist_get(pList, i)->value > linkedlist_get(pList, i + 1)->value) {
                linkedlist_swap(pList, i, i + 1);
            }
            i++;
        }
    }
}

int main()
{
printf("\n-----------------Basic Functions Test------------------------\n");
LinkedList list;
linkedlist_init(&list);

linkedlist_append(&list, 2);
linkedlist_print(&list);

linkedlist_append(&list, 3);
linkedlist_print(&list);

linkedlist_prepend(&list, 1);
linkedlist_append(&list, 4);
linkedlist_print(&list);

linkedlist_append(&list, 5);
linkedlist_prepend(&list, 0);
linkedlist_print(&list);

linkedlist_append(&list, 6);
linkedlist_print(&list);

linkedlist_move(&list, 5, 6);
linkedlist_print(&list);

linkedlist_swap(&list, 6, 3);
linkedlist_print(&list);

linkedlist_swap(&list, 6, 0);
linkedlist_print(&list);

linkedlist_sort(&list);
linkedlist_print(&list);

printf("\n-----------------Merge Test------------------------\n");

LinkedList listA;
linkedlist_init(&listA);

linkedlist_append(&listA, 1);
linkedlist_append(&listA, 10);
linkedlist_append(&listA, 20);

printf("List A: ");
linkedlist_print(&listA);

LinkedList listB;
linkedlist_init(&listB);

linkedlist_append(&listB, 12);
linkedlist_append(&listB, 14);
linkedlist_append(&listB, 16);
linkedlist_append(&listB, 42);

printf("List B: ");
linkedlist_print(&listB);

linkedlist_merge(&listA, &listB);
printf("List A: ");
linkedlist_print(&listA);
printf("List B: ");
linkedlist_print(&listB);

printf("\n-----------------Sorted Insert Test------------------------\n");
LinkedList listI;
linkedlist_init(&listI);

linkedlist_append(&listI, 0);
linkedlist_append(&listI, 1);
linkedlist_append(&listI, 3);
linkedlist_append(&listI, 4);
linkedlist_append(&listI, 5);
linkedlist_append(&listI, 7);
linkedlist_append(&listI, 10);

printf("List: ");
linkedlist_print(&listI);

linkedlist_sorted_insert(&listI, 11);

printf("List: ");
linkedlist_print(&listI);
return 0;
}

## Look back

### What we've learnt

This week we learned how to set up a brand new data structure called a double linked list. A linked list manily relies on it's pointers to the next (and sometimes previous) node to maintain a cohesive structure. Unlike simple arrays, modefying the length of a linked list is much easier since it soley dependent on modfying the existing pointers and creating a new node struct.

### What were the surprises

What suprised us this week was the difference in time compexity between arrays and linked lists. Although the linked list is not as rigit in size, the array has a big benifit of the index being much easier to access and modify.

### What problems we've encountered

The biggest problem we encountered was messing with existing pointers. It is sometimes very difficult to visulize the established linked list and what would happen when moving or swapping an element within that list. The pointers sometimes stay attached creating a bigger list than desired and many many times we ran into out of bounds errors which are like always hair-pullingly frustrating.

### What was or still is unclear

After messing with the code a bunch and even writing some fun extra functions the linked list concept is decently clear to us now.

### How did the group perform?

Collaboration was pretty hard especially with the holliday in the middle of the assignment however we pulled through and managed to write the code cohesivly. I explained the code to the rest of the group to ensure that we all learned the same thing and make sure we're all on the same page.