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.

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;

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.

Double and Circle Linkage

A linked list can be doubly and circly linked at the same time!