{"id":1120,"date":"2015-04-07T19:35:07","date_gmt":"2015-04-08T02:35:07","guid":{"rendered":"http:\/\/www.giassa.net\/?page_id=1120"},"modified":"2025-08-24T08:03:52","modified_gmt":"2025-08-24T15:03:52","slug":"linked-lists","status":"publish","type":"page","link":"https:\/\/www.giassa.net\/?page_id=1120","title":{"rendered":"Linked Lists"},"content":{"rendered":"

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<\/a>, 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.<\/p>\n

A sample implementation is provided below.<\/p>\n

 <\/p>\n

#ifndef LINKED_LIST_H \/\/ Prevent multiple inclusions\r\n#define LINKED_LIST_H\r\n\r\n\/*******************************************************************************\r\n * Preprocessor Directives\r\n ******************************************************************************\/\r\n\r\n\r\n\/*******************************************************************************\r\n * Macros and Constants\r\n ******************************************************************************\/\r\n\r\n\r\n\/*******************************************************************************\r\n * Abstract Data Types\r\n ******************************************************************************\/\r\n\/* Generic node in a linked list *\/\r\ntypedef struct lnode_t {\r\n   struct lnode_t* next;\r\n   void*    data;\r\n   size_t   width;\r\n} lnode_t;\r\n\r\n\/* Generic list *\/\r\ntypedef struct llist_t {\r\n   lnode_t* head;\r\n   size_t   length;\r\n} llist_t;\r\n\r\n\/*******************************************************************************\r\n * Public Function Prototypes\r\n *******************************************************************************\/\r\n\/* Handle compiling C code as part of a C++ project *\/\r\n#ifdef __cplusplus\r\nextern \"C\" {\r\n#endif\r\n\r\n\/* @functionName: llistInit\r\n * @brief:        Initializes an empty linked list.\r\n * @param:        list: A pointer to the list.\r\n *\/\r\nint llistInit(llist_t* list);\r\n\r\n\/* @functionName: llistDestroy\r\n * @brief:        Destroys and cleans up an entire list.\r\n * @param:        list: A pointer to the list.\r\n *\/\r\nint llistDestroy(llist_t* list);\r\n\r\n\/* @functionName: llistInsert\r\n * @brief:        Inserts a new node at the beginning of a linked list.\r\n * @param:        list: A pointer to the list.\r\n * @param:        ins:  A pointer to the node to insert.\r\n *\/\r\nint llistInsert(llist_t* list, lnode_t* ins);\r\n\r\n\/* @functionName: llistDelete\r\n * @brief:        Delete an item at a specific position in a list.\r\n * @param:        list: A pointer to the list.\r\n * @param:        idx:  The index of the item to delete.\r\n *\/\r\nint llistDelete(llist_t* list, int idx);\r\n\r\n\/* @functionName: llistAppend\r\n * @brief:        Appends an item to the end of a list.\r\n * @param:        list: A pointer to the list.\r\n * @param:        append:  A pointer to the node to add to the list.\r\n *\/\r\nint llistAppend(llist_t* list, lnode_t* append);\r\n\r\n\/* @functionName: llistInsertAfter\r\n * @brief:        Adds an item to a linked list at a specific index.\r\n * @param:        list: A pointer to the list.\r\n * @param:        add:       A pointer to the node to add to the list.\r\n * @param:        position:  The index at which to add the new node.\r\n *\/\r\nint llistInsertAfter(llist_t* list, lnode_t* add, int position);\r\n\r\n#ifdef __cplusplus\r\n}\r\n#endif\r\n\r\n#endif \/\/ LINKED_LIST_H\r\n<\/pre>\n
 <\/p>\n
\/*******************************************************************************\r\n * @file:      linked_list.c\r\n * @author:    Matthew Giassa\r\n * @email:     matthew@giassa.net\r\n * @copyright: Matthew Giassa, 2008\r\n * @brief:     Simple linked list implementation as part of Mmath library for\r\n *             current research projects in biomedical engineering.\r\n *\/\r\n\r\n\/*******************************************************************************\r\n * Preprocessor Directives\r\n ******************************************************************************\/\r\n\/* System Includes *\/\r\n#include <stdio.h>\r\n#include <errno.h>\r\n#include <stdlib.h>\r\n#include <string.h>\r\n#include <time.h>\r\n\r\n\/* Project Includes *\/\r\n#include \"inc\/linked_list.h\"\r\n\r\n\r\n\/*******************************************************************************\r\n * Macros and Constants\r\n ******************************************************************************\/\r\n#define EOK (0)\r\n\r\n\r\n\/*******************************************************************************\r\n * Abstract Data Types\r\n ******************************************************************************\/\r\n\r\n\r\n\/*******************************************************************************\r\n * Private Function Prototypes\r\n ******************************************************************************\/\r\nlnode_t* llistCloneNode(lnode_t* node);\r\nlnode_t* llistFreeNode(lnode_t* node);\r\nint      llistDump(llist_t* list);\r\n\r\n\r\n\/*******************************************************************************\r\n * Function Definitions\r\n ******************************************************************************\/\r\n#if 0\r\n\/*----------------------------------------------------------------------------*\/\r\nint main(void) {\r\n   llist_t list = { 0 };   \/* Need to zero out contents prior to calling init *\/\r\n   lnode_t* cur;\r\n   int i, ret;\r\n\r\n   \/* Initialize random seed *\/\r\n   srand(time(NULL));\r\n\r\n   \/* Initialize list and populate with a single zeroed out entry *\/\r\n   if ((ret = llistInit(&list)) != EOK) {\r\n      return ret;\r\n   }\r\n\r\n   \/* Create template entry for populating simple list *\/\r\n   const int nEntries = 10;\r\n   cur = calloc(1, sizeof(lnode_t));\r\n   cur->width = sizeof(int);\r\n   cur->data = calloc(1, cur->width);\r\n\r\n   \/* Populate the list with random entries *\/\r\n   for (i=0; i<nEntries; i++) {\r\n      *(int*)(cur->data) = rand() % 100;\r\n      llistInsert(&list, cur);\r\n   }\r\n\r\n   \/* Dump list contents to console *\/\r\n   llistDump(&list);\r\n\r\n   \/* Attempt to insert entries throughout the list at corner cases *\/\r\n   *(int*)(cur->data) = rand() % 100;\r\n   llistInsertAfter(&list, cur, nEntries-1);\r\n   *(int*)(cur->data) = rand() % 100;\r\n   llistInsertAfter(&list, cur, 0);\r\n   *(int*)(cur->data) = rand() % 100;\r\n   llistInsertAfter(&list, cur, nEntries*2);\r\n\r\n   \/* Dump list contents to console *\/\r\n   llistDump(&list);\r\n\r\n   \/* Insert more random entries in random positions *\/\r\n   for (i=0; i<nEntries; i++) {\r\n      *(int*)(cur->data) = rand() % 100;\r\n      llistInsertAfter(&list, cur, rand() % 100);\r\n   }\r\n\r\n   \/* Append some dummy entries to the end *\/\r\n   for (i=0; i<nEntries; i++) {\r\n      *(int*)(cur->data) = 0;\r\n      llistAppend(&list, cur);\r\n   }\r\n\r\n   \/* Dump list contents to console *\/\r\n   llistDump(&list);\r\n\r\n   \/* Try to make some good and bad deletions *\/\r\n   llistDelete(&list, -1);\r\n   llistDelete(&list, 0);\r\n   llistDelete(&list, 1);\r\n   llistDelete(&list, 100);\r\n   llistDelete(&list, 1);\r\n   llistDelete(&list, 1);\r\n   llistDelete(&list, 1);\r\n   llistDelete(&list, list.length);    \/* Expected to fail *\/\r\n   llistDelete(&list, list.length-1);\r\n   llistDelete(&list, list.length-2);\r\n\r\n   \/* Dump list contents to console *\/\r\n   llistDump(&list);\r\n\r\n   llistDestroy(&list);\r\n\r\n   return EOK;\r\n}\r\n#endif\r\n\r\n\/*----------------------------------------------------------------------------*\/\r\nlnode_t* llistCloneNode(lnode_t* node) {\r\n   if (!node) {\r\n      return NULL;\r\n   }\r\n\r\n   lnode_t* tmp;\r\n   if ((tmp = malloc(1*sizeof(lnode_t))) == NULL) {\r\n      return NULL;\r\n   }\r\n   if ((tmp->data = malloc(1*tmp->width)) == NULL) {\r\n      free(tmp);\r\n      return NULL;\r\n   }\r\n\r\n   \/* Copy contents of node, accounting for dynamically allocated contents *\/\r\n   tmp->width = node->width;\r\n   tmp->next = node->next;\r\n   memcpy(tmp->data, node->data, node->width);\r\n   return tmp;\r\n}\r\n\r\n\r\n\/*----------------------------------------------------------------------------*\/\r\nlnode_t* llistFreeNode(lnode_t* node) {\r\n   if (!node) {\r\n      return NULL;\r\n   }\r\n\r\n   free(node->data);\r\n   memset(node, 0, sizeof(lnode_t));\r\n   free(node);\r\n   return NULL;\r\n}\r\n\r\n\r\n\/*----------------------------------------------------------------------------*\/\r\nint llistInit(llist_t* list) {\r\n   if (!list) {\r\n      return (-EINVAL);\r\n   }\r\n   int ret = EOK;\r\n\r\n   \/* Just make sure the provided \"head\" node pointer points to NULL, so that\r\n    * we aren't erroneously calling init on an already-populated list.\r\n    *\/\r\n   if (list->head != NULL) {\r\n      ret = (-EIO);\r\n   } else {\r\n      list->length = 0;\r\n   }\r\n\r\n   return ret;\r\n}\r\n\r\n\r\n\/*----------------------------------------------------------------------------*\/\r\nint llistDestroy(llist_t* list) {\r\n   if (!list) {\r\n      return (-EINVAL);\r\n   }\r\n   lnode_t* cur = list->head;\r\n   lnode_t* next;\r\n\r\n   \/* Delete first entry in list until empty *\/\r\n   while (cur) {\r\n      next = cur->next;\r\n      llistDelete(list, 0);\r\n      cur = next;\r\n   }\r\n   list->length = 0;\r\n\r\n   return EOK;\r\n}\r\n\r\n\r\n\/*----------------------------------------------------------------------------*\/\r\nint llistInsert(llist_t* list, lnode_t* ins) {\r\n   if (!list || !ins) {\r\n      return (-EINVAL);\r\n   }\r\n   lnode_t* tmp;\r\n   if ((tmp = llistCloneNode(ins)) == NULL) {\r\n      return (-ENOMEM);\r\n   }\r\n\r\n   if (list->head == NULL) {\r\n      \/* Account for empty list *\/\r\n      list->head = tmp;\r\n      list->head->next = NULL;\r\n   } else {\r\n      \/* Insert at beginning of list *\/\r\n      tmp->next = list->head;\r\n      list->head = tmp;\r\n   }\r\n   list->length++;\r\n\r\n   return EOK;\r\n}\r\n\r\n\r\n\/*----------------------------------------------------------------------------*\/\r\nint llistAppend(llist_t* list, lnode_t* append) {\r\n   if (!list || !append) {\r\n      return (-EINVAL);\r\n   }\r\n   lnode_t* tmp;\r\n   if ((tmp = llistCloneNode(append)) == NULL) {\r\n      return (-ENOMEM);\r\n   }\r\n   lnode_t* cur = list->head;\r\n\r\n   if (list->head == NULL) {\r\n      \/* Account for empty list *\/\r\n      list->head = tmp;\r\n      list->head->next = NULL;\r\n   } else {\r\n      \/* Seek end of list *\/\r\n      while(cur->next != NULL) {\r\n         cur = cur->next;\r\n      }\r\n      \/* Append *\/\r\n      cur->next = tmp;\r\n      cur = tmp;\r\n      cur->next = NULL;\r\n   }\r\n   list->length++;\r\n\r\n   return EOK;\r\n}\r\n\r\n\r\n\/*----------------------------------------------------------------------------*\/\r\nint llistInsertAfter(llist_t* list, lnode_t* add, int position) {\r\n   if (!list || !list->head || !add || position < 0) {\r\n      return (-EINVAL);\r\n   }\r\n   int i, ret = EOK;\r\n   lnode_t *left, *right, *tmp;\r\n   if ((tmp = llistCloneNode(add)) == NULL) {\r\n      return (-ENOMEM);\r\n   }\r\n\r\n   right = list->head;\r\n   for (i=0; i <= position; i++) {\r\n      if (right == NULL) {\r\n         \/* Out of bounds; Abort *\/\r\n         ret = (-EIO);\r\n         break;\r\n      }\r\n      left = right;\r\n      right = right->next;\r\n   }\r\n   if (ret == EOK) {\r\n      left->next = tmp;\r\n      tmp->next = right;\r\n      list->length++;\r\n   }\r\n   return ret;\r\n}\r\n\r\n\r\n\/*----------------------------------------------------------------------------*\/\r\nint llistDelete(llist_t* list, int idx) {\r\n   if (!list || idx < 0) {\r\n      return (-EINVAL);\r\n   }\r\n   int i = 0;\r\n   lnode_t* cur = list->head;\r\n   lnode_t* prev;\r\n\r\n   \/* Find the entry to be removed *\/\r\n   cur = list->head;\r\n   for (i=0; cur != NULL; i++) {\r\n      if (i == idx) {\r\n         if (cur == list->head) {\r\n            list->head = cur->next;\r\n            llistFreeNode(cur);\r\n            list->length--;\r\n            return EOK;\r\n         } else {\r\n            prev->next = cur->next;\r\n            llistFreeNode(cur);\r\n            list->length--;\r\n            return EOK;\r\n         }\r\n      } else {\r\n         prev = cur;\r\n         cur = cur->next;\r\n      }\r\n   }\r\n\r\n   \/* Disqualify out-of-bounds requests *\/\r\n   printf(\"ERROR, out of bounds request\\n\");\r\n   return (-EINVAL);;\r\n}\r\n\r\n\r\n\/*----------------------------------------------------------------------------*\/\r\nint llistDump(llist_t* list) {\r\n   if (!list) {\r\n      return (-EINVAL);\r\n   }\r\n   int i = 0;\r\n   lnode_t* cur = list->head;\r\n\r\n   while (cur) {\r\n      printf(\"Iteration %d - Size:%zd - Data:%d - Length:%zd\\n\",\r\n            i, cur->width, *(int*)cur->data, list->length);\r\n      i++;\r\n      cur = cur->next;\r\n   }\r\n\r\n   return EOK;\r\n}\r\n\r\n\r\n<\/pre>\n
 <\/p>\n","protected":false},"excerpt":{"rendered":"
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 … Continue reading →<\/span><\/a><\/p>\n","protected":false},"author":1,"featured_media":0,"parent":1075,"menu_order":0,"comment_status":"closed","ping_status":"closed","template":"","meta":{"footnotes":""},"class_list":["post-1120","page","type-page","status-publish","hentry"],"aioseo_notices":[],"_links":{"self":[{"href":"https:\/\/www.giassa.net\/index.php?rest_route=\/wp\/v2\/pages\/1120","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/www.giassa.net\/index.php?rest_route=\/wp\/v2\/pages"}],"about":[{"href":"https:\/\/www.giassa.net\/index.php?rest_route=\/wp\/v2\/types\/page"}],"author":[{"embeddable":true,"href":"https:\/\/www.giassa.net\/index.php?rest_route=\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/www.giassa.net\/index.php?rest_route=%2Fwp%2Fv2%2Fcomments&post=1120"}],"version-history":[{"count":1,"href":"https:\/\/www.giassa.net\/index.php?rest_route=\/wp\/v2\/pages\/1120\/revisions"}],"predecessor-version":[{"id":1121,"href":"https:\/\/www.giassa.net\/index.php?rest_route=\/wp\/v2\/pages\/1120\/revisions\/1121"}],"up":[{"embeddable":true,"href":"https:\/\/www.giassa.net\/index.php?rest_route=\/wp\/v2\/pages\/1075"}],"wp:attachment":[{"href":"https:\/\/www.giassa.net\/index.php?rest_route=%2Fwp%2Fv2%2Fmedia&parent=1120"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}