Tag Archives: Linked List

Singly-linked list in C

A singly-linked list is a simple data structure in which each node has a pointer to the next node in the list. The main difference with a doubly-linked list is that to insert before a node, or remove a node, you need to have found the previous node as well, so that you can change its next pointer. This means that when iterating over the list to perform these modifications you need to keep track of a previous node shadowing the current one as follows:

snode *current, *previous = NULL;
for (current = list->head; current != NULL; current = current->next) {
    /* Modify current, using previous where necessary */
    previous = current;
}

Here is the header file:

#ifndef SLIST_H
#define SLIST_H

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

struct slist {
	snode * head;
	snode * tail;
	unsigned int count;
};
typedef struct slist slist;

typedef void (*slist_forfn)(void *);

slist * slist_create(void);
void slist_empty(slist * list);
void slist_delete(slist * list);
void slist_add_tail(slist * list, void * data);
void slist_add_head(slist * list, void * data);
void * slist_remove_head(slist * list);
void * slist_remove_tail(slist * list);
void * slist_remove(slist *list, snode *node, snode *previous);
void slist_insert_before(slist * list, snode * node, snode * previous, void * data);
snode * slist_insert_after(slist * list, snode * node, void * data);
void slist_for_each(const slist * list, slist_forfn fun);
unsigned int slist_get_count(const slist * list);

#endif /* SLIST_H */

The implemention:

#include <stdlib.h>

#include <slist.h>

static snode * snode_create(void * data)
{
	snode * node = malloc(sizeof(snode));
	if (node) {
		node->data = data;
		node->next = NULL;
	}

	return node;
}

slist * slist_create(void)
{
	slist * list = malloc(sizeof(slist));
	if (list) {
		list->head = NULL;
		list->tail = NULL;
		list->count = 0;
	}

	return list;
}

void slist_empty(slist * list)
{
	snode * node, * temp;
	node = list->head;
	while (node != NULL) {
		temp = node->next;
		free(node);
		node = temp;
	}
}

void slist_delete(slist * list)
{
	if (list) {
		slist_empty(list);
		free(list);
	}
}

void slist_add_tail(slist * list, void * data)
{
	snode * node = snode_create(data);
	if (list->head == NULL) {
		/* Adding the first node */
		list->head = node;
		list->tail = node;
	}
	else {
		list->tail->next = node;
		list->tail = node;
	}
	list->count++;
}

void slist_add_head(slist * list, void * data)
{
	snode * node = snode_create(data);
	if (list->tail == NULL) {
		/* Adding the first node */
		list->head = node;
		list->tail = node;
	}
	else {
		node->next = list->head;
		list->head = node;
	}
	list->count++;
}

void * slist_remove_head(slist * list)
{
	void *data = NULL;

	if (list->head) {
		snode *temp = list->head;
		if (list->head->next) {
			list->head = list->head->next;
		}
		else {
			/* List is now empty */
			list->head = NULL;
			list->tail = NULL;
		}
		data = temp->data;
		free(temp);
		list->count--;
		if (list->count == 1) {
			list->tail = list->head;
		}
	}
	
	return data;
}

void * slist_remove_tail(slist * list)
{
	void *data = NULL;

	if (list->tail) {
		snode *current, *previous = NULL;
		current = list->head;
		while (current->next) {
			previous = current;
			current = current->next;
		}
		data = current->data;
		free(current);
		if (previous) {
			previous->next = NULL;
		}
		else {
			/* List is now empty */
			list->head = NULL;
			list->tail = NULL;
		}
		list->count--;
		if (list->count == 1) {
			list->head = list->tail;
		}
	}

	return data;
}

void * slist_remove(slist *list, snode *node, snode *previous)
{
	void *data;
	if (node == list->head) {
		data = slist_remove_head(list);
	}
	else {
		previous->next = node->next;
		data = node->data;
		list->count--;
		if (list->count == 1) {
			list->tail = list->head;
		}
		else if (node == list->tail) {
			list->tail = previous;
		}
		free(node);
	}
	return data;
}

void slist_insert_before(slist * list, snode * node, snode * previous, void * data)
{
	if (node == list->head) {
		slist_add_head(list, data);
	}
	else {
		snode * newnode = snode_create(data);
		newnode->next = node;
		previous->next = newnode;
		list->count++;
	}
}

