Doubly linked list optimally defined over 17 operations in C [4]?

Question

Previous versions of this question

First Version

Second Version

Third Version

Fourth Version

Changes

I built upon the previous singly linked list and implemented a doubly linked one.

You are not allowed to insert_sll at the front or back, but only in position i such that 0 < i < n=size-1.

Thanks in advance for any improvement ideas!

#include <stdio.h>
#include <stdlib.h>

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

Node* head = NULL;
Node* tail = NULL;
int size = 0;

Node* create_node(int elm) {
    Node* node = malloc(sizeof * node), * exits = NULL;
    if (!node) return exits;
    node->data = elm;
    node->prev = NULL;
    node->next = NULL;
    size += 1;
    return node;
}

Node* get_tail() {
    return tail;
}

int is_empty_sll() {
    return head == NULL;
}

int size_sll() {
    return size;
}

Node* node_k_sll(int k) { // 0-based index
    int n = size_sll() - 1;
    if (!is_empty_sll() && (k >= 0 && k <= n)) {
        int i = 0;
        Node* node = head;
        while (i != k) {
            i += 1;
            node = node->next;
        }
        return node;
    }
    else {
        printf("Invalid k or List is Empty");
        Node* node = NULL;
        return node;
    }
}

void append_sll(int elm) { //O(1)
    Node* cur = create_node(elm);
    if (!head) {
        head = cur;
    }
    else {
        tail->next = cur;
        cur->prev = tail;
    }
    tail = cur;
}

void prepend_sll(int elm) {
    Node* updated_head = create_node(elm);
    if (!head) {
        head = updated_head;
        tail = head;
    }
    else {
        updated_head->next = head;
        head->prev = updated_head;
        head = updated_head;
    }
}

void insert_sll(int elm, int i) {
    if (!is_empty_sll()) {
        int k = 1, n = size_sll(); // we don't prepend, so K > 0
        if (i > 0 && i < n) { //  1 < i < n | 1:prepend, n:append
            Node* cur = create_node(elm);
            Node* last = head;
            while (k != i) {
                k += 1;
                last = last->next;
            }
            cur->next = last->next;
            (last->next)->prev = cur;
            cur->prev = last;
            last->next = cur;
            
        }
        else printf("Invalid i");
    }
    else printf("List Is Empty");
}

int delete_sll(int elm) {
    int n = size_sll(), found = 0;
    Node* node = head;
    if (head->data == elm) {
        head = head->next;
        head->prev = NULL;
        found = 1;
        free(node);
    }
    else {
        Node* prev = head;
        for (int i = 0; i < n; i++) {
            if (node->data != elm) {
                prev = node; // if comment this, uncomment below
                node = node->next;
            }
            else {
                found = 1;
                break;
            }
        }
        /*(node->prev)->next = node->next;
        (node->next)->prev = node->prev;*/
        prev->next = node->next;
        if (node->data != tail->data)
            (node->next)->prev = prev;
        else 
            tail = prev;
        free(node);
    }
    if (found) {
        size -= 1;
        return 1;
    }
    else
        return -1;
}

int find_sll(int elm) {// returns -1 if element not found
    int found = 0;
    if (!is_empty_sll()) {
        int i, n = size_sll();
        Node* last = head;
        for (i = 0; i < n; i++) {
            if (last->data != elm) {
                last = last->next;
            }
            else {
                found = 1;
                break;
            }
        }
        if (found) return i;
        else return -1;
    }
    else return -1;
}

void swap_sll(int i, int j) {// swap value of position i with j
    Node* node_i = node_k_sll(i);
    Node* node_j = node_k_sll(j);
    int temp = node_i->data;
    node_i->data = node_j->data;
    node_j->data = temp;
}

void print_sll(char p) {
    if (p == 'f') {
        Node* trav = head;
        while (trav) {
            printf("%d ", trav->data);
            trav = trav->next;
        }
    }
    else {
        Node* trav = tail;
        while (trav) {
            printf("%d ", trav->data);
            trav = trav->prev;
        }
    }
    printf("\n");
}

void reverse_sll() {
    if (!is_empty_sll()) {
        Node* node = head, *temp, *prev;
        while (node) {
            prev = node;
            node = node->next;
            temp = prev->next;
            prev->next = prev->prev;
            prev->prev = temp;  
        }
        temp = head;
        head = tail;
        tail = temp;
    }
}

void clear_sll() { //O(n)
    while (head) {
        Node* temp = head;
        head = head->next;
        free(temp);
        size -= 1;
    }
    printf("List Cleared!\n");
}

