> For the complete documentation index, see [llms.txt](https://wiki.tylerqwong.me/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://wiki.tylerqwong.me/cs/linked-lists.md).

# Linked Lists

### Introduction

A linked list is a type of data structure made up of nodes:

```
typedef struct
{
    my_node* next = NULL;
    int data1 = 0;
    char data2 = 'x';
} my_node;
```

You usually use a linked list for memory management reasons. The main difference between linked lists and arrays is *dynamic memory allocation* and *memory overhead*. With a linked list you can malloc and dealloc data as needed but each item in the list takes up extra space because it needs to contain a pointer to the next value.

![](/files/-LzTqawa3rsH3kHBiOth)

### Anatomy

|              |                                                                                           |
| ------------ | ----------------------------------------------------------------------------------------- |
| Head Pointer | Mandatory pointer to the first value, if this is lost then the whole list is inaccessible |
| Head         | The firsty node in the list                                                               |
| Tail Pointer | Optional but very useful for appending items to the end of the list                       |
| Tail         | The last node in the list, tail->next must be a NULL pointer unless circly linked         |
| 'next' value | Mandatory struct member, my\_node\* type that points to next node                         |
| 'prev' value | Optional struct member, my\_node\* type that points to previous node                      |
| 'data' value | Madatory struct member, any type depending on data in question                            |

Common operations on a linked list: insertion to a particular position, removal of a particular item, search for a particular item, iteration through with some sort of processing.

### Node Creation, Insertion, and Removal Example

```
// A linked list of unkown size is passed to us through "headptr"

// Initializing a new node
my_node* new_node = (my_node*) malloc(sizeof(my_node));

// Node is populated with data
new_node->data = 100;

// Check that the second node exists
if( headptr->next == NULL )
{
    // If it doesnt exist we can just append the new node
    headptr->next = new_node;
}
else{
    // Otherwise we have to save the next value so it doesnt leak
    tempptr = headptr->next;
    headptr->next = new_node;
    // And then make the new 2nd node point to the node we saved
    new_node->next = tempptr;
}

// Then we traverse to the tail...
while( currptr->next != NULL ){
}

// ...and free that portion of heap
free(currptr);
currptr = NULL;
```

{% hint style="info" %}
If currptr is not set to NULL at the end of this sequence then it is a *dangling pointer* which points to garbage. This can cause tricky bugs and unpredictable behaviour.
{% endhint %}

### Double and Circle Linkage

![](/files/-LzTw6hfGSMWxGIGfJGr)

{% hint style="info" %}
A linked list can be doubly and circly linked at the same time!
{% endhint %}