snode * slist_insert_after(slist * list, snode * node, void * data)
{
	snode * newnode;
	if (node == NULL) {
		slist_add_head(list, data);
		newnode = list->head;
	}
	else {
		newnode = snode_create(data);
		if (newnode) {
			newnode->next = node->next;
			node->next = newnode;
			if (node == list->tail) {
				list->tail = newnode;
			}
		}
		list->count++;
	}
	return newnode;
}

void slist_for_each(const slist * list, slist_forfn fun)
{
	snode * node;
	for (node = list->head; node != NULL; node = node->next) {
		fun(node->data);
	}
}

unsigned int slist_get_count(const slist * list)
{
	return list->count;
}

An example program:

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

#include <slist.h>

int main(void)
{
    slist * list = slist_create();
    char * elements[] = {"A", "B", "C", "D", "E", "F"};
    const unsigned int n = sizeof(elements) / sizeof(const char*);
    unsigned int i;
    snode * node, * previous = NULL;
    unsigned int found = 0;

    /* Populate the list with A, B, ..., F */
    for (i = 0; i < n; i++) {
        slist_add_tail(list, elements[i]);
    }
    
    /* Insert X and Y either side of C */
    for (node = list->head; node != NULL && !found; node = node->next) {
        if (strcmp((const char*)node->data, "C") == 0) {
            slist_insert_before(list, node, previous, "X");
            slist_insert_after(list, node, "Y");
            found = 1;
        }
        previous = node;
    }

    /* Forward iteration */
    for (node = list->head; node != NULL; node = node->next) {
        printf("%s\n", (const char*)node->data);
    }

    slist_delete(list);

    return 0;
}

Linked list in C

This is a doubly-linked list implementation. A linked list allows easy insertion and removal at either end or in the middle. Being doubly-linked allows traversal in reverse as well as forwards.

Here is an example program:

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

#include <linkedlist.h>

int main(void)
{
    linkedlist * list = linkedlist_create();
    char * elements[] = {"A", "B", "C", "D", "E", "F"};
    const unsigned int n = sizeof(elements) / sizeof(const char*);
    unsigned int i;
    listnode * node;
    unsigned int found = 0;

    /* Populate the list with A, B, ..., F */
    for (i = 0; i < n; i++) {
        linkedlist_add_tail(list, elements[i]);
    }
    
    /* Insert X and Y either side of C */
    for (node = list->head; node != NULL && !found; node = node->next) {
        if (strcmp((const char*)node->data, "C") == 0) {
            linkedlist_insert_before(list, node, "X");
            linkedlist_insert_after(list, node, "Y");
            found = 1;
        }
    }

    /* Forward iteration */
    for (node = list->head; node != NULL; node = node->next) {
        printf("%s\n", (const char*)node->data);
    }
    putchar('\n');

    /* Reverse iteration */
    for (node = list->tail; node != NULL; node = node->previous) {
        printf("%s\n", (const char*)node->data);
    }
    
    linkedlist_delete(list);

    return 0;
}

The header file:

#ifndef LINKEDLIST_H
#define LINKEDLIST_H

struct listnode {
	struct listnode * next;
	struct listnode * previous;
	void * data;
};
typedef struct listnode listnode;

struct linkedlist {
	listnode * head;
	listnode * tail;
	unsigned int count;
};
typedef struct linkedlist linkedlist;

typedef void (*linkedlist_forfn)(void *);

linkedlist * linkedlist_create(void);
void linkedlist_empty(linkedlist * list);
void linkedlist_delete(linkedlist * list);
void linkedlist_add_head(linkedlist * list, void * data);
void linkedlist_add_tail(linkedlist * list, void * data);
void linkedlist_insert_before(linkedlist * list, listnode * node, void * data);
void linkedlist_insert_after(linkedlist * list, listnode * node, void * data);
void * linkedlist_remove_head(linkedlist * list);
void * linkedlist_remove_tail(linkedlist * list);
void * linkedlist_remove_node(linkedlist * list, listnode * node);
void linkedlist_for_each(const linkedlist * list, linkedlist_forfn fun);
unsigned int linkedlist_get_count(const linkedlist * list);

#endif /* LINKEDLIST_H */

The implementation:

#include <stdlib.h>

#include <linkedlist.h>

