Unidirectional linked list in C

Question

I'm learning algorithms and I wrote the single-directional linked list implementation in C. I need a code review of what can I improve in my code and I want to make sure there are no possible memory leaks.

Code:

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

struct node {
    int data;
    struct node *next;
};

void push_back(struct node *node, int data) {
    while (node->next != NULL) {
        node = node->next;
    }
    node->next = malloc(sizeof(struct node));
    node->next->data = data;
}

int pop_back(struct node *node) {
    int data;
    if (node->next == NULL) {
        data = node->data;
        free(node);
        return data;
    }
    while (node->next->next != NULL) {
        node = node->next;
    }
    data = node->next->data;
    free(node->next);
    node->next = NULL;
    return data;
}

void push_front(struct node **node, int data) {
    struct node *new_node = malloc(sizeof(struct node));
    new_node->data = data;
    new_node->next = *node;
    *node = new_node;
}

int pop_front(struct node **node) {
    struct node *tmp = (*(node))->next;
    int data = (*(node))->data;
    free(*node);
    *node = tmp;
    return data;
}

int contains(struct node *node, int data) {
    while (node->next != NULL) {
        if (node->data == data) {
            return 1;
        }
        node = node->next;
    }
    return 0;
}

int count(struct node *node, int data) {
    int count = 0;
    while (node->next != NULL) {
        if (node->data == data) {
            ++count;
        }
    }
    return count;
}

int get_elem(struct node *node, int offset) {
    int i = 0;
    while (node->next != NULL && i < offset) {
        node = node->next;
        ++i;
    }
    return node->data;
}

struct node *init_list(int data) {
    struct node *list = malloc(sizeof(struct node));
    list->data = data;
    list->next = NULL;
    return list;
}

void free_list(struct node *node) {
    while (node->next != NULL) {
        struct node *tmp = node;
        node = node->next;
        free(tmp);
    }
}

void print_list(struct node *node) {
    int i = 0;
    while (node != NULL) {
        printf("offset %d: %d\n", i, node->data);
        node = node->next;
        ++i;
    }
}

int main(int argc, char *argv[]) {
    struct node *node = init_list(10);
    push_back(node, 20);
    push_back(node, 30);
    push_back(node, 40);
    print_list(node);
    pop_back(node);
    print_list(node);
    // test other functions
    free_list(node);
    return 0;
}

Answer 1

Bug

Test code better.

int count(struct node *node, int data) {
    int count = 0;
    while (node->next != NULL) {
        if (node->data == data) {
            ++count;
        } 
        // !! Missing code to advance pointer!!
    }
    return count;
}

Detect wrong usage

A bit of a hack, yet useful in debug mode.

Before freeing, consider trashing memory to more likely cause trouble with later freed memory use.

#ifndef NDEBUG
node->data = 42;
node->next = some_bad_pointer;  // e.g. (void*)0xDEADBEEF
#endif
free(node);

Avoid wrong sizing

Do not allocate to the size of the type. Allocate to the size of the refenced data. Easier to code right, review and maintain.

// node->next = malloc(sizeof(struct node));
node->next = malloc(sizeof node->next[0]);

List may be empty

int pop_front(struct node **node) (and others) assumes *node is not NULL. Avoid that.

