# HL Topic 5 Linked lists

:::info
HL students need to study linked lists but they don't have to implement them using pseudocode (yay)
:::

For this is helpful to have clear the concept of *reference* or *pointer* that we explained in paper 2. I explained it [here](https://hackmd.io/zfx3YkE9QD6-lnNz42kkbQ#Reference-types)

## What is a linked list.

Is a linear (elements go one after the other) data structure where each element has a link to the next.

Usually we have a special pointer to the head.

### Recommended Summary video

https://www.youtube.com/watch?v=njTh_OwMljA

{%youtube njTh_OwMljA%}

Linked lists are linear structures that can vary in size (something that the arrays cannot do) and they consist in elements that have a payload of data (integers, characters, Strings, objects) and a link to the next element.

The good thing about this is that we can make a bigger linked list or a smaller linked list just with the size that we need at any given time.

Why _then_ not use it for everything? Why do we care about Arrays then? Because accessing data can be a little bit more trickier.

As we have seen in stacks and queues, accessing the first or the last element of those is pretty fast foward but digging up it takes more time.

In this case if we have a linked list of elements we usually start with the first element and then we go through the elements until we reach the one that we're looking for or the index that we need.

Let's do an example in pseudocode (even if it's not asked) as if were a collection to find the 4th element

:::warning
Even if I'm using the collections as if they were linked lists, don't generalize that much. Please beware.
:::

LINKED_LIST //linked list
// Find the 4th element4
LINKED_LIST.resetNext()
loop C from 1 to 3
    LINKED_LIST.getNext()
    //this goes 3 times
end loop
    output LINKED_LIST.getNext()
    //this was the 4th element

Or if we're using to see if we have a specific value

LINKED_LIST //linked list
DATA // the value that we're looking fore
FOUND = false // boolean that is false if we haven't found the result
LINKED_LIST.resetNext()
loop while LINKED_LIST.hasNext()
    if LINKED_LIST.getNext() == DATA then
        FOUND = true
        break
    end if
end loop
if FOUND then
    output "We have found the data in the linked list"
else
    output "The data is not in the linked list"
end if

That is linear in the size of the Linked list so in the big O notation this is $O(n)$ where the access to the data in an array is $O(1)$.

## Lexicon of linked lists:

