Here, the linear order is specified using pointers. Each node is separated into two different parts:

• The first part holds the information of the element or node
• The second piece contains the address of the next node (link / next-pointer field) in this structure list.

Singly-Linked List

The following code helps to implement a basic singly linked list quickly. It defines the functions:

• create: create a new list. Takes an array of nodes values as a parameter.
• insert: add a node to the list. Takes as parameters: the list to update (head pointer), and the new node's value
• destroy: delete the list. Takes as parameter: the list to be deleted (head pointer)
• search: check if a value exists in the list or not. Returns a boolean. Takes as parameters: the list to search into (head pointer) and the value to be searched

We also used a print function to display the result of the program in the console. This function and the calls to it can be removed.

To remove a node, simply-linked list is not adapted: use a doubly-linked list instead (see next part of this post).

#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>
#include <string.h>

// Define data structure

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

// Define methods

node* create(int nodes);
node* insert(node* list, int value);
void destroy(node* list);
bool search(node* list, int needle);
void print(char* title, node *list);

// Process
int main()
{
    // create
    node *list = create(5); // *list points to the head of the list
    list = insert(list, 12);
    search(list, 12);
    destroy(list);
    return 0;
}

// Methods

/*
 * Create a linked list
 */
node* create(int nodes)
{
    node *p, *head, *prev;
    head = NULL;
    for (int i = 0; i < nodes; i++)
    {
        p = malloc(sizeof(struct node));
        p->value = i;
        p->next = NULL;
        if(head == NULL)
        {
            head = p;
        }
        else
        {
            prev->next = p;
        }
        prev = p;
    }
    print("create", head);
	return head;
}

/*
 * Insert a new node into the linked list
 */
node* insert(node* list, int value)
{
    node *head, *new;
    head = list;
    // Dynamically allocate space for a new node
	node *p = malloc(sizeof(struct node));
    // Check to mack sure we didn't run out of memory (using malloc)
    if (p == NULL)
    {
        free(p);
        return head;
    }
    // Populate and insert the node **at the beginning of the linked list**
    new = p;
    new->value = value;
    new->next = head;
    // Return a pointer to the new head of the linked list
    print("insert", new);
    return new;
}

/*
 * Delete an entire linked list
 */
void destroy(node* list)
{
    node *current, *next;
    current = list;
    // If you've reached a null pointer, stop
    while (current != NULL)
    {
        // Delete **the rest of the list** (recursive method)
        next = current->next;
        free(current);
        current = next;
    }
    // Free the current node
    list = NULL;
    print("destroy", list);
}

// Utilities

/*
 * Search through a linked list to find an element
 */
bool search(node* list, int needle)
{
    // Create a traversal pointer pointing to the list's head
    node *current = list;

    printf("-> Applying function search() ...\n\n");
	while (current != NULL)
    {
        // If the current node's `val` field is what we're looking for, report success
        if (current->value == needle)
        {
            printf("The value %i exists in the list.\n\n", needle);
            return true;
        }
        // If not, set the transversal pointer to the next pointer in the list and loop over
        current = current->next;
    }
    // If you've reached the end of the list (pointer is NULL), report failure
    printf("The value %i does not exist in the list.\n\n", needle);
    return false;

}

void print(char* title, node *list)
{
    node *current = list;
    if(strlen(title) > 0)
    {
        printf("-> Applying function %s() ...\n\n", title);
    }
    // Check if the list exists
    if (list == NULL)
    {
        printf("The list does not exist!\n\n");
        return;
    }
    // If it exists, print the list's details
    int i = 0;
    printf("nodes:\n");
    while(current != NULL)
    {
        printf("%i: { ", i);
        printf("value: %i, next: %p }", current->value, current->next);
        if (i == 0)
        {
            printf(" [head: %p] ", current);
        }
        printf("\n");
        current = current->next;
        i++;
    }
    printf("\n");
}

Doubly-Linked List

The doubly-link list adds a prev variable to the node structure. This allows to remove easily a node from the list.

The following code makes some updates to the previous code (simply-linked list):

• the typedef declaration,
• the create and insert functions

And it adds the following function:

• delete: remove a node from the list based on its value. It takes as parameters:  the list pointer (head) and the value of the node to be remove. It returns the updated list. 

