Understanding and implementing a singly linked list in C.

This lesson is taught using the C programmming language, and thus expects some comfort level with foundational concepts like pointers, structs, arrays, memory allocation, etc.

What is a linked list?

A linked list is a meta data-structure consisting of a sequence of structures connected by references. A linked list has the following properties:

Nodes - This represents a structure which holds some data including a next property which is a pointer to the next node, or NULL.
Edges - This represents the link between two or more nodes through references.
Head - This represents the linked list itself. It is a pointer to the first node of the linked list.

The foundational data structure in most programming languages is an Array. It is very efficient in most cases, and behaves predictably. However, programs often require behaviour which either cannot be implemented using an array, or would be somewhat inefficient if done.

Some of the advantages of a linked list over the traditional array are:

It provides flexibility by allowing us to link together chunks of memory from any source (heap, stack, etc), whereas a traditional array can only store data in contiguous memory locations (next to each other in memory).
It allows us to link different types of data. A traditional array can only store homogenous data. e.g An array of numbers, an array of chars, etc.
The amount of memory used by a linked list scales linearly with the amount of elements added to it. An array however, pre-allocates a fixed size for it's elements thus making it difficult to resize/shrink the array if more/fewer elements are inserted by the program.
A linked list allows easy and fast insertion and deletion of elements at any position in the list without needing to shift elements around; we just adjust the links.. easy-peasy.

That all sounds great, but those awesome advantages come at a cost.

Linked lists use a lot more memory than an array. This is because each node of a linked list stores not only the data, but also a pointer to the next node. That is an extra 8 bytes (on 64-bit machines) of memory for every node in the list!

This overhead can be significant or negligible depending on many factors, and in most cases is a good trade-off for the flexibility the linked list provides.

Implementing a linked list

The first thing we need when implementing a linked-list is to define the structure of our nodes. In C, this is done by defining a struct with members including the next pointer to the next node or NULL, and one or more data properties.

In the code below, we define a struct that holds a string str, the length of the string len, and a pointer to the next node next.

/**
 * struct list_s - singly linked list
 * @str: string - (malloc'ed string)
 * @len: length of the string
 * @next: points to the next node
 *
 * Description: singly linked list node structure
 */
typedef struct list_s
{
    char *str;
    unsigned int len;
    struct list_s *next;
} list_t;

Next, let's write a function that creates a new node, and returns a pointer to the newly created node.

/**
 * create_node - Create a new node
 * @str: string - string literal to add to new node
 *
 * Return: Pointer to a new node, (NULL) if error.
 */
list_t *create_node(char *str)
{
    list_t *new_node = malloc(sizeof(list_t));

    if (new_node == NULL)
        return (NULL);
    
    new_node->str = strdup(str);
    new_node->len = strlen(str);
    new_node->next = NULL;

    return (new_node);
}

Now, let's write a function that adds a new node to the beginning of a linked list.

Notice that the function accepts the linked list as a double pointer to the head of the list. This allows us to update the variable holding the address to the head of the linked list, to now hold the address of the new node who's next value now points to the former head of the linked list.

/**
 * add_node - Add a new node to the head of a linked list.
 * @head: pointer to a pointer to a linked list.
 * @str: string - string literal to add to new node
 *
 * Return: Pointer to the new node, (NULL) if error.
 */
list_t *add_node(list_t **head, char *str)
{
    list_t *new_node;

    new_node = create_node(str);

    if (new_node == NULL)
        return (NULL);

    if (*head != NULL)
        new_node->next = *head;
    
    *head = new_node;

    return (new_node);
}

Some helper functions to print and free a linked list.

When freeing a linked list, it is important to declare a variable that holds a reference to the next node of the linked list before the current node is freed, otherwise our program would end up having a ton of leaked memory.

Use valgrind to inspect the memory usage of your program.

/**
 * print_llist - Print all elements of a linked list.
 * @head: pointer to a linked list.
 *
 */
void print_llist(list_t *head)
{
    while (head)
    {
        printf("[%d] %s\n", head->len, head->str);
        head = head->next;
    }
}

/**
 * free_llist - Free all memory used by a linked list.
 * @head: pointer to a linked list.
 *
 */
void free_llist(list_t *head)
{
    list_t *tmp;

    while (head)
    {
        tmp = head->next;
        free(head->str);
        free(head);
        head = tmp;
    }
}

Finally bringing everything together to create a linked list, print its elements, and free it when done.

int main(void)
{
    list_t *head;

    add_node(&head, "Greek Freak");
    add_node(&head, "Chef Curry");
    add_node(&head, "The Beard");
    add_node(&head, "Ice Trey");
    add_node(&head, "Kai");
    add_node(&head, "Dame Time");
    add_node(&head, "PG 13");
    add_node(&head, "Le Goat");

    print_llist(head);
    free_llist(head);

    head = NULL;
}

This was a very simple implementation, and there are many more interesting operations that can be baked into a linked list, but this should help a beginner get their feet wet.

Linked lists are a very important data structure, and understanding them strenghtens your handle on more abstract data structures found in high-level languages like Java, Python, JavaScript, etc.

Hope you learnt something, and thanks for reading!

What is a linked list?

Benefits of a linked list

Implementing a linked list