* *Node*. Each of the elements of the linked list. It has the data (*payload*) and the link or links. (2 separated things)
* To *traverse* a linked list: To go through each element of the linked list, sometimes through all the elements, sometimes trough some elements of the linked lists.
* The node's *successor* is the next node that is pointing to.
* The node's *predecessor* is the previous node that is pointing to the current node.
* Pointer is an address of something in logic memory or phisical memory. Can be an address of the *payload* or can be the address of the next node (the node's successor).
* *Null pointer* is a special pointer that points to nothing. It doesn't have *pointee*. It can be represented with a diagonal line in the box that points at null
* *Append* is to insert at the end. For example if I append "to" to the string "apple" I'd have "appleto"
* *Prepend* is to insert at the beginning. For example, if I prepend "to" to the string "apple" I'd have "toapple"
* *Head* Is the first node of the linked list
* *Tail* is the last node of the linked list
* *Header* Is a special node that we're going to talk about.

## The head problem (header)

When administrating linked lists we know that we have nodes that link to each other but, how do we know where is the start? (something that can happen in circled linked list or when we delete the head of the linked list but we want to keep the rest)

So the idea is that we're going to have a header. A node with no data whatsoever but the link to the head of the linked list.

https://www.geeksforgeeks.org/header-linked-list-in-c/

## Types of linked lists

https://www.w3schools.com/dsa/dsa_data_linkedlists_types.php

### Single linked list

We have a single linked list were the element has the payload (data) and just one pointer to the next. The advantadge is that we're taking less memory so when the payload is small (like numbers or characters) this is usually the way to go.

_single linked list_

### Doubly linked list

We have doubly linked list (remember that is not spelled like dolby surround). In this kind of linked list the links go to the next element AND to the previous element. That is handy when we want to do operations of switching places but it takes more memory usage



### Circular single linked list

In this case when we arrive to the end of the linked list we have a pointer to the Head, the first element of the list.


Is a little bit harder to tell where do you have the "HEAD" or the "tail" of this kind of list, usually we have another pointer that tells you where the head is.

### Circular doubly linked list


The same as the circular single linked list but with twice the links.

## Compare linked list to arrays
(from here: https://www.w3schools.com/dsa/dsa_algo_linkedlists_operations.php)

These are some key linked list properties, compared to arrays:

* Linked lists are not allocated to a fixed size in memory like arrays are, so linked lists do not require to move the whole list into a larger memory space when the fixed memory space fills up, like arrays must.
* Linked list nodes are not laid out one right after the other in memory (contiguously), so linked list nodes do not have to be shifted up or down in memory when nodes are inserted or deleted.
* Linked list nodes require more memory to store one or more links to other nodes. Array elements do not require that much memory, because array elements do not contain links to other elements.
* Linked list operations are usually harder to program and require more lines than similar array operations, because programming languages have better built in support for arrays.
* We must traverse a linked list to find a node at a specific position, but with arrays we can access an element directly by writing myArray[5].

## Sketech linked list

The student should be able to draw diagrams about this:
* How to add data to a linked list

* Delete specified data item

* Modify the data held in the linked list

* Search for a given item.

### Empty linked list

It's trivial but this is one way to depict it.


One node that has a null pointer in the payload and a null pointer of the Next node.

### Adding an element in the linked list

We need to specify 4 steps
a. Find the node that we want to insert after
b. Create the new node
c. Copy the pointer from the node that is already in the list that points to the next element after the new one into the new node next.
d. Change the pointer in the node that preceeds the new one so it points to the new one.

We have 2 special cases, doing into the Head or the tail.

#### Inserting into the head (prepending)

In the case of the head we usually have a special value that we're going to enter into the linked list. So we have to

a) Create the new node.
b) Make the new node point to the old head
c) Change the special value that points to the head and make it point to the new head.

Example diagram (credit Y.C)


#### Inserting after the tail (appending)

For doing this we have to

a) traverse trough _all_ the linked list so we find the last element (this is the long step)
b) create the new node with a null pointer in the next.
c) make the old last element of the linked list point to the new last node.

Diagram example (credit Y.C.)


### Deleting a specific node

First we have to check which node do we want to delete (with a condition or counting the number of nodes). Then we have three cases. Deleting at the beginning, at the end or in the middle.

:::info
When we delete using this procedure we only have to take away the pointer. Usually we have other algorithms to take out the data that has no pointers to. These are called garbage collectors


:::

To delete in the middle of the linked list once we have the node that we want to delete, we make the predecessor node to the deleted node to link to the successor node of the deleted element (instead of the deleted element)

#### Delete the Head

If we want to delete the head, we need to change the link to the header to the next node after he header

Diagram example (credit Y.C.)

#### Delete the tail

If we want to delete the tail we have to set the pointer to the second last element to null.

Diagram example (Credit Y.C.)


### Modifying the data

To modify the payload of a node we have 3 approaches.
1) Delete the node and insert a new one
2) Change the pointer of the data of the node that we want to change
3) Change the data itself that the pointers of the pay load goes to.

### Searching data

We have to use linear search _even if it's sorted_ since there is no way to use binary search because we cannot have direct access to the elements. We need to traverse the linked list.

### Sorted linked lists

Having sorted linked lists means that the payloads are ordered by value (or one of their values). It's a little bit harder to implement (and cannot implement binary search) but is easier to maintain when we have to add or delete elements on that list.

### Other usesful reference

https://www.geeksforgeeks.org/data-structures/linked-list/