Linked lists are a linear collection of elements whose order order is not given by their physical placement in memory. Instead, each element contains a member variable which is a pointer to the next element. For example:
struct _inode{ int data; struct _inode *next; }; typedef struct _inode inode_t; struct _list{ inode_t *head; unsigned int count; };
In this section, i will be going over algorithms to help manipulate these data structures, as well as different types of linked lists. I will also be writing a generic linked list similar to the vector structure we went over. I will first start off by showing you how i plan on having the list header file setup:
#ifndef LIST_H_ #define LIST_H_ #include <stdint.h> #include <stddef.h> struct _node{ void * data; struct _node * next; }; typedef struct _node node_t; node_t * mallocNode(void * data); void allocData(node_t * out,size_t size); void setData(node_t * out, void * d); void setNext(node_t * out, node_t * n); node_t * getTail(node_t * head); struct _list{ uint32_t count; struct _node * head; }; typedef struct _list list_t; void pushBack(list_t * out , void * data); void pushFront(list_t * out , void * data); void * popFront(list_t * list); void * popBack(list_t * list); node_t * nodeAt(unsigned int index, list_t * out); void insert(list_t * list, unsigned int index, void * data); #endif
As you can see, we have a structure named node_t, which represents the data it contains, as well as a pointer to the next structure. I decided to typedef the structure after definition. This is considered a singly-linked list node. Another way programmers tend to define linked lists is through doubly-linked lists, where the structure node_t would also contain a pointer to the previous node in the list.
After defining the structure, i wrote a couple functions which would help
manipulate the data. The function mallocNode will allocate a new node_t and set the data of that node to the parameter passed in. allocData is a more procedural way of dealing with it. You pass the node_t in which you want data to be allocated, and then you malloc its data member variable. I also wrote a setData and setNext function which you pass the node into and it manipulates the member variables. Last I wrote the getTail function for convenience. That will just return the last node_t in the list recursively.
Next was the actual list structure. list_t is a structure which only defines the head of a list, as well as the count of elements in the list. I created two different functions for each operation on the list. You can either push an element to the front of the list, or to the back, as well as pop an element from the front or the back. For more convenience, I wrote the nodeAt function which gets a node from a specific index (as long as the index is within the list’s count). Last, i used the nodeAt function to write an insert function that inserts an element at the specified location (as long as the index is within the list’s count).
#include "list.h" #include <stdio.h> #include <stdlib.h> #include <string.h> /************ mallocNode : node_t * input : pointer to the data being placed in the node return : pointer to the node being allocated *************/ node_t * mallocNode(void * data){ node_t * ret = malloc(sizeof(node_t)); ret->data = data; ret->next = NULL; return ret; } /************ setData : void input : pointer to the node being manipulated pointer to the data being placed within the node return : nothing *************/ void setData(node_t * out, void * d){ out->data = d; } /************ allocData : void input : the node being manipulated the size of the node's data return : nothing *************/ void allocData(node_t * out,size_t size){ out->data = malloc(size); memset(out->data,0, size); } /************ setNext : void input : the node being manipulated the node which will refer to out->next return : nothing *************/ void setNext(node_t * out, node_t * n){ out->next = n; } /************ getTail : node_t * input : the head of the node return : pointer to the last node of the link *************/ node_t * getTail(node_t * head){ node_t * ret = head; if(ret->next != NULL){ return getTail(ret->next); } return ret; } /*************** allocEmptyList: list_t * input : nothing return : allocated list with an empty head ****************/ list_t * allocEmptyList(){ list_t * ret = malloc(sizeof(list_t)); ret->count = 0; ret->head = NULL; return ret; } /*************** pushBack : void input : pointer to list being manipulated pointer to data being placed in list return : nothing ****************/ void pushBack(list_t * out , void * data){ if(out->head != NULL){ node_t * tail = getTail(out->head); node_t * item = mallocNode(data); setNext(tail,item); } else{ out->head = mallocNode(data); } out->count++; } /*************** pushFront : void input : pointer to list being manipulated pointer to data being placed in list return : nothing ****************/ void pushFront(list_t * out , void * data){ if(out->head != NULL){ node_t * item = mallocNode(data); setNext(item,out->head); out->head = item; } else{ out->head = mallocNode(data); } out->count++; } /*************** popFront : void * input : pointer to list being manipulated return : pointer to data from the front of the list ****************/ void * popFront(list_t * list){ void * ret; node_t * postHead = list->head->next; node_t * currHead = list->head; setNext(currHead, NULL); list->head = postHead; ret = currHead->data; list->count--; return ret; } /*************** popBack : void * input : pointer to list being manipulated return : pointer to data from the Back of the list ****************/ void * popBack(list_t * list){ node_t * temp = list->head; node_t * ret = getTail(list->head); //iterate until temp's next node is ret. while(temp->next != ret){ temp = temp->next; } temp->next = NULL; list->count--; return ret; } /*************** nodeAt : node_t * input : unsigned int index of node pointer to list being iterated over return : node at specified index ****************/ node_t * nodeAt(unsigned int index, list_t * out){ if(index > out->count){ return NULL; } node_t * temp = out->head; unsigned int i = 0; while(i > index){ temp = temp->next; i++; } return temp; } /*************** insert : void input : pointer to list unsigned int index of node being placed pointer to data being placed within the node return : none ****************/ void insert(list_t * list, unsigned int index, void * data){ if(index > list->count){ printf("Error, size of list (%u) is not as big as index (%u)\n", list->count,index); return; } node_t * preNode = nodeAt(index-1, list); node_t * postNode = nodeAt(index, list); node_t * insertNode = mallocNode(data); setNext(insertNode, postNode); setNext(preNode,insertNode); list->count++; }
With the little I’ve read, it sounds like you know the topic. I’ll have to come back to read it.