C dynamic data structures (1)

Originally published on Medium

I used C over ten years ago when i started programming but moved to other languages very fast — now I am back on C.

Self-Referencing structures

A structure cannot contain instances of itself but it can contain pointers to instances of itself, see:

struct Wolf {
    int id;
    char name[32];
    struct Wolf *next;
};

This struct is called a self-referencing structure, which contains a member of pointer to an instance of itself. To implement dynamic data structes like a Singly Linked List I will use self-referencing structures.

Example: Self-Referencing structrues

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

struct Wolf {
    int id;
    char name[32];
    struct Wolf *next;
};

struct Wolf *AddWolf(int id, char *name){
    struct Wolf *wolf;
    wolf = (struct Wolf *)malloc(sizeof(struct Wolf));
    wolf->id = id;             /*set id*/
    strcpy(wolf->name, name);  /*set name*/
    wolf->next = NULL;         /*set next, point to NULL*/
    return wolf;
}

int main(){
    struct Wolf *alpha, *node;
    alpha = AddWolf(1, "Balto");
    alpha->next = AddWolf(2, "Steele");
    alpha->next->next = AddWolf(3, "Boris"); 
                  /*i know - boris isn't a dog/husky/wolf :) */
    node = alpha; /*point to alpha*/

    while(node != NULL){/*process all nodes*/
        printf("id = %d\n", node->id);
        printf("name = %s\n", node->name);
        node = node->next;
    }

    while(alpha != NULL){ /*memory handling*/
        node = alpha;
        alpha = node->next;
        free(node);
    }
    return 0;
}

The output of this self-ref struct example is:

id = 1
name = Balto
id = 2
name = Steele
id = 3
name = Boris

The null pointer wolf->next = NULL; is used as a flag value to get the end of a list. The first while loop uses the node variable to obtain a node of the linked list. The value NULL of the member next of the last node is used to stop the iteration of the loop.

Singly Linked List

As illustrated before, a linked list consists of nodes. Proximate nodes are linked to each other. Lets write a library of functions to process linked lists with following linked list functions:

create a node manage memory prepend, append, insert, find and remove a node clear the list I finished the implementation of the list but descriptions are missing. I will add them in a few days. Piece by piece.

list.h

/*list.h*/
#ifndef LIST_LIST_H
#define LIST_LIST_H

struct ListNode{
    int id;
    char *name;
    struct ListNode *next;
};

typedef struct ListNode *Node;

extern Node CreateNode(int id, const char *name);
extern void FreeNode(Node node);
extern void Prepend(Node *head, Node node);
extern void Append(Node *head, Node node);
extern int Insert(Node *head, Node node, int pos);
extern Node Find(Node head, int id, const char *name);
extern void Remove(Node *head, Node node);
extern void Print(Node node);
extern void PrintList(Node head);
extern void Clear(Node head);

#ifdef _CH_
#pragma importf <list.c>
#endif

#endif //LIST_LIST_H

Implementation

CreateNode

The function CreateNode is used to create a list element-a node. The memory of a node is dynamically allocated using malloc.

Node CreateNode(int id, const char *name){
    Node node;
    node = (Node) malloc(sizeof(struct ListNode));
    if(node == NULL){
        fprintf(stderr, "Error: not enough memory.\n");
        return NULL;
    }
    node->id = id;
    node->name = strdup(name);
    node->next = NULL;
    return node;
}

FreeNode

This function is used to free the memory used by a node which was created with CreateNode before. It frees the allocated memory for name and the node itself.

void FreeNode(Node node){
    if(node){
        if(node->name){
            free(node->name);
        }
        free(node);
    }
}

Prepend

The prepend function adds a element to the beginning of a list.

void Prepend(Node *head, Node node){
    node->next = *head;
    *head = node;
}

Append

Append can also be used to add an element to a list. The difference between append and prepend is that append adds the element at the end of the list rather than the beginning. This is the normal add function you may know from C#, Java or other languages.

