How should I implement capacity for C Dymanic Linked List?

Question

I know it is very easy to implement when you are using it as an ADT in OOP languages.

But what should be done in case of structured language like C?

Should I use a global variable?

Should I keep an extra variable in every node?

Or what?

I have implemented my Dynamic Stack like this.

As you can see there are no capacity checking.

Answer 1

Linked/Dynamic stacks grows by adding a new dynamically allocated node to it's top. Now memory is never unlimited, at one point in dynamically growing you'll run out of memory and you won't be able to create a new node. This can be treated as a stackoverflow.

Answer 2

If you want to implement a capacity limit to a linked list, the best way is to have a per-list limitation. The following structures will allow that:

// List structure: first/last pointers plus remaining capacity.
typedef struct {
    tNode *first;
    tNode *last;
    size_t freeCount;
} tList;

// Node structure: value pointer and next.
typedef struct sNode {
    void *val;
    struct sNode *next;
} tNode;

Then you initialise your limit per list:

// Creates an empty list.
tList *makeList (size_t limit) {
    tList *list = malloc (sizeof (tList));
    if (list == NULL)
        return NULL;
    list->freeCount = limit;
    list->first = list->last = NULL;
}

// Destroys a list after clearing it if necessary.
void destroyList (tList list) {
    void *val = getNode (list);
    while (val != NULL) {
        free (val);
        val = getNode (list);
    }
    free (list);
}

After that, adding a node will fail if the freeCount is zero, otherwise it will add a node and decrement freeCount. Removing a node will increase freeCount, something like:

// Puts an item on to the list end.
int putNode (tList *list, void *val, size_t sz) {
    // No more capacity.
    if (list->freeCount == 0) return -1;

    // Try to make node, returning error if no memory.
    tNode *node = malloc (sizeof (tNode));
    if (node == NULL) return -1;

    // Try to duplicate payload, clean up and return if no memory.
    node->val = malloc (sz);
    if (node->val == NULL) {
        free (node);
        return -1;
    }

    // Initialise node.
    memcpy (node->val, val, sz)
    node->next = NULL;

    // Adjust remaining capacity and insert into list.
    list->freeCount--;
    if (list->first == NULL) {
        list->first = list->last = node;
    } else {
        list->last->next = node;
        list->last = node;
    }

    return 0;
}

 

// Gets an item from the list.
void *getNode (tList *list) {
    // If empty, just return NULL.
    if (list->first == NULL)
        return NULL;

    // Get first node and remove it from list.
    tNode node = list->first;
    list->first = list->first->next;

    // Get the payload and free the node.
    void *val = node->val;
    free (node);

    // Adjust remianing capacity and return payload.
    list->freeCount++;
    return val;
}

Notice how all the normal error conditions are there (no memory, list empty and so on) as well as the extra limitation of trying to add a node when you've already reached full capacity (when freeCount is zero).