# Week 2 - 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. |Larissa |
| **Spokesperson** communicates group’s questions and problems to the teacher and talks to other teams; presents the group’s findings. |Anton |
| **Reflector** observes and assesses the interactions and performance among team members. Provides positive feedback and intervenes with suggestions to improve groups’ processes. |Larissa |
| **Recorder** guides consensus building in the group by recording answers to questions. Collects important information and data. |Jesse |

## Activities

### Activity 1: Linked lists versus arrays

In the courses programming 1 & 2 you have used arrays a lot, and in the previous week, you have revisited them. Common operations performed on arrays and linked lists are retrieval, appending, insertion, and deletion.
Discuss how these four operations compare for arrays and linked lists, in terms of the effort it takes to implement these operations, and in terms of the time these operations take. Can you think of a situation where you would not want to use an array, but rather a (singly or doubly) linked list?

**Record your answer here:**
Bij retrieval is een array stukken beter. Bij een linked list heb je geen random access.
Bij appending is een linked list stukken beter. Je hoeft de grootte van een linked list niet te declaren.
Bij insertion is een linked list stukken beter. Bij een linked list kun je makkelijk items in het midden toevoegen.
Bij deletion is een array stukken beter. Doordat je daarbij random access hebt kun je ook makkelijk items verwijderen.

Als je een array aanmaakt en je maakt het bijvoorbeeld voor 100 elementen aan maar je gebruikt niet alle 100 elementen is het een waste of memory dit heb je bij linked lists niet.

Voorbeeld:
Vorige en volgende pagina in een webbrowser

### Activity 2: Linked list initialization

Implement the linkedlist_init function, using the prototype definition listed below. Make sure that the head and tail of the initialized linked list are set to NULL.

**Record your answer here:**

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


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

void linkedlist_init(LinkedList *list){
    list->pHead = NULL;
    list->pTail = NULL;
}

### Activity 3: Adding nodes & memory

Discuss with your group: when adding a new value to the list, a LinkedListNode structure
must be created to hold the value. Should this structure be kept on the stack or on the heap?
Why?

**Record your answer here:**

De linkedListNode structure zal moeten worden opgeslagen in de de heap.
De heap memory is er namelijk voor om objecten, zoals de structures van de nodes van de linked list, in op te slaan.

### Activity 4: Appending and prepending elements

Implement the two functions to append and prepend a new integer to the list, given by the following prototypes:

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

    if(*pList->pHead->pNext == NULL){
        pList->pTail->pPrevious = NULL;
        return;
    }
}

void linkedlist_prepend(LinkedList *pList, int value) {

}

**Record your answer here:**

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

**Record your answer here:**

void linkedlist_print(const LinkedList *pList)
 {
 LinkedListNode *pCurrent = list->pHead;
 printf("[");
 if (pCurrent != NULL)
 {
/* TODO: 1. print the value stored in the node referred to
8 by pCurrent.
9 2. make pCurrent refer to the next node. */

 while (pCurrent != NULL)
 {
/* TODO: 1. print a comma, followed by the value stored
14 in the node referred to by pCurrent
15 2. make pNode refer to the next node */
 }
 }
 printf("]\n");
 }

### Activity 6: Element retrieval

**Record your answer here:**

### Activity 7: The const keyword

**Record your answer here:**

De const kan handig zijn als je van te voren al weet dat de waarde van hetgene dat je initialiseerd, niet zal veranderen, mits er met pointer wordt gewerkt want dan kan het wel.

### Activity 8: Time complexity of retrieval

**Record your answer here:**

### Activity 9: Implementing insertion

**Record your answer here:**

### Activity 10: Linked lists and memory management

**Record your answer here:**

Het geheugen dat is gereserveerd per node zal, tijdens het verwijderen van de node zelf, ook verwijderd moeten worden om te zorgen dat het gereserveerde geuheugen gelijk blijft aan de hoeveelheid nodes die de lijst bezit.

### Activity 11: Implementation of removal

**Record your answer here:**

### Activity 12: Implementing merge

**Record your answer here:**

### Activity 13: Time complexity of merge

**Record your answer here:**

Hoe langer de lijsten worden, hoe meer tijd nodig is om beide lijsten samen te voegen omdat alle items die in de lijsten staan moeten worden verwerkt.

### Activity 14: Implementing sorted insert

**Record your answer here:**

### Activity 15: Time complexity of sorted insert

**Record your answer here:**

Het plaatsen van een item in een linked list duurt langer omdat de pointers de hele lijst door moeten configureren voordat het item op de juiste plek kan komen te staan. Bij een array is dit niet het geval, hier kan een item er simpelweg gewoon tussen gezet worden.

## Look back

### What we've learnt

Fill in...
De verschillen tussen een array en een linked list
de uses voor een linked list

### What were the surprises

Fill in...

### What problems we've encountered

Fill in...
Activity 4: Het doorverwijzen naar de LinkedListNode

### 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?