void Append(Node *head, Node node){
    Node tmp = *head;
    if(*head == NULL) { /*no node (empty)*/
        *head = node;
    }else{
        while(tmp->next){
            tmp = tmp->next;
        }
        tmp->next = node;
    }
}

Insert

In my opinion the insert function is one of the most complicated operations to perform on a linked list. Before you can insert, you have to search for the place where the new node will be added and manipulating the next pointers so the link is not broken. Inserting at the first position is handled first, this is the easy part. If the insertion point is elsewhere, insert() performs a search to check where the new element should be inserted using the while-loop. If an insertion point is found, the link (next-pointer) needs to directed to the appropriate node. The other link that originally pointed to this node must be detached and attached to the new element. The new node is the next element of node tmp. If everythink worked fine, the function returns 0, otherwise -1.

int Insert(Node *head, Node node, int pos){
    int i = 0;
    /*tmp is the head*/
    Node tmp = *head;

    /*insert at the beginning of the list*/
    if(pos == 1){
        *head = node;
        (*head)->next = tmp;
        return 0;
    }
    /*get position*/
    while(tmp){
        /*invalid or matching position*/
        if(++i >= pos-1){
            break;
        }
        tmp = tmp->next;
    }
    if(i != pos-1){
        fprintf(stderr, "Error: can not insert at pos %d", pos);
        return -1;
    }
    /*update all links*/
    node->next = tmp->next;
    tmp->next = node;
    return 0;
}

Find

Node Find(Node head, int id, const char *name){
    while(head != NULL && /*reached last element*/
            !(head->id == id &&
                    !strcmp(head->name, name))){
        head = head->next;
    }
    /*found it: return it*/
    return head;
}

Remove

void Remove(Node *head, Node node){
    Node tmp = *head;

    /*handle empty list*/
    if(*head == NULL){
        return;
    } else if (*head == node) {
        *head = (*head)->next;
        /*give memory back to its owner (free)*/
        FreeNode(node);
    } else {
        while(tmp->next){
            /*we found the node*/
            if(tmp->next == node){
                /*unlink it*/
                tmp->next = tmp->next->next;
                /*give memory back*/
                FreeNode(node);
                return;
            }
            tmp = tmp->next;
        }
    }
}

Clear

void Clear(Node head){
    Node node;

    while(head){
        node = head;
        head = head->next;
        FreeNode(node);
    }
}

Printing

void Print(Node node){
    if(node){
        printf("id = %d, name = %s\n", node->id, node->name);
    }
}

void PrintList(Node head){
    while(head){
        Print(head);
        head = head->next;
    }
}

main.c — the final demo program

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

int main() {
    Node head, node;

    Node n1 = CreateNode(1, "A"),
         n2 = CreateNode(2, "B"),
         n3 = CreateNode(3, "C"),
         n4 = CreateNode(4, "D");

    head = NULL;
    Prepend(&head, n1);
    printf("List with one element: \n");
    PrintList(head);
    Prepend(&head, n2);
    printf("List with two elements: \n");
    PrintList(head);
    Append(&head, n3);
    printf("List with three elements: \n");
    PrintList(head);
    Insert(&head, n4, 2);
    printf("List with four elements: \n");
    PrintList(head);

    node = Find(head, 1, "A");
    Remove(&head, node);
    printf("List without A\n");
    PrintList(head);
    Clear(head);

    return 0;
}

output:

List with one element:
id = 1, name = A
List with two elements:
id = 2, name = B
id = 1, name = A
List with three elements:
id = 2, name = B
id = 1, name = A
id = 3, name = C
List with four elements:
id = 2, name = B
id = 4, name = D
id = 1, name = A
id = 3, name = C
List without A
id = 2, name = B
id = 4, name = D
id = 3, name = C
The next topic will be the implementation of a doubly linked list. You may ask why, but why not?

C dynamic data structures