Linked List

Introduction to linked list.

A linked list is a data structure that looks a lot like a regular list, except that it's a sequence of nodes. Each node comprises of two parts: data field and data reference. The latter is what defines nodes in a linked list as they're needed to point to the next node in the sequence. Without the data reference, the elements of a linked list wouldn't be bound at all; they'd be only loose entities without any connecting feature to relate them. A head pointer is used to track the first element in the linked list, always pointing to it.

The linked list data structure is tops for insertion or removal at any position in the list. However finding elements according to some specified criterium is made more difficult when compared to other compound data structures such as arrays and lists because it requires going through the whole list in order to find the desired item.

We can model a node of the linked list using a structure as follows:

typedef struct node{
    int data;
    struct node* next;
}

It should be noted that a linked list element is basically a struct, an object-esque entity in C which shares some similarities with a bona fide object from OO programming. For instance, a struct can store other values using common data types such as ints and chars, which can be referred to later on down the project.  Also, notice how data stores information while the next pointer holds the address of the next node.


First we declare a head pointer that always points to the first node of the list.

To add a node at the beginning of list we need to create a new node. We will need to create a new node each time we want to insert a new node into the list so we can develop a function that creates a new node and return it.

node* create(int data,node* next)
{
    node* new_node = (node*)malloc(sizeof(node));
    if(new_node == NULL)
    {
        printf("Error creating a new node.\n");
        exit(0);
    }
    new_node->data = data;
    new_node->next = next;

    return new_node;
}

Then we need to point the next pointer of the new node to the head pointer and point the head pointer to the new node.

node* prepend(node* head,int data)
{
    node* new_node = create(data,head);
    head = new_node;
    return head;
}

TRaversing the linked list

To traverse the linked list, we start from node 1, and move to the next node until we reach a NULL pointer.


typedef void (*callback)(node* data);
The following is the traverse() function:

void traverse(node* head,callback f)
{
    node* cursor = head;
    while(cursor != NULL)
    {
        f(cursor);
        cursor = cursor->next;
    }
}