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++;
}