C

How to implement list data structure from scratch ?

Linked List Data Structure Implementing Linked List data structure in C

Rohit Kumar

Rohit Kumar

— 2 min read
How to implement list data structure from scratch ?

List data structure brings the non-contiguous implementation of data, unlike array which is contiguous in nature. Usually, Array’s size is static in nature which will wastage of memory if it is not being used by the program. In the case of List, one can store the data in a node and the node will have a link to its next value.

The Node of a List
#ifndef  LISTNODE_H_
#define LISTNODE_H_

// Defining Node of List
typedef struct _list_node{
    int data;
    struct _list_node *next;
}list_node;

#endif //  LISTNODE_H_

list_node.h

The List
The below diagram represents a list where the head is the pointer that always points to the first node of the list and the last node’s next pointer is always null ptr or NULL.

Here each node show has two elements first part is data i.e integer value and the second part is the address of the next node. Below each node, there are 100, 200, 300, and 400. They are the addresses of the node.

linked list representation
#include <stdio.h>
#include <stdlib.h>
#include "list_node.h"

//Implementation of list operations 

//Insert new node at front. head will change after each insertion. 
void add_node(list_node** head, int data)
{
    list_node* new_node = malloc(sizeof(list_node));
    new_node->data = data;
    new_node->next = *head;
    *head = new_node;
}

//find the first occurance of the val in the list.
list_node* find_node(list_node* head, int val)
{
    for(list_node* ptrv = head; ptrv!=NULL; ptrv=ptrv->next)
    {
        if(ptrv->data == val)
        {
            return ptrv;
        }
    }
    return NULL;
}

//delete the node if val is found in the list.
void delete_node(list_node** head, int val)
{
    list_node* del_node = find_node(*head, val);

    if(del_node != NULL)
    {
        //if del_node is first node
        if(*head == del_node)
        {
            *head = del_node->next;
            free(del_node);
            del_node = NULL;
        }
        //if del_node is other than first.
        else
        {
            list_node* prev = *head;
            while(prev->next != del_node)
            {
                prev = prev->next;
            }

            prev->next = del_node->next;
            free(del_node);
            del_node = NULL;
        }
    }
}

void show_list(list_node* head)
{
    printf("\n");
    for(list_node* ptrv = head; ptrv!=NULL; ptrv=ptrv->next)
    {
        printf("[%d|%p]->",ptrv->data, ptrv->next);
    }
    printf("\n");
}

list_impl.c

#include <stdio.h>
#include "list_node.h"

void add_node(list_node** head, int data);
void delete_node(list_node** head, int val);
void show_list(list_node* head);

int main()
{
    list_node *head = NULL;
    add_node(&head, 21);
    add_node(&head, 23);
    add_node(&head, 34);
    add_node(&head, 12);
    add_node(&head, 56);

    show_list(head);

    delete_node(&head, 12);
    show_list(head);

    delete_node(&head, 21);
    show_list(head);

    delete_node(&head, 56);
    show_list(head);

    return 0;
}

main.c

Read more