Concerning Graph Prologue: The L

We address linked list in this post, which serves as the backbone of several other more advanced ADTs.

#include <stdlib.h>
#include <stdio.h>
#include <limits.h>
#include <stdbool.h>
#ifndef LINKED_LIST
#define LINKED_LIST
typedef struct NodeStruct {
    int item;
    struct NodeStruct *next;
}* Node;

/**
 * head->...->tail
*/
typedef struct LinkedListStruct {
    int count;
    Node head;
    Node tail;
}* LinkedList;

Node NodeCreate(int item) {
    Node node = (Node)malloc(sizeof(*node));
    node->item = item;
    node->next = NULL;
    return node;
}

void NodeRelease(Node node) { if (node != NULL) free(node); }

LinkedList LinkedListCreate() { 
    LinkedList lst = (LinkedList)malloc(sizeof(*lst));
    lst->count = 0;
    lst->head = lst->tail = NULL;
    return lst;
 }

void LinkedListRelease(LinkedList list) {
    if (list != NULL) {
        Node x = list->head;
        while (x != NULL) {
            Node t = x;
            x = x->next;
            NodeRelease(t);
        }
        free(list);
    }
}

int LinkedListCount(LinkedList list) { return list == NULL ? 0 : list->count; }

bool LinkedListIsEmpty(LinkedList list) { return list == NULL || list->count == 0; }

/**
 * Works when list == NULL, that is, insertion into a empty list
*/
void LinkedListInsertHead(LinkedList list, int item) {
    Node x = NodeCreate(item);
    x->next = list->head;
    list->head = x;
    list->count++;
    if (list->count == 1) { list->tail = x; }
}

int LinkedListRemoveHead(LinkedList list) {
    if (list == NULL) return INT_MIN;

    Node x = list->head;
    list->head = x->next;
    int item = x->item;
    list->count--;
    NodeRelease(x);
    if (list->count == 0) { list->tail = NULL; }
    return item;
}

void LinkedListInsertTail(LinkedList list, int item) {
    if (list != NULL) {
        Node x = NodeCreate(item);
        if (list->count == 0) {
            list->head = list->tail = x;
        } else {
            list->tail->next = x;
            list->tail = x;
        }
        list->count++;
    }
}

int* LinkedListItems(LinkedList list, int *n) {
    if (list == NULL) return NULL;
    if (n != NULL) { *n = list->count; }
    int *items = (int*)malloc(list->count * sizeof(*items));
    Node x = list->head;
    while (x != NULL) {
        *(items++) = x->item;
        x = x->next;
    }
    return items - list->count;
}

/**
 * Not used
*/
int LinkedListRemoveTail(LinkedList list) {return INT_MIN; }

void LinkedListPrint(LinkedList list) {
    Node x = list->head;
    printf("[\n");
    while (x != NULL) { 
        printf("%s%i", x == list->head ? "" : "->", x->item); 
        x = x->next;
    }
    printf("\n]\n");
}

#endif

Bag implementation:

#include "linked_list.c"
typedef struct LinkedListBagStruct {
    LinkedList list;
}*LinkedListBag;

LinkedListBag LinkedListBagCreate() {
    LinkedListBag bag = (LinkedListBag)malloc(sizeof(*bag));
    bag->list = LinkedListCreate();
    return bag;
}

void LinkedListBagRelease(LinkedListBag bag) {
    if (bag == NULL) return;
    if (bag->list != NULL) { LinkedListRelease(bag->list); }
    free(bag);
}

int LinkedListBagCount(LinkedListBag bag) { return bag == NULL ? 0 : LinkedListCount(bag->list); }

bool LinkedListBagIsEmpty(LinkedListBag bag) { return LinkedListBagCount(bag) == 0; }

void LinkedListBagAdd(LinkedListBag bag, int item) { if (bag != NULL) { LinkedListInsertHead(bag->list, item); } }

int* LinkedListBagItems(LinkedListBag bag) {
    int count = LinkedListBagCount(bag);
    if (count == 0) return NULL;
    int *items = (int*)malloc(count * sizeof(*items));
    Node x = bag->list->head;
    while (x != NULL) {
        *(items++) = x->item;
        x = x->next;
    }
    return items - count;
}

void LinkedListBagPrint(LinkedListBag bag) {
    printf("(\n");
    if (bag != NULL) {
        printf("count: %i\n", LinkedListBagCount(bag));
        LinkedListPrint(bag->list);
    }
    printf(")\n");
}

Stack impl:

#include "linked_list.c"
typedef struct LinkedListStackStruct {
    LinkedList list;
}*LinkedListStack;

LinkedListStack LinkedListStackCreate() {
    LinkedListStack stack = (LinkedListStack)malloc(sizeof(*stack));
    stack->list = LinkedListCreate();
    return stack;
}

void LinkedListStackRelease(LinkedListStack stack) {
    if (stack != NULL) {
        if (stack->list != NULL) { LinkedListRelease(stack->list); }
        free(stack);
    }
}

int LinkedListStackCount(LinkedListStack stack) { return stack == NULL ? INT_MIN : LinkedListCount(stack->list); }

bool LinkedListStackIsEmpty(LinkedListStack stack) { return LinkedListStackCount(stack) == 0; }

void LinkedListStackPush(LinkedListStack stack, int item) { if (stack != NULL) { LinkedListInsertHead(stack->list, item); } }

int LinkedListStackPop(LinkedListStack stack) {
    if (stack == NULL || LinkedListStackIsEmpty(stack)) return INT_MIN;
    return LinkedListRemoveHead(stack->list);
}

int* LinkedListStackItems(LinkedListStack stack, int *n) { return LinkedListStackIsEmpty(stack) ? NULL : LinkedListItems(stack->list, n); }

void LinkedListStackPrint(LinkedListStack stack) {
    printf("<\n");
    if (stack != NULL) {
        printf("count: %i\n", LinkedListCount(stack->list));
        LinkedListPrint(stack->list);
    }
    printf(">\n");
}

FIFO Queue impl:

#include "linked_list.c"
#include "linked_list.c"
typedef struct LinkedListQueueStruct {
    LinkedList list;
}*LinkedListQueue;

LinkedListQueue LinkedListQueueCreate() {
    LinkedListQueue queue = (LinkedListQueue)malloc(sizeof(*queue));
    queue->list = LinkedListCreate();
    return queue;
}

void LinkedListQueueRelease(LinkedListQueue queue) {
    if (queue != NULL) {
        LinkedListRelease(queue->list);
        free(queue);
    }
}

int LinkedListQueueCount(LinkedListQueue queue) { return queue == NULL ? 0 : LinkedListCount(queue->list); }

bool LinkedListQueueIsEmpty(LinkedListQueue queue) { return queue == NULL || LinkedListCount(queue->list) == 0; }

void LinkedListQueueEnqueue(LinkedListQueue queue, int item) { if (queue != NULL) { LinkedListInsertTail(queue->list, item); } }

int LinkedListQueueDequeue(LinkedListQueue queue) {
    if (queue == NULL || LinkedListQueueIsEmpty(queue)) return INT_MIN;
    return LinkedListRemoveHead(queue->list);
}

void LinkedListQueuePrint(LinkedListQueue queue) {
    if (queue == NULL) return;
    printf("<\n");
    printf("count: %i\n", LinkedListCount(queue->list));
    LinkedListPrint(queue->list);
    printf("\n>\n");
}