void rotate_sll(int k, char p) {
    if (!is_empty_sll() && (k < size && size > 1)) {
        int size = size_sll();
        Node* k_node = node_k_sll(k);
        head->prev = tail;
        tail->next = head;
        if (p == 'f') {
            for (int i = 0; i < size; i++) {
                printf("%d ", k_node->data);
                k_node = k_node->next;
            }
        }
        else {
            for (int i = 0; i < size; i++) {
                printf("%d ", k_node->data);
                k_node = k_node->prev;
            }
        }
        tail->next = NULL;
        head->prev = NULL;
        printf("\n");
    }
    else printf("List Is Empty or Invalid k");
}

void delete_front_sll() {
    if (!is_empty_sll())
        delete_sll(head->data);
    else
        printf("List is Empty!");
}

void delete_back_sll() {
    if (!is_empty_sll())
        delete_sll(tail->data);
    else
        printf("List is Empty!");
}

// void sort_sll() {//

// }

int main() {
    prepend_sll(0);
    append_sll(1);
    append_sll(2);
    append_sll(4);
    insert_sll(3, 3);
    print_sll('f');
    reverse_sll();
    print_sll('f');
    rotate_sll(2, 'f');
    insert_sll(3, 3);
    print_sll('f');
    prepend_sll(0);
    print_sll('f');
    printf("size: %d\n", size_sll());
    printf("index of 3 is: %d\n", find_sll(3));
    delete_sll(2);
    print_sll('f');
    swap_sll(0, 1);
    print_sll('f');
    reverse_sll();
    print_sll('f');
    append_sll(0);
    append_sll(-1);
    print_sll('f');
    rotate_sll(2, 'f');
    delete_front_sll();
    print_sll('f');
    delete_back_sll();
    print_sll('f');
    append_sll(20);
    prepend_sll(-20);
    print_sll('f');
    clear_sll();

    return 0;
}

Answer 1

These globals are a problem:

Node* head = NULL;
Node* tail = NULL;
int size = 0;

That means that we can only ever have a single list in any given program. We need to encapsulate these variables into a struct that we can instantiate as many times as we need (and use a more appropriate type for the size):

struct LinkedList {
    Node* head = NULL;
    Node* tail = NULL;
    size_t size = 0;
};

---

create_node() ought to have static linkage, as Node shouldn't be part of the user-visible interface to the list.

Declare one variable per line. In fact, exits isn't needed, because it's only used in one place:

Node *create_node(int elm)
{
    Node* node = malloc(sizeof *node);
    if (!node) { return node; }
    node->data = elm;
    node->prev = NULL;
    node->next = NULL;
    ++size;
    return node;
}

---

Some of the function declarations are prototypes (they specify the arguments that can be passed) and some are not (they allow any number of arguments, of any type). It's better to be consistent, and use prototypes for all declarations:

Node *get_tail(void);
int is_empty_sll(void);
size_t size_sll(void);
void reverse_sll(void);
void clear_sll(void);
void delete_front_sll(void);
void delete_back_sll(void);
int main(void);

Also, why do most these functions have sll in the name? It's not clear what that stands for.

---

GCC believes that append_sll dereferences tail - you should check whether it's detected a bug:

