A linked list is a data structure composed of “nodes”. Each node contains, at the minimum, a piece of data, and a pointer to another node. It is a FIFO structure (First In, First Out), but unlike a stack, some implementations allow the insertion and removal of elements in the middle of the structure rather than requiring all additions and removals to occur at the extremities of the list.
A sample implementation is provided below.
#ifndef LINKED_LIST_H // Prevent multiple inclusions
#define LINKED_LIST_H
/*******************************************************************************
* Preprocessor Directives
******************************************************************************/
/*******************************************************************************
* Macros and Constants
******************************************************************************/
/*******************************************************************************
* Abstract Data Types
******************************************************************************/
/* Generic node in a linked list */
typedef struct lnode_t {
struct lnode_t* next;
void* data;
size_t width;
} lnode_t;
/* Generic list */
typedef struct llist_t {
lnode_t* head;
size_t length;
} llist_t;
/*******************************************************************************
* Public Function Prototypes
*******************************************************************************/
/* Handle compiling C code as part of a C++ project */
#ifdef __cplusplus
extern "C" {
#endif
/* @functionName: llistInit
* @brief: Initializes an empty linked list.
* @param: list: A pointer to the list.
*/
int llistInit(llist_t* list);
/* @functionName: llistDestroy
* @brief: Destroys and cleans up an entire list.
* @param: list: A pointer to the list.
*/
int llistDestroy(llist_t* list);
/* @functionName: llistInsert
* @brief: Inserts a new node at the beginning of a linked list.
* @param: list: A pointer to the list.
* @param: ins: A pointer to the node to insert.
*/
int llistInsert(llist_t* list, lnode_t* ins);
/* @functionName: llistDelete
* @brief: Delete an item at a specific position in a list.
* @param: list: A pointer to the list.
* @param: idx: The index of the item to delete.
*/
int llistDelete(llist_t* list, int idx);
/* @functionName: llistAppend
* @brief: Appends an item to the end of a list.
* @param: list: A pointer to the list.
* @param: append: A pointer to the node to add to the list.
*/
int llistAppend(llist_t* list, lnode_t* append);
/* @functionName: llistInsertAfter
* @brief: Adds an item to a linked list at a specific index.
* @param: list: A pointer to the list.
* @param: add: A pointer to the node to add to the list.
* @param: position: The index at which to add the new node.
*/
int llistInsertAfter(llist_t* list, lnode_t* add, int position);
#ifdef __cplusplus
}
#endif
#endif // LINKED_LIST_H
/*******************************************************************************
* @file: linked_list.c
* @author: Matthew Giassa
* @email: matthew@giassa.net
* @copyright: Matthew Giassa, 2008
* @brief: Simple linked list implementation as part of Mmath library for
* current research projects in biomedical engineering.
*/
/*******************************************************************************
* Preprocessor Directives
******************************************************************************/
/* System Includes */
#include <stdio.h>
#include <errno.h>
#include <stdlib.h>
#include <string.h>
#include <time.h>
/* Project Includes */
#include "inc/linked_list.h"
/*******************************************************************************
* Macros and Constants
******************************************************************************/
#define EOK (0)
/*******************************************************************************
* Abstract Data Types
******************************************************************************/
/*******************************************************************************
* Private Function Prototypes
******************************************************************************/
lnode_t* llistCloneNode(lnode_t* node);
lnode_t* llistFreeNode(lnode_t* node);
int llistDump(llist_t* list);
/*******************************************************************************
* Function Definitions
******************************************************************************/
#if 0
/*----------------------------------------------------------------------------*/
int main(void) {
llist_t list = { 0 }; /* Need to zero out contents prior to calling init */
lnode_t* cur;
int i, ret;
/* Initialize random seed */
srand(time(NULL));
/* Initialize list and populate with a single zeroed out entry */
if ((ret = llistInit(&list)) != EOK) {
return ret;
}
/* Create template entry for populating simple list */
const int nEntries = 10;
cur = calloc(1, sizeof(lnode_t));
cur->width = sizeof(int);
cur->data = calloc(1, cur->width);
/* Populate the list with random entries */
for (i=0; i<nEntries; i++) {
*(int*)(cur->data) = rand() % 100;
llistInsert(&list, cur);
}
/* Dump list contents to console */
llistDump(&list);
/* Attempt to insert entries throughout the list at corner cases */
*(int*)(cur->data) = rand() % 100;
llistInsertAfter(&list, cur, nEntries-1);
*(int*)(cur->data) = rand() % 100;
llistInsertAfter(&list, cur, 0);
*(int*)(cur->data) = rand() % 100;
llistInsertAfter(&list, cur, nEntries*2);
/* Dump list contents to console */
llistDump(&list);
/* Insert more random entries in random positions */
for (i=0; i<nEntries; i++) {
*(int*)(cur->data) = rand() % 100;
llistInsertAfter(&list, cur, rand() % 100);
}
/* Append some dummy entries to the end */
for (i=0; i<nEntries; i++) {
*(int*)(cur->data) = 0;
llistAppend(&list, cur);
}
/* Dump list contents to console */
llistDump(&list);
/* Try to make some good and bad deletions */
llistDelete(&list, -1);
llistDelete(&list, 0);
llistDelete(&list, 1);
llistDelete(&list, 100);
llistDelete(&list, 1);
llistDelete(&list, 1);
llistDelete(&list, 1);
llistDelete(&list, list.length); /* Expected to fail */
llistDelete(&list, list.length-1);
llistDelete(&list, list.length-2);
/* Dump list contents to console */
llistDump(&list);
llistDestroy(&list);
return EOK;
}
#endif
/*----------------------------------------------------------------------------*/
lnode_t* llistCloneNode(lnode_t* node) {
if (!node) {
return NULL;
}
lnode_t* tmp;
if ((tmp = malloc(1*sizeof(lnode_t))) == NULL) {
return NULL;
}
if ((tmp->data = malloc(1*tmp->width)) == NULL) {
free(tmp);
return NULL;
}
/* Copy contents of node, accounting for dynamically allocated contents */
tmp->width = node->width;
tmp->next = node->next;
memcpy(tmp->data, node->data, node->width);
return tmp;
}
/*----------------------------------------------------------------------------*/
lnode_t* llistFreeNode(lnode_t* node) {
if (!node) {
return NULL;
}
free(node->data);
memset(node, 0, sizeof(lnode_t));
free(node);
return NULL;
}
/*----------------------------------------------------------------------------*/
int llistInit(llist_t* list) {
if (!list) {
return (-EINVAL);
}
int ret = EOK;
/* Just make sure the provided "head" node pointer points to NULL, so that
* we aren't erroneously calling init on an already-populated list.
*/
if (list->head != NULL) {
ret = (-EIO);
} else {
list->length = 0;
}
return ret;
}
/*----------------------------------------------------------------------------*/
int llistDestroy(llist_t* list) {
if (!list) {
return (-EINVAL);
}
lnode_t* cur = list->head;
lnode_t* next;
/* Delete first entry in list until empty */
while (cur) {
next = cur->next;
llistDelete(list, 0);
cur = next;
}
list->length = 0;
return EOK;
}
/*----------------------------------------------------------------------------*/
int llistInsert(llist_t* list, lnode_t* ins) {
if (!list || !ins) {
return (-EINVAL);
}
lnode_t* tmp;
if ((tmp = llistCloneNode(ins)) == NULL) {
return (-ENOMEM);
}
if (list->head == NULL) {
/* Account for empty list */
list->head = tmp;
list->head->next = NULL;
} else {
/* Insert at beginning of list */
tmp->next = list->head;
list->head = tmp;
}
list->length++;
return EOK;
}
/*----------------------------------------------------------------------------*/
int llistAppend(llist_t* list, lnode_t* append) {
if (!list || !append) {
return (-EINVAL);
}
lnode_t* tmp;
if ((tmp = llistCloneNode(append)) == NULL) {
return (-ENOMEM);
}
lnode_t* cur = list->head;
if (list->head == NULL) {
/* Account for empty list */
list->head = tmp;
list->head->next = NULL;
} else {
/* Seek end of list */
while(cur->next != NULL) {
cur = cur->next;
}
/* Append */
cur->next = tmp;
cur = tmp;
cur->next = NULL;
}
list->length++;
return EOK;
}
/*----------------------------------------------------------------------------*/
int llistInsertAfter(llist_t* list, lnode_t* add, int position) {
if (!list || !list->head || !add || position < 0) {
return (-EINVAL);
}
int i, ret = EOK;
lnode_t *left, *right, *tmp;
if ((tmp = llistCloneNode(add)) == NULL) {
return (-ENOMEM);
}
right = list->head;
for (i=0; i <= position; i++) {
if (right == NULL) {
/* Out of bounds; Abort */
ret = (-EIO);
break;
}
left = right;
right = right->next;
}
if (ret == EOK) {
left->next = tmp;
tmp->next = right;
list->length++;
}
return ret;
}
/*----------------------------------------------------------------------------*/
int llistDelete(llist_t* list, int idx) {
if (!list || idx < 0) {
return (-EINVAL);
}
int i = 0;
lnode_t* cur = list->head;
lnode_t* prev;
/* Find the entry to be removed */
cur = list->head;
for (i=0; cur != NULL; i++) {
if (i == idx) {
if (cur == list->head) {
list->head = cur->next;
llistFreeNode(cur);
list->length--;
return EOK;
} else {
prev->next = cur->next;
llistFreeNode(cur);
list->length--;
return EOK;
}
} else {
prev = cur;
cur = cur->next;
}
}
/* Disqualify out-of-bounds requests */
printf("ERROR, out of bounds request\n");
return (-EINVAL);;
}
/*----------------------------------------------------------------------------*/
int llistDump(llist_t* list) {
if (!list) {
return (-EINVAL);
}
int i = 0;
lnode_t* cur = list->head;
while (cur) {
printf("Iteration %d - Size:%zd - Data:%d - Length:%zd\n",
i, cur->width, *(int*)cur->data, list->length);
i++;
cur = cur->next;
}
return EOK;
}