Hello there,
I am currently learning C / C++, and decided to implement widely used data structures in C language, just for educational purposes.

Linked List is for today

In my implementation, Linked List consists of nodes with pointers to user data, linked together in one chain. The way it's linked is straightforward: each node, besides the pointer to user data, also contains pointer to the next node in the chain. For better understanding I drew simple Linked List scheme with type names I will use in implementation.

Linked List in C

Note, that instead of having void* pointer to user data in the node, you can have the actual value (int data). But in that case, your value is strictly typed, which means that you can use your Linked List with certain type only. I think, it's not flexible enough.

Comparable to array, linked list has it's pros and cons:

Advantages

  1. Linked List is a dynamic data structure. User is able to add new data to the list as long as program doesn't reach memory cap. In case with non-dynamic array - user is able to add only certain amount of elements to the array, constrained by amount of memory allocated for this array.

Disadvantages

  1. User can't access elements by index. To get to the certain element, algorithm has to iterate over all the elements. It's always linear O(n) complexity.

  2. Each new node with it's data is always dynamically allocated, which creates additional overhead.

  3. List has to keep additional pointers to the head and tail nodes, also each node contains two more pointers: to the data and to the next node. More pointers - higher complexity.

Implementation

At first, we need to describe header files for two custom structures in C:

  • s_node - list node.
  • s_linked_list - Linked List structure itself;

s_node.h:

typedef struct { void* data; struct s_node* next; } s_node;

Node structure contains two members:

  • void* data - pointer to user data, so we are not dependant of data type, and able to keep whatever we want in our linked list.
  • s_node* next - pointer to the next node to actually chain our List.

s_linked_list.h

#include <stddef.h>
#include <stdlib.h>
#include <stdio.h>
#include "s_node.h"

typedef struct { s_node *head; s_node *tail; int length; } s_linked_list;
s_linked_list* create_linked_list();

void llist_push(s_linked_list *list, void *data);
void llist_remove_node(s_linked_list *list, void *data);
void llist_remove_first(s_linked_list *list);
void llist_remove_last(s_linked_list *list);
int get_length(s_linked_list *list);

Linked List structure has three members:

  • s_node *head - pointer to the first node in the list.
  • s_node *tail - pointer to the last node in the list.
  • int length - amount of nodes added to the list (actual length).

Now, let's implement each function described in Linked List's header file.

s_linked_list.c

First function we need to have implemented is similar to a constructor in OOP languages. It allocates linked list structure in memory, initialises it and returns pointer to it, so we can use it in our programs.

#include "s_linked_list.h"

s_linked_list* create_linked_list()
{
    s_linked_list* list = 
malloc(sizeof(s_linked_list));
    list->head = NULL;
    list->tail = NULL;

    list->length = 0;

    printf("Empty list initialized");
    return list;
}

What we do here, is allocating memory for Linked List structure and initialising it's elements.

Second function is for pushing data to the list:

void llist_push(s_linked_list *list, void *data)
{
    s_node *new_item = malloc(sizeof(s_node));
new_item->data = data;
new_item->next = NULL;

    if (list->head == NULL)
    {
        list->head = new_item;
        printf("\n pushed to null  head");
    }

    else if (list->tail == NULL)
    {
        list->tail = new_item;
        list->head->next = new_item;
        printf("\n data  pushed to null tail");
    }

    else 
    {
        list->tail->next = new_item;
        list->tail = list->tail->next;
        list->tail->next = NULL;
        printf("\n data pushed to new tail");
    }

    list->length += 1;
    printf("\nList Length %d", list->length);
}

The overall mechanism behind this is simple: push data to list by adding new node, and manage pointers, so nodes do not lose references to next nodes, and list always has updated pointers to head and tail nodes.