listnode * listnode_create(void * data)
{
	listnode * node = malloc(sizeof(listnode));
	if (node) {
		node->next = NULL;
		node->previous = NULL;
		node->data = data;
	}
	return node;
}

linkedlist * linkedlist_create(void)
{
	linkedlist * list = malloc(sizeof(linkedlist));
	if (list) {
		list->head = NULL;
		list->tail = NULL;
		list->count = 0;
	}
	return list;
}

void linkedlist_empty(linkedlist * list)
{
	while(list->head != NULL) {
		linkedlist_remove_tail(list);
    }
}

void linkedlist_delete(linkedlist * list)
{
	if (list) {
		linkedlist_empty(list);
		free(list);
	}
}

void linkedlist_add_head(linkedlist * list, void * data)
{
	listnode * node;
	node = listnode_create(data);
	if (list->head != NULL) {
		list->head->previous = node;
		node->next = list->head;
		list->head = node;
	}
	else {
		list->head = node;
		list->tail = node;
	}
	list->count++;
}

void linkedlist_add_tail(linkedlist * list, void * data)
{
	listnode * node;
	node = listnode_create(data);
	if (list->tail != NULL) {
		list->tail->next = node;
		node->previous = list->tail;
		list->tail = node;
	}
	else {
		list->head = node;
		list->tail = node;
	}
	list->count++;
}

void linkedlist_insert_before(linkedlist * list, listnode * node, void * data)
{
	listnode * newnode;
	if (node == list->head) {
		linkedlist_add_head(list, data);
	}
	else {
		newnode = listnode_create(data);
		newnode->next = node;
		newnode->previous = node->previous;
		node->previous->next = newnode;
		node->previous = newnode;
		list->count++;
	}
}

void linkedlist_insert_after(linkedlist * list, listnode * node, void * data)
{
	listnode * newnode;
	if (node == list->tail) {
		linkedlist_add_tail(list, data);
	}
	else {
		newnode = listnode_create(data);
		newnode->previous = node;
		newnode->next = node->next;
		node->next->previous = newnode;
		node->next = newnode;
		list->count++;
	}
}

void * linkedlist_remove_head(linkedlist * list)
{
	void * data = NULL;
	if (list->head != NULL) {
		listnode * temp = list->head;
		list->head = list->head->next;
		if (list->head == NULL) {
			list->tail = NULL;
		}
		else {
			list->head->previous = NULL;
			if (list->head->next != NULL) {
				list->head->next->previous = list->head;
			}
			else {
				list->tail = list->head;
			}
		}
		data = temp->data;
		free(temp);
		list->count--;
	}
	return data;
}

void * linkedlist_remove_tail(linkedlist * list)
{
	void * data = NULL;
	if (list->tail != NULL) {
		listnode * temp = list->tail;
		list->tail = list->tail->previous;
		if (list->tail == NULL) {
			list->head = NULL;
		}
		else {
			list->tail->next = NULL;
			if (list->tail->previous != NULL) {
				list->tail->previous->next = list->tail;
			}
			else {
				list->head = list->tail;
			}
		}
		data = temp->data;
		free(temp);
		list->count--;
	}
	
	return data;
}

void * linkedlist_remove_node(linkedlist * list, listnode * node)
{
	void * data;
	if (node == list->head) {
		data = linkedlist_remove_head(list);
	}
	else if (node == list->tail) {
		data = linkedlist_remove_tail(list);
	}
	else {
		node->previous->next = node->next;
		node->next->previous = node->previous;
		data = node->data;
		free(node);
		list->count--;
	}
	return data;
}

void linkedlist_for_each(const linkedlist * list, forfn fun)
{
	listnode * node;
	for (node = list->head; node != NULL; node = node->next) {
		fun(node->data);
    }
}

unsigned int linkedlist_get_count(const linkedlist * list)
{
	return list->count;
}

Sorting a linked list by turning it into a binary search tree

Introduction

A doubly-linked list node has two pointers, previous and next, and a binary tree node also has two pointers, left and right

This means that one way of sorting a linked list is to turn it into a binary tree and then back into a list again.

Turning the list into a binary tree

Turning the list into a tree is just a question of iterating over the list and performing the normal binary tree insertion algorithm. We need to remember to save the current node’s next pointer before we insert it, as it will not be available afterwards.

typedef int(*cmpfn)(const void*, const void*);