#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>
#include <string.h>

// Define data structure

typedef struct node
{
	int value;
	struct node* prev;
	struct node* next;
}
node;

// Methods declaration

node* create(int nodes);
node* insert(node* list, int value);
node* delete(node* list, int value);
void destroy(node* list);
bool search(node* list, int value);
void print(char* title, node *list);

// Process
int main()
{
    node *list = create(5); // *list points to the head of the list
    list = insert(list, 12);
    list = delete(list, 2);
    destroy(list);
    return 0;
}

// Methods

/*
 * Create a linked list
 */
node* create(int nodes)
{
    node *p, *head, *prev;
    head = NULL;
    for (int i = 0; i < nodes; i++)
    {
        p = malloc(sizeof(struct node));
        p->value = i;
        p->next = NULL;
        p->prev = NULL;
        if(head == NULL)
        {
            head = p;
        }
        else
        {
        	p->prev = prev;
            prev->next = p;
        }
        prev = p;
    }
    print("create", head);
	return head;
}

/*
 * Insert a new node into the linked list
 */
node* insert(node* list, int value)
{
    node *head, *new;
    head = list;
    // Dynamically allocate space for a new node
	node *p = malloc(sizeof(struct node));
    // Check to mack sure we didn't run out of memory (using malloc)
    if (p == NULL)
    {
        free(p);
        return head;
    }
    // Populate and insert the node **at the beginning of the linked list**
    new = p;
    new->value = value;
    new->prev = NULL;
    new->next = head;
    // Fix the `prev` pointer of the old head of the linked list
    head->prev = new;
    // Return a pointer to the new head of the linked list
    print("insert", new);
    return new;
}

/*
 * Delete a node inside the list
 */
node* delete(node* list, int value)
{
    node *current, *prev, *next;
	// Create a traversal pointer pointing to the list's head
    current = list;

    // Check that the value exists in the list
    if(!search(list, value))
    {
        return list;
    }
	while (current != NULL)
    {
        // If the current node's `val` field is what we're looking for, delete it from the list
        if (current->value == value)
        {
            current->prev->next = current->next; // link prev->next to current->next
            current->next->prev = current->prev; // link next->prev to current->prev
            free(current); // remove current node
            break;
        }
        // If not, set the transversal pointer to the next pointer in the list and loop over
        current = current->next;
    }
    // print and return the updated list
    print("delete", list);
    return list;
}

/*
 * Delete an entire linked list (same as for simply-linked list)
 */
void destroy(node* list)
{
    node *current, *next;
    current = list;
    // If you've reached a null pointer, stop
    while (current != NULL)
    {
        // Delete **the rest of the list** (recursive method)
        next = current->next;
        free(current);
        current = next;
    }
    // Free the current node
    list = NULL;
    print("destroy", list);
}

// Utilities

/*
 * Search through a linked list to find an element (same as for simply-linked list)
 */
bool search(node* list, int value)
{
    // Create a traversal pointer pointing to the list's head
    node *current = list;

    printf("-> Applying function search() ...\n\n");
	while (current != NULL)
    {
        // If the current node's `val` field is what we're looking for, report success
        if (current->value == value)
        {
            printf("The value %i exists in the list.\n\n", value);
            return true;
        }
        // If not, set the transversal pointer to the next pointer in the list and loop over
        current = current->next;
    }
    // If you've reached the end of the list (pointer is NULL), report failure
    printf("The value %i does not exist in the list.\n\n", value);
    return false;
}

void print(char* title, node *list)
{
    node *current = list;
    if(strlen(title) > 0)
    {
        printf("-> Applying function %s() ...\n\n", title);
    }
    // Check if the list exists
    if (list == NULL)
    {
        printf("The list does not exist!\n\n");
        return;
    }
    // If it exists, print the list's details
    int i = 0;
    printf("nodes:\n");
    while(current != NULL)
    {
        printf("%i: { ", i);
        printf("value: %i, prev: %p, next: %p }", current->value, current->prev, current->next);
        if (i == 0)
        {
            printf(" [head: %p] ", current);
        }
        printf("\n");
        current = current->next;
        i++;
    }
    printf("\n");
}