# 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 %}


---

# Agent Instructions: Querying This Documentation

If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.

Perform an HTTP GET request on the current page URL with the `ask` query parameter:

```
GET https://wiki.tylerqwong.me/cs/linked-lists.md?ask=<question>
```

The question should be specific, self-contained, and written in natural language.
The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.

Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.