listnode * linkedlist_to_tree(linkedlist * list, cmpfn compare)
{
    listnode * root = list->head;
    if (root) {
        listnode * node = root->next;
        root->previous = NULL;
        root->next = NULL;
        while (node != NULL) {
            listnode * next = node->next;
            listnode * current = root, * previous = NULL;
            int result;
            while (current != NULL) {
                previous = current;
                result = compare(current->data, node->data);
                if (result > 0) {
                    current = current->previous;
                }
                else {
                    current = current->next;
                }
            }
            if (result > 0) {
                previous->previous = node;
            }
            else {
                previous->next = node;
            }
            node->previous = NULL;
            node->next = NULL;
            node = next;
        }
    }
    return root;
}

Turning the binary tree back into a list

This involves an inorder traversal of the tree, which is most easily implemented using recursion. We need to look out for the first and last elements; they need to be treated specially as they are the head and tail of the list.

The first element in a binary tree is the one that we encounter the first time we can go left no further. We find the last element by keeping track of the number of elements encountered so far, and comparing it to the number in the list.

void linkedlist_from_tree(linkedlist * list, listnode * root,
        listnode ** previous, unsigned int * count)
{
    if (root) {
        listnode * left = root->previous;
        listnode * right = root->next;
        linkedlist_from_tree(list, left, previous, count);
        if (root->previous == NULL && list->head == NULL) {
            /* We're at the first element */
            list->head = root;
            list->head->previous = NULL;
        }
        else {
            (*previous)->next = root;
            root->previous = *previous;
        }
        if (*count == linkedlist_get_count(list) - 1) {
            /* We're at the last element */
            list->tail = root;
            list->tail->next = NULL;
        }
        *previous = root;
        (*count)++;
        linkedlist_from_tree(list, right, previous, count);
    }
}

The sort function

Our linked list sort function now just needs to combine the two operations:

void linkedlist_sort(linkedlist * list, cmpfn compare)
{
    unsigned int count = 0;
    listnode * previous;
    listnode * tree = linkedlist_to_tree(list, compare);
    list->head = NULL;
    list->tail = NULL;
    linkedlist_from_tree(list, tree, &previous, &count);
}

Example program

int main(void)
{
    char * elements[] = {"D", "B", "D", "F", "A", "C", "E"};
    const unsigned int n = sizeof(elements) / sizeof(const char *);
    linkedlist * list;
    unsigned int i;

    list = linkedlist_create();
    for (i = 0; i < n; i++) {
        linkedlist_add_tail(list, elements[i]);
    }
    linkedlist_sort(list, (cmpfn)strcmp);
    linkedlist_for_each(list, (forfn)puts);
    linkedlist_delete(list);

    return 0;
}

Circular linked list in C

A circular linked list is a linked list in which the head node’s previous pointer points to the tail node, and the tail node’s next pointer points to the head node. This means that the list only needs to keep track of one pointer for both head and tail.

A circular linked list containing elements labelled A to F

Looping over a circular linked list is slightly different from looping over an ordinary linked list because there is no NULL node to detect, and instead you are trying to get back to where you started. There are 2 methods of doing this.

Method 1: Use a do loop

void iterate1(const circularlist *list)
{
    cnode *node = list->head;
    if (node != NULL) {
        do {
            printf("%s\n", (const char*)node->data);
            node = node->next;
        } while (node != list->head);
    }
}

Method 2: Use a counter

void iterate2(const circularlist *list)
{
    cnode *node;
    unsigned int i;
    for (i = 0, node = list->head; i < list->count; i++, node = node->next) {
        printf("%s\n", (const char*)node->data);
    }
}

Here is the header file for the circular linked list

#ifndef CIRCULARLIST_H
#define CIRCULARLIST_H

struct cnode {
	struct cnode * next;
	struct cnode * previous;
	void * data;
};
typedef struct cnode cnode;

struct circularlist {
	cnode * head;
	unsigned int count;
};
typedef struct circularlist circularlist;

typedef void (*circularlist_forfn)(void *);

circularlist * circularlist_create(void);
void circularlist_delete(circularlist * list);

void circularlist_add_head(circularlist * list, void * data);
void circularlist_add_tail(circularlist * list, void * data);
void * circularlist_remove_head(circularlist * list);
void * circularlist_remove_tail(circularlist * list);
void * circularlist_remove_node(circularlist * list, cnode * node);
void circularlist_empty(circularlist * list);

