Can we use doubly linked list in C without dynamic memory allocation?

Question

I am trying to use a doubly linked list data structure to implement a replacement policy in a buffer manager.

But my C program doesn't have a linked list library so I just defined the data structure by myself.

The problem is: Can I avoid doing any [dynamic?] memory allocation to use a doubly linked list?

What's the advantage of using palloc() instead of malloc()?

Answer 1

You can certainly create a doubly-linked list without using dynamic memory allocation at all; it is just aconventional to do so.

#include <stdio.h>
#include <assert.h>
#include <inttypes.h>

enum { NODEBUG = 0, DEBUG = 1 };

static const int debug = NODEBUG;

typedef struct DList DList;
struct DList
{
    int    data;
    DList *next;
    DList *prev;
};

enum { MAX_DLIST = 100 };
struct DList dlist[MAX_DLIST];

static void add_node(DList *head, DList *node)
{
    assert(head != 0 && node != 0);
    if (head->next == 0)
    {
        assert(head->prev == 0);
        head->next = node;
        head->prev = node;
        node->next = head;
        node->prev = head;
    }
    else
    {
        assert(head->prev != 0);
        node->next = head->next;
        node->prev = head;
        head->next->prev = node;
        head->next = node;
    }
}

static void diagnode(DList *node)
{
    if (debug)
        printf(" (T = 0x%.12" PRIXPTR ", N = 0x%.12" PRIXPTR ", P = 0x%.12" PRIXPTR ")\n",
               (uintptr_t)node, (uintptr_t)node->next, (uintptr_t)node->prev);
}

static void print_list(DList *head)
{
    assert(head != 0);
    printf("List:");
    if (head->next != 0)
    {
        DList *node;
        int counter = 0;
        if (debug)
            printf("\nHEAD");
        diagnode(head);
        for (node = head->next; node != head; node = node->next)
        {
            printf(" %3d", node->data);
            diagnode(node);
            assert(counter++ < MAX_DLIST);
        }
    }
    printf(" <EOL>\n");
}

int main(void)
{
    DList head = { 0, 0, 0 };

    for (int i = 0; i < MAX_DLIST; i++)
    {
        dlist[i].data = (i * 13 + 7) % 100;
        add_node(&head, &dlist[i]);
        if (debug)
            print_list(&head);
    }
    print_list(&head);
}

Not a memory allocation in sight! You can use a variant of this when you have something like a buffer manager where there is a fixed array of data buffers, but you want an LRU (least-recently used) replacement policy. Instead of have the data directly in the doubly-linked list structure as in this example, the data element would point to an entry in the buffer pool. You can then add and remove entries from the list without changing anything in the main data structure that your list is linked to.

---

If palloc() is a pooled memory allocator, the advantage of using it over malloc() is that you can release all the memory allocated to a given pool with a single function call, rather than having to manage all the separate frees yourself. Sometimes, a pool allocator will be more efficient than separate memory allocation with malloc(); it might allocate a big array of a fixed size structure and then dole out entries on request, reducing the number of allocations and thereby reducing the amount of overhead.