int pop_front(struct node **node) {
    if (*node == NULL) {
      ; // Handle error with TBD code
    } 
    ...

When list does not change, use const

// int count(struct node *node, int data) {
int count(const struct node *node, int data) {

Why int length?

For the list length, why int? int is at least reasonable, yet unsigned, size_t deserve consideration.

Consider bool for true/false like code

bool conveys the function's goal better than int.

// int contains(struct node *node, int data) {
#include <stdbool.h>
bool contains(struct node *node, int data) {

Scattered name space

Code uses names like node, contains, count which are certain to collide with other code. Carve out a corner of the name space perhaps with zp_node, zp_contains, zp_count, zp_... .

Next step

Segment code into a .c, .h and main.c files.

Example ll.h. Note the members of struct ll_node_s are not coded here - only in the ll.c file.

#ifndef LL
#define LL 1

  typedef struct ll_node_s ll_node;
  int ll_pop_back(ll_node *node);
  void ll_push_back(ll_node *node, int data);
  ...

#endif

Edit: push_back(), pop_back() performance improvement

Both functions walk the list taking O(n) time. Yet a single-linked list can employ O(1) for one of those without incurring more storage.

Example: instead of the link-list pointing to the first node and the last node pointing to NULL, have the link-list point to the last node and the last node point to the first. With the circular linked-list, the end is determined by matching with the start.

push_back() is then like push_front(): O(1). They differ on updating the linked-list pointer.

The real cost to this approach is that to find the front requires an extra -> operation.

Side benefit: Cost of peek_back() (report the end data) is O(1) rather than O(n). peek_front() remains O(1).

Answer 2

Think about the failure cases. For example:

struct node *list = malloc(sizeof(struct node));
list->data = data;
list->next = NULL;
return list;

If malloc() fails, then list contains a null pointer, and accessing list->data and list->next is Undefined Behaviour (meaning that we can make no statements about what the code does).

We need to be defensive here, for example:

struct node *list = malloc(sizeof *list);
if (list) {
    list->data = data;
    list->next = NULL;
}
return list;

And we also need to be defensive where we call the function, since it can return a null pointer:

int main(void)
{
    struct node *node = init_list(10);
    if (!node) {
        return EXIT_FAILURE;
    }
    push_back(node, 20);
    ⋮

Answer 3

You might consider to abbreviate struct node with a typedef name:

typedef struct node {
    int data;
    struct node *next;
} *list;

The above would make list a struct node *. Though often one sees the typedef without pointer and equal to the struct name.

malloc's result must be tested - null if out-of-memory.

Apart from that the following are perfect:

void push_front(struct node **node, int data) { ...

int pop_front(struct node **node) {
    struct node *tmp = (*node)->next;
    int data = (*node)->data;
    free(*node);
    *node = tmp;
    return data;
}

The other functions like push_back suffer from not allowed to be called for an empty list, a null node. It seems you want to always init lists with one element at least. Not a good idea.

void push_back(struct node **node, int data) {
    while (*node != NULL) {
        node = &(*node)->next;
    }
    struct node *new_node = malloc(sizeof(struct node));
    new_node->data = data;
    new_node->next = *node;
    *node = new_node;
}

In push_back the variable node is either an alias of the passed list pointer, or the alias of a next field.

int pop_back(struct node **node) {
    if (*node == NULL) {
        return 0; // Error
    }
    while ((*node)->next != NULL) {
        node = &(*node)->next;
    }
    int data = (*node)->data;
    free(*node);
    *node = NULL;
    return data;
}

Again using aliases pop_back is simple.

bool contains(struct node *node, int data) {
    while (node != NULL) {
        if (node->data == data) {
            return true;
        }
        node = node->next;
    }
    return false;
}

It is a matter of taste, but booleans add so much more semantic information to code, use it.

int count(struct node *node, int data) {
    int count = 0;
    while (node != NULL) {
        if (node->data == data) {
            ++count;
        }
        node = node->next;
    }
    return count;
}

In count there again is a next too much. The same for get_elem.

int get_elem(struct node *node, int offset) {
    int i = 0;
    while (node != NULL && i < offset) {
        node = node->next;
        ++i;
    }
    if (node == NULL) {
        ...
    }
    return node->data;
}

struct node *init_list() {
    return null;
}

void free_list(struct node **node) {
    while (*node != NULL) {
        struct node *tmp = node;
        *node = &(*node)->next;
        free(tmp);
    }
}

free_list can have its passed variable set to NULL, so there is no dangling pointer.

void print_list(struct node *node) {
    puts("[");
    for (int i = 0; node != NULL; ++i) {
        if (i != 0) {
            puts(", ");
        }
        printf("%d: %d", i, node->data);
        node = node->next;
    }
    printf("]\n");
}

The list printing should print something for the empty list. I made it a one liner.

Answer 4

A serious error everybody appears to fix without comment:

push_back() allocates memory and forgets to initialize some of it. Specifically, it fails to write: node->next->next = NULL;

The reason your program has worked so far is that the OS typically zero fills new memory for you. If you allocate a lot, then free it, and then use push_back(), later operations will fail.

Answer 5

Interfaces

Consider the work that your contains function does compared to the information it returns.

It finds the first position that has the value in question. But all it effectively returns is true/false. What if the user wanted to modify the element at that position? Or splice it out?

It would be more useful (satisfy more use cases) if it simply returns the pointer to the element that it landed on, and NULL when it is not found. It would then be more appropriate to call it find or similar.

It would then be possible to use the result of find with a subsequent call to find in order to find the next position with that value, etc.

If you really wanted to, you could then implement contains using find, but personally I wouldn't bother.

PS. By the same token, get_elem should also return the pointer to the node, not the data on the node. This will also give you the choice of how to handle when offset is greater than the size of the list -- at the moment it returns the data in the last node, which some might say is more gracious than crashing, but it could easily be a subtle, undetected bug for a long time.

Assumptions

I recommend that you #include <assert.h> and liberally assert the preconditions and postconditions of your functions.

Any function that implicitly assumes that the node parameter is non-NULL should have assert(node); right at the start.

get_elem should have assert(offset >= 0);.

Answer 6

Some suggestions follow.

1/ Comment your code. It won't affect at all how the code does its job (unless you do something silly like comment out a vital line of code), but it will affect the ability to maintain that code. The programmers that follow you may well praise or curse your name depending on this.

2/ Since you have a few operations that work on the end of the list, you can speed things up by caching that somewhere. I suggest that the best way to do this is to have a list data structure, separate from the node one, something like:

struct node {
    int data; // or whatever the actual payload is.
    struct node *next;
}
struct list {
    struct node *first;
    struct node *last;
    size_t count;
}

This will allow you to quickly get at the last element for push_back/pop_back (but see next item). Caching the length in the list structure will also turn the count() call into an O(1) operation instead of O(n).

It's also more logical since it makes little sense to call pop_back() passing a node that isn't the last node - these are list operations, not node ones. A classic example of wrongness with the current method is if you call count() passing in a node that's not the head. It will only count items from there until the end.

Now that may be what you intended but the lack of comments (see point 1) do not make it clear.

3/ Consider using a doubly linked list even if you think you only need a singly linked one. It makes insertions and deletions a lot easier, not needing a list traversal to find a node's predecessor for example.

Granted it's a little wasteful to have two pointers for every integer in the list but that's also true of a singly linked list. In general, list payloads tend to be more substantial.

4/ Things fail, allow for that. For example, you should be detecting malloc failure and handling it. In addition, you should be indicating to the caller if they do something silly, like:

• popping on an empty list;
• passing in a NULL pointer;
• trying to retrieve an index beyond the end of the list.

The functions that currently return void are easy to fix, you simply have them return an error code instead. The trickier ones are those that already return something useful (and, of course, limited to those that can actually fail), these need to be able to indicate failure and return that useful thing.

5/ Consider separating your monolithic code into a form more usable by a client. That means providing stuff in a header file for the client to include, and removing test/exercise code into a separate source file so it's not included in clients that don't need it.

6/ Better typing. C has had a proper boolean type for a while now, and size_t is a more natural fit for counting things (you'll never have -42 items in a list, for example).

7/ Sit down with a pen and paper and actually "run" your code in certain scenarios. This will catch any errors in your logic related to missing a step, such as forgetting to set or change a pointer in the mode.

Alternatively, add a debug function that prints out the internal structures in such a way that a core dump will not prevent you from seeing it. That often involves flushing the data at multiple levels (the fflush/fsync sequence).

---

With all that taken into account, this code is one example of how to do it. First, the header file, separate for reasons explained above, and with documentation for clients.

Note the comment at the top about preferring an opaque pointer to enforce encapsulation. I haven't done that in this answer but you can look here to get an idea on how to do it.

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

// Do NOT use these structures from outside (they really
// should be opaque). All access should be via the API
// functions only.

struct s_node {
    int data;               // Payload.
    struct s_node *next;    // NULL for tail.
    struct s_node *prev;    // NULL for head.
};

struct s_list {
    size_t count;           // Other fields valid only if count > 0.
    struct s_node *first;
    struct s_node *last;
};

// This is the start of the public API stuff that clients can use.
// Needless to say, all functions below receiving a list must get a
// properly created one (from init_list). You can also call
// free_list(NULL) to mirror free(NULL)..

enum e_error {
    OKAY = 0,   // Operation succeeded.
    NO_MEMORY,  // Allocation failure.
    EMPTY_LIST, // Cannot do to empty list.
    BAD_INDEX,  // Index beyond list length.
};

// Returns new empty list object. Return NULL if no memory.
    struct s_list *init_list();

// Frees everything to do with a list. No errors possible.
    void free_list(struct s_list *list);

// Places an item before the current first item, or adds to the list
// if empty. Can return NO_MEM or OK.
    enum e_error push_front(struct s_list *list, int data);

// Places an item after the current last item, or adds to the list
// if empty. Can return NO_MEM or OK.
    enum e_error push_back(struct s_list *list, int data);

// Pops the item from the front of list into int pointer, NULL
// means throw away. Can return EMPTY_LIST or OK.
    enum e_error pop_front(struct s_list *list, int *p_data);

// Pops the item from the back of list into int pointer, NULL
// means throw away. Can return EMPTY_LIST or OK.
    enum e_error pop_back(struct s_list *list, int *p_data);

// Returns true if value found in list, false ortherwise.
    bool contains(struct s_list *list, int data);

// Returns number of nodes is in list.
    size_t count(struct s_list *list);

// Returns number of times a specific value is in list.
    size_t count_with(struct s_list *list, int data);

// Gives the value at an index. Can return BEYOND or OK.
    enum e_error get_elem_at(struct s_list *list, size_t offset, int *p_data);

Next, the code itself. Modifications are mostly listed in the numbered points at the start of this answer but I've also changed count() into count_with() and provided a count() that counts all elements regardless of value. That's so you can see the value of the caching the count in the list structure.

#include <stdlib.h>

#include "prog.h"

struct s_list *init_list(void) {
    // Allocate new list, failing if no memory.

    struct s_list *list = malloc(sizeof(struct s_list));
    if (list == NULL) {
        return NULL;
    }

    // Mark list as empty.

    list->count = 0;
    return list;
}

void free_list(struct s_list *list) {
    // Allow NULL input as no-operation.

    if (list == NULL) {
        return;
    }

    // First, free all nodes (count is in control, not first).

    if (list->count > 0) {
        struct s_node *node = list->first;
        while (node != NULL) {
            struct s_node *corpse_node = node;
            node = node->next;
            free(corpse_node);
        }
    }

    // Then free the list itself.

    free(list);
}

enum e_error push_front(struct s_list *list, int data) {
    // Allocate new node, failing if no memory.

    struct s_node *node = malloc(sizeof(struct s_node));
    if (node == NULL) {
        return NO_MEMORY;
    }

    // These are identical for empty/non-empty lists.

    node->data = data;
    node->prev = NULL;

    // Simple case if list currently empty.

    if (list->count == 0) {
        node->next = NULL;
        list->count = 1;
        list->first = list->last = node;

        return OKAY;
    }

    // List has a first element so insert before it.

    node->next = list->first;
    list->first->prev = node;
    list->first = node;
    list->count++;

    return OKAY;
}

enum e_error push_back(struct s_list *list, int data) {
    // Allocate new node, failing if no memory.

    struct s_node *node = malloc(sizeof(struct s_node));
    if (node == NULL) {
        return NO_MEMORY;
    }

    // These are identical for empty/non-empty lists.

    node->data = data;
    node->next = NULL;

    // Simple case if list currently empty.

    if (list->count == 0) {
        node->prev = NULL;
        list->count = 1;
        list->first = list->last = node;

        return OKAY;
    }

    // List has a last element so insert after it.

    node->prev = list->last;
    list->last->next = node;
    list->last = node;
    list->count++;

    return OKAY;
}

enum e_error pop_front(struct s_list *list, int *p_data) {
    // Not allowed on empty list.

    if (list->count == 0) {
        return EMPTY_LIST;
    }

    // Save stuff needed to free.

    struct s_node *node = list->first;
    if (p_data != NULL) {
        *p_data = node->data;
    }

    // Adjust list.

    list->first = node->next;
    list->first->prev = NULL;
    list->count--;

    // Free and return.

    free(node);

    return OKAY;
}

enum e_error pop_back(struct s_list *list, int *p_data) {
    // Not allowed on empty list.

    if (list->count == 0) {
        return EMPTY_LIST;
    }

    // Save stuff needed to free.

    struct s_node *node = list->last;
    if (p_data != NULL) {
        *p_data = node->data;
    }

    // Adjust list.

    list->last = node->prev;
    list->last->next = NULL;
    list->count--;

    // Free and return.

    free(node);

    return OKAY;
}

bool contains(struct s_list *list, int data) {
    // Count is in control.

    if (list->count == 0) {
        return false;
    }

    // Check each mode, return immediately if found.

    struct s_node *node = list->first;
    while (node->next != NULL) {
        if (node->data == data) {
            return true;
        }
        node = node->next;
    }
    return false;
}

size_t count(struct s_list *list) {
    // Cached info, no need to traverse list.

    return list->count;
}

size_t count_with(struct s_list *list, int data) {
    // Count is in control.

    if (list->count == 0) {
        return 0;
    }

    // Check each mode, counting matches.

    struct s_node *node = list->first;
    size_t count = 0;
    while (node->next != NULL) {
        if (node->data == data) {
            ++count;
        }
    }

    return count;
}

enum e_error get_elem_at(struct s_list *list, size_t offset, int *p_data) {
    // Count limits what you can get to.

    if (offset >= list->count) {
        return BAD_INDEX;
    }

    // Find node at given index and return its data.

    struct s_node *node = list->first;
    while (offset > 0) {
        node = node->next;
        offset--;
    }

    *p_data = node->data;

    return OKAY;
}

Then the modified test program, with the mentioned debugging function to check for things like invalid pointers and such (ensuring a core dump doesn't happen before all output is fully flushed).

#define _POSIX_C_SOURCE 200809L

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

#include "prog.h"

void debug(char *desc, struct s_list *list) {
    printf("===== List @ %p (%s)\n", (void*)list, desc);
    fflush(stdout); fsync(fileno(stdout));

    printf("    count = %zu\n", list->count);
    fflush(stdout); fsync(fileno(stdout));

    printf("    first = %p\n", (void*)(list->first));
    fflush(stdout); fsync(fileno(stdout));

    printf("    last  = %p\n", (void*)(list->last));
    fflush(stdout); fsync(fileno(stdout));

    struct s_node * node = list->first;
    while (node != NULL) {
        printf("    Node @ %p\n", (void*)node);
        fflush(stdout); fsync(fileno(stdout));

        printf("        data = %d\n", node->data);
        fflush(stdout); fsync(fileno(stdout));

        printf("        prev = %p\n", (void*)(node->prev));
        fflush(stdout); fsync(fileno(stdout));

        printf("        next  = %p\n", (void*)(node->next));
        fflush(stdout); fsync(fileno(stdout));
        node = node->next;
    }

    printf("-----\n");
    fflush(stdout); fsync(fileno(stdout));
}

void print_list(struct s_list *list) {
    int data;
    size_t i = 0;

    while (get_elem_at(list, i, &data) == OKAY) {
        printf("offset %zu: %d\n", i++, data);
    }
}

void check_err(enum e_error err_code, char *desc) {
    if (err_code == OKAY) {
        return;
    }

    printf("Error %d while %s\n", err_code, desc);
}

int main(int argc, char *argv[]) {
    int data;

    struct s_list *list = init_list();
    debug("after init", list);
    if (list != NULL) {
        check_err(push_back(list, 10), "pushing back 10");
        debug("after push 10", list);

        check_err(push_back(list, 20), "pushing back 20");
        debug("after push 20", list);

        check_err(push_back(list, 30), "pushing back 30");
        debug("after push 30", list);

        check_err(push_back(list, 40), "pushing back 40");
        debug("after push 40", list);

        print_list(list);

        check_err(pop_back(list, &data), "popping back");
        debug("after pop 40", list);

        print_list(list);

        free_list(list);
    }

    return 0;
}

And, finally, the output of that modified test program so you can see the detailed structures after each modification:

===== List @ 0x555a3e7502a0 (after init)
    count = 0
    first = (nil)
    last  = (nil)
-----
===== List @ 0x555a3e7502a0 (after push 10)
    count = 1
    first = 0x555a3e7506d0
    last  = 0x555a3e7506d0
    Node @ 0x555a3e7506d0
        data = 10
        prev = (nil)
        next  = (nil)
-----
===== List @ 0x555a3e7502a0 (after push 20)
    count = 2
    first = 0x555a3e7506d0
    last  = 0x555a3e7506f0
    Node @ 0x555a3e7506d0
        data = 10
        prev = (nil)
        next  = 0x555a3e7506f0
    Node @ 0x555a3e7506f0
        data = 20
        prev = 0x555a3e7506d0
        next  = (nil)
-----
===== List @ 0x555a3e7502a0 (after push 30)
    count = 3
    first = 0x555a3e7506d0
    last  = 0x555a3e750710
    Node @ 0x555a3e7506d0
        data = 10
        prev = (nil)
        next  = 0x555a3e7506f0
    Node @ 0x555a3e7506f0
        data = 20
        prev = 0x555a3e7506d0
        next  = 0x555a3e750710
    Node @ 0x555a3e750710
        data = 30
        prev = 0x555a3e7506f0
        next  = (nil)
-----
===== List @ 0x555a3e7502a0 (after push 40)
    count = 4
    first = 0x555a3e7506d0
    last  = 0x555a3e750730
    Node @ 0x555a3e7506d0
        data = 10
        prev = (nil)
        next  = 0x555a3e7506f0
    Node @ 0x555a3e7506f0
        data = 20
        prev = 0x555a3e7506d0
        next  = 0x555a3e750710
    Node @ 0x555a3e750710
        data = 30
        prev = 0x555a3e7506f0
        next  = 0x555a3e750730
    Node @ 0x555a3e750730
        data = 40
        prev = 0x555a3e750710
        next  = (nil)
-----
offset 0: 10
offset 1: 20
offset 2: 30
offset 3: 40
===== List @ 0x555a3e7502a0 (after pop 40)
    count = 3
    first = 0x555a3e7506d0
    last  = 0x555a3e750710
    Node @ 0x555a3e7506d0
        data = 10
        prev = (nil)
        next  = 0x555a3e7506f0
    Node @ 0x555a3e7506f0
        data = 20
        prev = 0x555a3e7506d0
        next  = 0x555a3e750710
    Node @ 0x555a3e750710
        data = 30
        prev = 0x555a3e7506f0
        next  = (nil)
-----
offset 0: 10
offset 1: 20
offset 2: 30

Answer 7

make sure there are no possible memory leaks
Advice on testing:
Have allocation & disposal functions increasing & decreasing an instance count as appropriate.
Check, at least, final total after last disposal.

Write push_back() (and init_list() if not dropping that) in terms of push_front()

void push_back(struct node *node, int data) {
    while (node->next != NULL) {
        node = node->next;
    }
    push_front(&(node->next), data);
}

struct node *init_list(int data) {
    struct node *list = NULL;
    push_front(&list, data);

    return list;
}