(linked-list)=
# Linked list

In previous weeks we discussed about:
- the superpower of `struct`'s before in section {ref}`self-referential-struct`, where we built an infinite string.
- {ref}`static-and-stack-based-memory`
  - we will introduce *heap*-based memory

## Definition

:::{wpd} linked list
a linear collection of data elements whose order is not given by their physical placement in memory.
:::

:::::{grid} 2
::::{grid-item-card} (singly) linked list 
:::{commons-figure} https://commons.wikimedia.org/wiki/File:Singly-linked-list.svg
:align: right
A linked list. Each node contains data (e.g., 12) and a pointer to the next node. `☒` stands for `nullptr`.
:::
::::
::::{grid-item-card} doubly linked list
:::{commons-figure} https://commons.wikimedia.org/wiki/File:Doubly-linked-list.svg
Doubly linked list
:::
::::
:::::

:::{activity} Implementing a singly linked list
:label: implementing-a-singly-linked-list
Implement a linked list similar . Milestones:
1. Create a struct that contains an integer and a self-reference.
1. Create an example list like in {ref}`self-referential-struct`, navigate through the list and print the elements.
1. Declare a pointer called `head`, which will point to the first element.
1. Implement a function `insert(*list, index, *node)` that inserts the node `node` at the location `index` in the list `*list`.
:::

:::{activity} Appropriate data structure for FrankenText
:label: appropriate-data-structure-for-frankentext
In {ref}`frankentext` we used many arrays.
1. Write down arrays and their sizes. A pointer and `size_t` have 8 byte each. 

   <!--
   Tip: A drawing which depicts how they related to each other could be helpful.
   -->
1. How do these sizes affect the performance of our program or even other programs?
1. How could we reduce the memory used by our program?

   ```{dropdown} Hint
   - Could {ref}`sequential-io` help?
   ```
:::

## Array vs linked list

:::{commons-figure} https://commons.wikimedia.org/wiki/File:List_VS_linked_list.png
:name: array-vs-linked-list
:figwidth: 60%
:align: right
Visualization of appending the letter `W` to an array (names as `list` above) and linked list.
:::
Array elements are always in sequence and its space cannot be changed after declaration. See {numref}`array-vs-linked-list`. 

1. Above (list): If we wanted to add additional data and array did not have reserved space for additional data, we would need to allocate a larger space and copy the original array and the new data into the larger space

2. Below (linked list): In contrast, we don't have to copy the original data, but (1) allocate new space for the new data and (2) connect the new data to the original data.

## Insert operation on a linked list

:::{commons-figure} https://commons.wikimedia.org/wiki/File:Doubly_linked_list_insert_after.svg
:figwidth: 60%
:align: right
`newNode` is inserted after node `A` in a double linked list.
:::

For modification, we need the following steps:
1. Find the node we want to insert the element after.
1. Allocate new space for `newNode` using `malloc` on the heap memory
1. Link `newNode` with the neighboring nodes


## Heap-based memory

```c
typedef struct S S;

S *f1() {
   S s;
  // stack-based memory 
  // Released after the function returns.
  //...
  return &s;  // ❌ will be overwritten by other functions
}

S *f2() {
    S *sp = malloc(sizeof(S));
    // heap-based memory
    // Persists after the function returns.
    //...
    return sp;
}
auto sp = f2();
//...
free(sp);
// Deallocates sp.
// In other words, gives the memory area free for other users.
```

<!--
TODO activity
-->