283247.c: In function ‘append_sll’:
283247.c:64:20: warning: dereference of NULL ‘tail’ [CWE-476] [-Wanalyzer-null-dereference]
   64 |         tail->next = cur;
      |         ~~~~~~~~~~~^~~~~
  ‘main’: events 1-2
    |
    |  257 | int main()
    |      |     ^~~~
    |      |     |
    |      |     (1) entry to ‘main’
    |  258 | {
    |  259 |     prepend_sll(0);
    |      |     ~~~~~~~~~~~~~~
    |      |     |
    |      |     (2) calling ‘prepend_sll’ from ‘main’
    |
    +--> ‘prepend_sll’: events 3-4
           |
           |   70 | void prepend_sll(int elm)
           |      |      ^~~~~~~~~~~
           |      |      |
           |      |      (3) entry to ‘prepend_sll’
           |   71 | {
           |   72 |     Node* updated_head = create_node(elm);
           |      |                          ~~~~~~~~~~~~~~~~
           |      |                          |
           |      |                          (4) calling ‘create_node’ from ‘prepend_sll’
           |
           +--> ‘create_node’: events 5-7
                  |
                  |   14 | Node* create_node(int elm)
                  |      |       ^~~~~~~~~~~
                  |      |       |
                  |      |       (5) entry to ‘create_node’
                  |......
                  |   17 |     if (!node) { return node; }
                  |      |        ~
                  |      |        |
                  |      |        (6) following ‘false’ branch (when ‘node’ is non-NULL)...
                  |   18 |     node->data = elm;
                  |      |     ~~~~~~~~~~~~~~~~
                  |      |                |
                  |      |                (7) ...to here
                  |
           <------+
           |
         ‘prepend_sll’: events 8-10
           |
           |   72 |     Node* updated_head = create_node(elm);
           |      |                          ^~~~~~~~~~~~~~~~
           |      |                          |
           |      |                          (8) returning to ‘prepend_sll’ from ‘create_node’
           |   73 |     if (!head) {
           |      |        ~                  
           |      |        |
           |      |        (9) following ‘true’ branch...
           |   74 |         head = updated_head;
           |      |         ~~~~~~~~~~~~~~~~~~~
           |      |              |
           |      |              (10) ...to here
           |
    <------+
    |
  ‘main’: events 11-12
    |
    |  259 |     prepend_sll(0);
    |      |     ^~~~~~~~~~~~~~
    |      |     |
    |      |     (11) returning to ‘main’ from ‘prepend_sll’
    |  260 |     append_sll(1);
    |      |     ~~~~~~~~~~~~~
    |      |     |
    |      |     (12) calling ‘append_sll’ from ‘main’
    |
    +--> ‘append_sll’: events 13-14
           |
           |   58 | void append_sll(int elm)
           |      |      ^~~~~~~~~~
           |      |      |
           |      |      (13) entry to ‘append_sll’
           |   59 | { //O(1)
           |   60 |     Node* cur = create_node(elm);
           |      |                 ~~~~~~~~~~~~~~~~
           |      |                 |
           |      |                 (14) calling ‘create_node’ from ‘append_sll’
           |
           +--> ‘create_node’: events 15-19
                  |
                  |   14 | Node* create_node(int elm)
                  |      |       ^~~~~~~~~~~
                  |      |       |
                  |      |       (15) entry to ‘create_node’
                  |   15 | {
                  |   16 |     Node* node = malloc(sizeof * node);
                  |      |                  ~~~~~~~~~~~~~~~~~~~~~
                  |      |                  |
                  |      |                  (16) allocated here
                  |   17 |     if (!node) { return node; }
                  |      |        ~                ~~~~
                  |      |        |                |
                  |      |        |                (19) ...to here
                  |      |        (17) assuming ‘node’ is NULL
                  |      |        (18) following ‘true’ branch (when ‘node’ is NULL)...
                  |
           <------+
           |
         ‘append_sll’: events 20-23
           |
           |   60 |     Node* cur = create_node(elm);
           |      |                 ^~~~~~~~~~~~~~~~
           |      |                 |
           |      |                 (20) return of NULL to ‘append_sll’ from ‘create_node’
           |   61 |     if (!head) {
           |      |        ~         
           |      |        |
           |      |        (21) following ‘false’ branch...
           |......
           |   64 |         tail->next = cur;
           |      |             ~~   
           |      |             |
           |      |             (22) ...to here
           |   65 |         cur->prev = tail;
           |      |         ~~~~~~~~~~~~~~~~
           |      |                   |
           |      |                   (23) state of ‘&HEAP_ALLOCATED_REGION(55)’: ‘null’ -> ‘stop’ (NULL origin)
           |
    <------+
    |
  ‘main’: events 24-25
    |
    |  260 |     append_sll(1);
    |      |     ^~~~~~~~~~~~~
    |      |     |
    |      |     (24) returning to ‘main’ from ‘append_sll’
    |  261 |     append_sll(2);
    |      |     ~~~~~~~~~~~~~
    |      |     |
    |      |     (25) calling ‘append_sll’ from ‘main’
    |
    +--> ‘append_sll’: events 26-27
           |
           |   58 | void append_sll(int elm)
           |      |      ^~~~~~~~~~
           |      |      |
           |      |      (26) entry to ‘append_sll’
           |   59 | { //O(1)
           |   60 |     Node* cur = create_node(elm);
           |      |                 ~~~~~~~~~~~~~~~~
           |      |                 |
           |      |                 (27) calling ‘create_node’ from ‘append_sll’
           |
           +--> ‘create_node’: events 28-31
                  |
                  |   14 | Node* create_node(int elm)
                  |      |       ^~~~~~~~~~~
                  |      |       |
                  |      |       (28) entry to ‘create_node’
                  |......
                  |   17 |     if (!node) { return node; }
                  |      |        ~                ~~~~
                  |      |        |                |
                  |      |        |                (31) ...to here
                  |      |        (29) ‘tail’ is NULL
                  |      |        (30) following ‘true’ branch (when ‘node’ is NULL)...
                  |
           <------+
           |
         ‘append_sll’: events 32-35
           |
           |   60 |     Node* cur = create_node(elm);
           |      |                 ^~~~~~~~~~~~~~~~
           |      |                 |
           |      |                 (32) returning to ‘append_sll’ from ‘create_node’
           |   61 |     if (!head) {
           |      |        ~         
           |      |        |
           |      |        (33) following ‘false’ branch...
           |......
           |   64 |         tail->next = cur;
           |      |         ~~~~~~~~~~~~~~~~
           |      |             |      |
           |      |             |      (35) dereference of NULL ‘tail’
           |      |             (34) ...to here
           |

There are a number of other -fanalyzer warnings that should be checked and rectified.

I think the cause of most of these is that although we're careful to check whether malloc() returns a null pointer in create_node(), we then fail to check the return value of create_node() where we call it.

---

node_k_sll accepts a signed int, but rejects negative values. A more appropriate type for indexing into storage is size_t.

It's redundant to test the size and emptiness of the list (size should always be 0 when the list is empty).

The while loop has a control variable that's incremented each time around, so would be better (more easily recognised) as a for loop.

In the error case, we print to standard output - diagnostics such as that should go to the standard error stream. And output should always be complete lines.

Node* node_k_sll(size_t k)
{ // 0-based index
    if (k >= size_sll()) {
        fprintf(stderr, "Invalid k or List is Empty\n");
        return NULL;
    }

    Node* node = head;
    while (k--) {
        node = node->next;
    }
    return node;
}

---

insert_sll fails if the list is empty, which seems wrong to me when we're inserting at position 0. In fact, we can always delegate to prepend_sll() in that case (and, for efficiency, delegate to append_sll() when inserting at the end; also consider walking the list from the end if inserting to the second half).

It's easier to consider the error cases first, and return early. That reduces the amount of context readers need to maintain:

bool insert_sll(int elm, size_t i)
{
    if (i == 0) {
        return prepend_sll(elm);
    }
    if (i == size_sll()) {
        return append_sll(elm);
    }
    if (is_empty_sll()) {
        fprintf(stderr, "List Is Empty");
        return false;
    }

    Node *node = head;
    Node *const new_node = create_node(elm);
    if (!new_node) {
        return false;
    }
    while (i--) {
        node = node->next;
        assert(node);           /* given that initial i < size */
    }
    new_node->next = node;
    new_node->prev = node->prev;
    node->prev->next = new_node;
    node->prev = new_node;
    return true;
}

---

delete_sll() has a bug when it removes the only node from a single-element list:

        head = head->next;
        head->prev = NULL;

When head->next is null, we should be adjusting tail instead:

        head = head->next;
        if (head) {
            head->prev = NULL;
        } else {
            tail = NULL;
        }

---

delete_back_sll() has a bug that requires unravelling the undocumented behaviour of other functions. It actually deletes the first element that has the same value as the tail element. Delegating to the delete-by-value function doesn't cut it:

bool delete_back_sll(void)
{
    Node *const node = tail;
    if (!node) {
        fprintf(stderr, "List is Empty!\n");
        return false;
    }
    tail = node->prev;
    if (tail) {
        tail->next = NULL;
    } else {
        head = NULL;
    }
    free(node);
    return true;
}

It may be a worthwhile idea to write an internal function

static bool delete_node(Node *node);

---

Swapping nodes by exchanging their contents is fine for int content. However, for lists of larger content, it can be more efficient to exchange their links instead. It might even be necessary if any content is the target of a pointer.

---

clear_sll has a bug - it leaves tail unchanged, likely a dangling pointer.

---

A lot of the complication of dealing with head and tail pointers in place of a node's prev and next can be eliminated by having a dummy Node to hold the head and tail of the list. You might recognise this as us using the Null Object pattern.

---

The main() program exercises the code, but it doesn't confirm the correctness of it. We should be verifying the results of operations, and returning EXIT_FAILURE if the behaviour is not as expected.

Answer 2

create_node()

This applies to all your questions, it was in a previous review I wrote. Use calloc(size_t count, size_t size). The reason I suggest this is that calloc() returns memory that has been initialized to all \0. This greatly simplifies you code by removing the need to initialize the pointers to NULL.

Please note that Node *exits is not necessary, node will be NULL if malloc() or calloc() fail.

Node* create_node(int elm) {
    Node* node = calloc(1, sizeof(*node));
    if (node) {
        node->data = elm;
        size += 1;
    }
    return node;
}

find_sll()

You have finally fixed the problem with find_sll(). You can make this function faster and simpler by using a while loop rather than a for loop.

int find_sll(int elm) {// returns -1 if element not found
    int not_found = -1;
    int i = 0;
    Node* last = head;

    while (last)
    {
        if (last->data == elm)
        {
            return i;
        }
        last = last->next;
        i++;
    }
    
    return not_found;
}

There is no reason to continue or break the loop in this code: it returns i if found, and returns -1 otherwise. The code is much simpler.

It is also important to understand that size_sll() never needs to be called in this function.

In this case is_empty_sll() doesn't need to be called either because if head is null then last will also be null and the flow will never enter the while loop.

This is what I meant in the previous review when I said you were mixing up arrays with linked lists.

If I was writing this code, rather than returning an index I would be returning a Node pointer; it gives direct access to the node.

Answer 3

Consider a test-driven approach to implementing this functionality. That is, write tests for each piece of functionality before implementing it.

We would want to begin with the minimum necessary to create and destroy an empty list:

#define TEST_LIST(list, count, ...) /* TODO */

int main(void)
{
    {
        List *list = list_alloc();
        TEST_LIST(list, 0);
        list_free(list);
    }
}

We'll need the beginnings of the public interface (in a header file):

typedef struct List List;

List *list_alloc(void);
void list_free(List*);

Notice I'm using a common prefix to the function names. This is helpful because it means they all end up together when sorted alphabetically.

And now we can start the implementation. I'll use a circular list with dummy head node, because I anticipate that this will reduce special-case code for start and end.

#include <stdlib.h>

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

struct List {
    Node content;
    size_t size;
};

List *list_alloc(void) {
    List *list = malloc(sizeof *list);
    if (list) {
        list->size = 0;
        list->content.prev = NULL;
        list->content.next = NULL;
    }
    return list;
}

void list_free(List *list)
{
    if (!list) { return; }
    Node *n = list->content.next;
    while (n && n != &list->content) {
        Node *t = n;
        n = n->next;
        free(t);
    }
    free(list);
}

Now we just need to implement the TEST_LIST macro. At this stage, we just need to be able to test an empty list, but I'm going to jump ahead and implement the whole test:

#include <stdarg.h>
#include <stdbool.h>
#include <stdio.h>

/* verify list's invariants and contents */
bool test_list(char const *file, int line,
               const List *list, size_t count, ...)
{
    if (!list) {
        fprintf(stderr, "%s:%d: List is null\n", file, line);
        return false;
    }
    if (list->size != count) {
        fprintf(stderr, "%s:%d: List length is %zu, but expected %zu\n",
                file, line, list->size, count);
        return false;
    }

    va_list args;
    va_start(args, count);

    Node const *node = list->content.next;
    for (size_t i = 0;  i < count;  ++i) {
        if (node->prev->next != node) {
            fprintf(stderr, "%s:%d: Inconsistent 'prev' pointer at element %zu\n",
                    file, line, i);
            return false;
        }
        if (node->next->prev != node) {
            fprintf(stderr, "%s:%d: Inconsistent 'next' pointer at element %zu\n",
                    file, line, i);
            return false;
        }
        int val = va_arg(args, int);
        if (val != node->data) {
            fprintf(stderr, "%s:%d: list[%zu] contains %d, but expected %d\n",
                    file, line, i, node->data, val);
            return false;
        }
        node = node->next;
    }

    va_end(args);
    return true;
}

#define TEST_LIST(...) if (!test_list(__FILE__, __LINE__, __VA_ARGS__)) \
        return EXIT_FAILURE;

We now have something which will fail if we break any of the functionality, and which we can run under Valgrind to diagnose any of the usual memory problems.

---

Now we add a test for the next function:

    {
        List *list = list_alloc();
        assert(list_prepend(list, 4));
        TEST_LIST(list, 1, 4);
        assert(list_prepend(list, 6));
        TEST_LIST(list, 2, 6, 4);
        list_free(list);
    }

Then we can implement it:

bool list_prepend(List *list, int value)
{
    if (!list) { return false; }
    Node* node = malloc(sizeof *node);
    if (!node) { return false; }
    node->data = value;
    node->next = list->content.next;
    node->prev = &list->content;
    list->content.next = node;
    node->next->prev = node;
    ++list->size;
    return true;
}

We run the test, and it passes, with no Valgrind errors. Great!

---

Next function:

    {
        List *list = list_alloc();
        assert(list_append(list, 4));
        TEST_LIST(list, 1, 4);
        assert(list_append(list, 6));
        TEST_LIST(list, 2, 4, 6);
        list_free(list);
    }

And implementation:

bool list_append(List *list, int value)
{
    if (!list) { return false; }
    Node* node = malloc(sizeof *node);
    if (!node) { return false; }
    node->data = value;
    node->next = &list->content;
    node->prev = list->content.prev;
    list->content.prev = node;
    node->prev->next = node;
    ++list->size;
    return true;
}

This passes first time, too! But before we congratulate ourselves, now is the opportunity to refactor. We have two functions that are very similar, so let's reduce the duplication by introducing an internal helper function:

static bool insert_after(Node *node, int value)
{
    Node *new_node = malloc(sizeof *new_node);
    if (!new_node) { return false; };
    new_node->data = value;
    new_node->next = node->next;
    new_node->prev = node;
    new_node->prev->next = new_node;
    new_node->next->prev = new_node;
    return true;
}

bool list_prepend(List *list, int value)
{
    if (!list) { return false; }
    if (!insert_after(&list->content, value)) { return false; }
    ++list->size;
    return true;
}

bool list_append(List *list, int value)
{
    if (!list) { return false; }
    if (!insert_after(list->content.prev, value)) { return false; }
    ++list->size;
    return true;
}

The tests give us a safety-net to perform refactoring like this without fear that we break existing functionality.

---

The refactoring we have just done is about to pay off, as we add the function to insert at a given index. First, the tests. We start by testing the error case - inserting beyond the end:

    {
        List *list = list_alloc();
        assert(!list_insert(list, 1, 5));
        list_free(list);
    }

We can make that test pass:

bool list_insert(List *list, size_t position, int value)
{
    if (!list || position > list->size) { return false; }
    return true;                 /* for now */
}

Now extend to handle a valid call:

    {
        List *list = list_alloc();
        assert(!list_insert(list, 1, 5)); /* out of range */
        TEST_LIST(list, 0);

        assert(list_append(list, 4));
        assert(list_append(list, 6));
        assert(list_insert(list, 1, 5)); /* in the middle */
        TEST_LIST(list, 3,  4, 5, 6);

        assert(list_insert(list, 0, 3)); /* at the front */
        TEST_LIST(list, 4,  3, 4, 5, 6);

        assert(list_insert(list, 4, 7)); /* at the back */
        TEST_LIST(list, 5,  3, 4, 5, 6, 7);

        list_free(list);
    }

bool list_insert(List *list, size_t position, int value)
{
    if (!list || position > list->size) { return false; }
    Node *n = &list->content;
    while (position--) {
        n = n->next;
    }
    if (!insert_after(n, value)) { return false; }
    ++list->size;
    return true;
}

---

We can continue implementing the functionality a piece at a time. And as we go, add extra functions that help the tests; they are probably valuable to users as well. For example, I created a list_set_values() function to quickly initialise a non-empty list.

When I did this, it resulted in this header:

#ifndef LIST_H_
#define LIST_H_

#include <stdbool.h>
#include <stddef.h>
#include <stdio.h>

typedef struct List List;

//static const size_t Invalid_Index = (size_t)-1;

/* create and destroy */
List *list_alloc(void);
void list_free(List *list);

/* add values */
bool list_set_values(List *list, size_t count, ...);
bool list_prepend(List *list, int value);
bool list_append(List *list, int value);
bool list_insert(List *list, size_t position, int value);

/* remove values */
void list_clear(List *list);
void list_pop_front(List *list);
void list_pop_back(List *list);
bool list_remove_value(List *list, int value);

/* move values */
void list_rotate_left(List *list, size_t steps);
void list_rotate_right(List *list, size_t steps);
void list_reverse(List *list);

/* traversal */
void list_traverse(List *list, void (*fun)(int*,void*), void*);
void list_print(List *list, FILE *f);

/* for the unit tests */
bool test_list(char const *file, int line,
               const List *list, size_t count, ...);

#endif

And these tests:

#include "list.h"

#undef NDEBUG
#include <assert.h>
#include <stdlib.h>

#define TEST_LIST(...) if (!test_list(__FILE__, __LINE__, __VA_ARGS__)) \
        return EXIT_FAILURE;

static void times_two(int *p, void *unused)
{
    (void)unused;
    *p *= 2;
}

static void accumulate(int *p, void *s)
{
    int *sum = s;
    *sum += *p;
}

int main(void)
{
    {
        List *list = list_alloc();
        TEST_LIST(list, 0);
        list_free(list);
    }

    {
        List *list = list_alloc();
        assert(list_set_values(list, 2,  10, 20));
        TEST_LIST(list, 2,  10, 20);
        list_clear(list);
        TEST_LIST(list, 0);
        list_free(list);
    }

    {
        List *list = list_alloc();
        assert(list_prepend(list, 4));
        TEST_LIST(list, 1,  4);
        assert(list_prepend(list, 6));
        TEST_LIST(list, 2,  6, 4);
        list_free(list);
    }

    {
        List *list = list_alloc();
        assert(list_append(list, 4));
        TEST_LIST(list, 1,  4);
        assert(list_append(list, 6));
        TEST_LIST(list, 2,  4, 6);
        list_free(list);
    }

    {
        List *list = list_alloc();
        assert(!list_insert(list, 1, 5)); /* out of range */
        TEST_LIST(list, 0); /* unchanged */

        assert(list_set_values(list, 2,  4, 6));
        assert(list_insert(list, 1, 5)); /* in the middle */
        TEST_LIST(list, 3,  4, 5, 6);

        assert(list_insert(list, 0, 3)); /* at the front */
        TEST_LIST(list, 4,  3, 4, 5, 6);

        assert(list_insert(list, 4, 7)); /* at the back */
        TEST_LIST(list, 5,  3, 4, 5, 6, 7);

        list_free(list);
    }

    {
        List *list = list_alloc();
        assert(list_set_values(list, 2,  5, 6));
        list_pop_front(list);
        TEST_LIST(list, 1,  6);
        list_pop_front(list);
        TEST_LIST(list, 0);
        assert(list_set_values(list, 2,  5, 6));
        list_pop_back(list);
        TEST_LIST(list, 1,  5);
        list_pop_back(list);
        TEST_LIST(list, 0);
        list_free(list);
    }

    {
        List *list = list_alloc();
        assert(list_set_values(list, 5,  1, 2, 3, 4, 1));
        assert(!list_remove_value(list, 0)); /* not present */
        TEST_LIST(list, 5,  1, 2, 3, 4, 1);
        assert(list_remove_value(list, 4));
        TEST_LIST(list, 4,  1, 2, 3, 1);
        assert(list_remove_value(list, 1));
        TEST_LIST(list, 3,  2, 3, 1);
        assert(list_remove_value(list, 1));
        TEST_LIST(list, 2,  2, 3);
        list_free(list);
    }

    {
        List *list = list_alloc();
        assert(list_set_values(list, 5,  1, 2, 3, 4, 5));
        list_rotate_left(list, 0);
        TEST_LIST(list, 5,  1, 2, 3, 4, 5);
        list_rotate_left(list, 2);
        TEST_LIST(list, 5,  3, 4, 5, 1, 2);
        list_rotate_right(list, 3);
        TEST_LIST(list, 5,  5, 1, 2, 3, 4);
        list_free(list);
    }

    {
        List *list = list_alloc();
        assert(list_set_values(list, 5,  1, 2, 3, 4, 5));
        list_reverse(list);
        TEST_LIST(list, 5,  5, 4, 3, 2, 1);
        list_free(list);
    }

    {
        List *list = list_alloc();
        assert(list_set_values(list, 4,  1, 2, 3, 4));
        list_traverse(list, times_two, NULL);
        TEST_LIST(list, 4,  2, 4, 6, 8);
        int sum = 0;
        list_traverse(list, accumulate, &sum);
        assert(sum == 20);
        list_free(list);
    }

    {
        List *list = list_alloc();
        assert(list_set_values(list, 5,  1, 2, 3, 4, 5));
        list_print(list, stdout);
        puts("");
        list_free(list);
    }
}

And here's my implementation:

#include "list.h"

#include <assert.h>
#include <stdarg.h>
#include <stdio.h>
#include <stdlib.h>

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

struct List {
    Node content;
    size_t size;
};

List *list_alloc(void) {
    List *list = malloc(sizeof *list);
    if (list) {
        list->size = 0;
        list->content.prev = &list->content;
        list->content.next = &list->content;
    }
    return list;
}

static void delete_nodes(List *list)
{
    Node *n = list->content.next;
    while (n && n != &list->content) {
        Node *t = n;
        n = n->next;
        free(t);
    }
}

void list_free(List *list)
{
    if (!list) { return; }
    delete_nodes(list);
    free(list);
}

static bool insert_after(Node *preceding, int value)
{
    Node *new_node = malloc(sizeof *new_node);
    if (!new_node) { return false; };
    Node *following = preceding->next;
    new_node->data = value;
    new_node->next = following;
    new_node->prev = preceding;
    preceding->next = new_node;
    following->prev = new_node;
    return true;
}

bool list_prepend(List *list, int value)
{
    if (!list) { return false; }
    if (!insert_after(&list->content, value)) { return false; }
    ++list->size;
    return true;
}

bool list_append(List *list, int value)
{
    if (!list) { return false; }
    if (!insert_after(list->content.prev, value)) { return false; }
    ++list->size;
    return true;
}

bool list_insert(List *list, size_t position, int value)
{
    if (!list || position > list->size) { return false; }
    Node *n = &list->content;
    while (position--) {
        n = n->next;
    }
    if (!insert_after(n, value)) { return false; }
    ++list->size;
    return true;
}

bool list_set_values(List *list, size_t count, ...)
{
    list_clear(list);

    va_list args;
    va_start(args, count);
    while (count--) {
        if (!list_append(list, va_arg(args, int))) {
            va_end(args);
            return false;
        }
    }
    va_end(args);
    return true;
}

void list_clear(List *list)
{
    if (!list) { return; }
    delete_nodes(list);
    list->size = 0;
    list->content.prev = &list->content;
    list->content.next = &list->content;
}

static void delete_node(List *list, Node *n)
{
    n->prev->next = n->next;
    n->next->prev = n->prev;
    free(n);
    --list->size;
}

void list_pop_front(List *list)
{
    if (!list || !list->size) { return; }
    delete_node(list, list->content.next);
}

void list_pop_back(List *list)
{
    if (!list || !list->size) { return; }
    delete_node(list, list->content.prev);
}

bool list_remove_value(List *list, int value)
{
    Node *n = &list->content;
    while ((n = n->next) != &list->content) {
        if (n->data == value) {
            delete_node(list, n);
            return true;
        }
    }
    return false;               /* not found */
}

void list_rotate_left(List *list, size_t steps)
{
    if (!list) { return; }
    steps %= list->size;
    if (!steps) { return; }
    Node *n = list->content.next;
    while (steps--) {
        n = n->next;
    }
    /* detach the dummy head */
    list->content.next->prev = list->content.prev;
    list->content.prev->next = list->content.next;
    /* and insert it before n */
    list->content.next = n;
    list->content.prev = n->prev;
    n->prev = &list->content;
    list->content.prev->next = &list->content;
}

void list_rotate_right(List *list, size_t steps)
{
    if (!list) { return; }
    steps %= list->size;
    list_rotate_left(list, list->size - steps);
}

void list_reverse(List *list)
{
    Node *n = &list->content;
    do {
        /* swap next and prev pointers */
        Node *tmp = n->next;
        n->next = n->prev;
        n->prev = tmp;
    } while ((n = n->next) != &list->content);
}

void list_traverse(List *list, void (*fun)(int*,void*), void *p)
{
    Node *n = &list->content;
    while ((n = n->next) != &list->content) {
        fun(&n->data, p);
    }
}

static void print_value(int *p, void *s)
{
    FILE *f = s;
    fprintf(f, "%d, ", *p);
}

void list_print(List *list, FILE *f)
{
    fputs("{ ", f);
    list_traverse(list, print_value, f);
    fputs("}", f);
}


/* verify list's invariants and contents */
bool test_list(char const *file, int line,
               const List *list, size_t count, ...)
{
    if (!list) {
        fprintf(stderr, "%s:%d: List is null\n", file, line);
        return false;
    }
    if (list->size != count) {
        fprintf(stderr, "%s:%d: List length is %zu, but expected %zu\n",
                file, line, list->size, count);
        return false;
    }

    va_list args;
    va_start(args, count);

    Node const *node = list->content.next;
    for (size_t i = 0;  i < count;  ++i) {
        if (node->prev->next != node) {
            fprintf(stderr, "%s:%d: Inconsistent 'prev' pointer at element %zu\n",
                    file, line, i);
            va_end(args);
            return false;
        }
        if (node->next->prev != node) {
            fprintf(stderr, "%s:%d: Inconsistent 'next' pointer at element %zu\n",
                    file, line, i);
            va_end(args);
            return false;
        }
        int val = va_arg(args, int);
        if (val != node->data) {
            fprintf(stderr, "%s:%d: list[%zu] contains %d, but expected %d\n",
                    file, line, i, node->data, val);
            va_end(args);
            return false;
        }
        node = node->next;
    }

    va_end(args);
    return true;
}

This isn't totally finished. I recommend you consider adding (at least internally) one or more functions for detaching sub-lists and splicing them elsewhere. That will reduce duplication further.

Answer 4

Just an addition: In your Node structure, you should have "prev" and "next" pointers first, then most of your code can be re-used for linked lists where the data isn't "int" but something else. As it is here, if you have a type T (here: int) and want a "node of T" and a "list of T", you need to duplicate all of your code.