We could describe the algorithm of this function in few steps:

  • allocate new node (*new_item) and initialise it's data pointer to user data pointer passed as argument;

  • if list is empty (head is null) we make head pointing to freshly created node.

  • if tail is empty (list->tail is NULL), make tail point to new node. Now data is pushed to tail. Don't forget to point head->next to new_item too. Now head points to tail.

  • if head and tail are not empty - push new item to the tail, and make list->tail->next point to NULL (it's a useful indication where list ends).

  • update list length at the end of operation.

By the way, it will be a wise thing to add is_list_empty() and check header node for content.

Ok, we can add data to the Linked List now. Moving forward, let's implement function, which removes data from list.

 void llist_remove_node(s_linked_list *list, void *data)
{
    if (list->head == NULL)
    {
        printf("This list is empty. Nothing to remove.");
        return;
    }

    if (data == list->head->data)
    {
        llist_remove_first(list);
        return;
    }

    else if (list->tail != NULL && data == list->tail->data)
    {
        llist_remove_last(list);
        return;
    }

    s_node *temp = list->head;
    s_node *prev = NULL;

    while(temp->next != NULL)
    {
        temp = temp->next;
        prev = temp;

        if (data == temp->data)
        {
            prev->next = temp->next; 
            free(temp->data);
            free(temp);    
             printf("\n Node containing queried data is removed.");
            return;
        }
    }
}

Let's decompose this function too:

  • if list is empty return from function

  • if head node keeps data which needs to be removed - remove first node from the list (head) and return from function. Implementation of removefirst() and removelast() goes below.

  • if tail node keeps data which needs to be removed - remove last node from the list (tail) and return from function.

  • if none of above is true - iterate over each node, comparing it's data with user data provided by argument. Deallocate (free) data itself and node containing it. Change previous node next pointer to the next of node we destroyed (if exists).

Moving forward, we obligated to describe removefirst() and removelast() functions.

void llist_remove_first(s_linked_list *list)
{
    if (list->head == NULL)
    {   
        printf("\n This list is empty. Nothing to remove.");
        return;
    }

    s_node *temp;
    temp = list->head;
    free(temp->data);
    free(temp);

    if(list->tail != NULL)
    {
        list->head = list->head->next;
    }

    else 
    {
        list->head = NULL;
    }

    list->length -= 1;
    printf("\n First element removed");
    printf("\nList Length %d", list->length);
}
  • if list is empty - return from function. I would also log notification to console in this case;
  • destroy head->data and head node itself.
  • move list head to the next node if next node exists. Otherwise, set head to NULL (initial state, which indicates that Linked List is empty).
  • decrement length by 1, as we destroyed one node.

remove_last() is a bit more complicated

 void llist_remove_last(s_linked_list *list)
{
    if (list->head == NULL)
    {   
        printf("\n This list is empty. Nothing to remove.");
        return;
    }

    if (list->tail == NULL)
    {
        printf("\n Removing HEAD");
        free(list->head->data);
        free(list->head);
        list->head = NULL;

        printf("\nHead Now Removed");

        list->length -= 1;
        printf("\nList Length %d", list->length);
    return;
}   

    s_node *prevTail = list->head;

    while(prevTail->next != list->tail)
    {
        prevTail = prevTail->next;
    }

    if (prevTail->next != NULL)
    {
        free(list->tail->data);
        free(list->tail);

        if (list->head != prevTail)
        {
            list->tail = prevTail;
            list->tail->next = NULL;
        }

        else 
        {
            list->tail = NULL;
        }

        list->length -= 1;
        printf("\n last element removed");
        printf("\nList Length %d", list->length);
    }

}
  • as usual, return from function if list is empty (list->head is NULL);

  • remove head node and it's data if tail is empty (list->tail is NULL). It indicates that last node is currently head. Set head to NULL after deallocating memory.

  • iterate over the all nodes in our Linked List until we come across tail node. Remember to keep reference to previous node before tail (prevTail). Destroy (deallocate memory) of tail data and tail node itself.

  • prevTail becomes list->tail in case if head doesn't point to prevTail too.

  • in other cases, our tail becomes NULL pointer, as only head node left before destroyed tail.

  • decrement length by 1 as we successfully removed one node from the chain.

Last and easiest function we need to describe is get_length (s_linked_list *list) which takes pointer to our list as an argument and returns it's length.

int get_length(s_linked_list *list)
{
    return list->length;
}

That's pretty much it. Must have functionality for custom made Linked List. I uploaded source code to github with some demo usage of our newly created data structure: https://github.com/pan1cmode/dataStructuresInC/tree/master/LinkedList