void circularlist_insert_before(circularlist * list, cnode * node, void * data);
void circularlist_insert_after(circularlist * list, cnode * node, void * data);

void circularlist_for_each(const circularlist * list, circularlist_forfn fun);
unsigned int circularlist_get_count(const circularlist * list);

#endif /* CIRCULARLIST_H */

Here is the implementation

#include <stdlib.h>

#include <circularlist.h>

static cnode * cnode_create(void * data)
{
	cnode * node = malloc(sizeof(cnode));
	if(node) {
		node->next = node;
		node->previous = node;
		node->data = data;
	}

	return node;
}

static void cnode_delete(cnode * node)
{
	free(node);
}

circularlist * circularlist_create(void)
{
	circularlist * list = malloc(sizeof(circularlist));
	if (list) {
		list->head = NULL;
		list->count = 0;
	}

	return list;
}


void circularlist_delete(circularlist * list)
{
	if (list) {
		circularlist_empty(list);
		free(list);
	}
}

void circularlist_add_head(circularlist * list, void * data)
{
	circularlist_insert_before(list, list->head, data);
	list->head = list->head->previous;
}

void circularlist_add_tail(circularlist * list, void * data)
{
	circularlist_insert_before(list, list->head, data);
}

void * circularlist_remove_head(circularlist * list)
{
	return circularlist_remove_node(list, list->head);
}

void * circularlist_remove_tail(circularlist * list)
{
	void * data = NULL;
	if (list->head) {
		data = circularlist_remove_node(list, list->head->previous);
	}
	return data;
}

void * circularlist_remove_node(circularlist * list, cnode * node)
{
	void * data = NULL;
	if (list->count > 0) {
		if (node != node->next) { /* Or, list->count > 1 */
			node->next->previous = node->previous;
			node->previous->next = node->next;
			if (node == list->head)
				list->head = list->head->next;
		}
		else {
			/* Removing the last element */
			list->head = NULL;
		}
		data = node->data;
		cnode_delete(node);
		list->count--;
	}
	return data;
}

void circularlist_empty(circularlist * list)
{
	while (circularlist_remove_tail(list) != NULL);
}

void circularlist_insert_before(circularlist * list, cnode * node, void * data)
{
	cnode * newnode = cnode_create(data);

	if (newnode) {
		if (list->count > 0) {
			newnode->next = node;
			newnode->previous = node->previous;
			newnode->previous->next = newnode;
			node->previous = newnode;
		}
		else {
			/* Adding the first element */
			list->head = newnode;
		}
		list->count++;
	}
}

void circularlist_insert_after(circularlist * list, cnode * node, void * data)
{
	circularlist_insert_before(list, node->next, data);
}

void circularlist_for_each(const circularlist * list, circularlist_forfn fun)
{
	cnode * node = list->head;

	if (node != NULL) {
		do {
			fun(node->data);
			node = node->next;
		} while (node != list->head);
	}
}

unsigned int circularlist_get_count(const circularlist *list)
{
	return list->count;
}

Here is a test program

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

#include <circularlist.h>

int main(void)
{
    char * elements[] = {"A", "B", "C", "D", "E", "F"};
    const unsigned int n = sizeof(elements) / sizeof(const char*);
    circularlist * list;
    unsigned int i;
    cnode * node;
    unsigned int removed = 0, added = 0;

    list = circularlist_create();
    if (list) {
        /* Populate the list */
        for (i = 0; i < n; i++) {
            circularlist_add_tail(list, elements[i]);
        }

        /* Remove "C" */
        node = list->head;
        do {
            if (strcmp((const char*)node->data, "C") == 0) {
                circularlist_remove_node(list, node);
                removed = 1;
            }
            else {
                node = node->next;
            }
        } while (node != list->head && !removed);

        /* Add "X" and "Y" either side of "D" */
        node = list->head;
        do {
            if (strcmp((const char*)node->data, "D") == 0) {
                circularlist_insert_before(list, node, "X");
                circularlist_insert_after(list, node, "Y");
                added = 1;
            }
            else {
                node = node->next;
            }
        } while (node != list->head && !added);

        /* Print */
        printf("Count is %d\n", circularlist_get_count(list));
        circularlist_for_each(list, (circularlist_forfn)puts);

        circularlist_delete(list);
    }
    return 0;
}