3
\$\begingroup\$

I'd appreciate any and all criticism about this code. I didn't have a particular use case in mind when I wrote it; I just wanted to try implementing linked lists. My comments are not very useful, I think. I'm not a very experienced programmer, so there's probably plenty of things I could improve or fix here.

Here is the header file:

// llist.h
#ifndef LLIST_H_
#define LLIST_H_

struct LList;
typedef struct LList LList;

struct LLNode;
typedef struct LLNode LLNode;

struct LList {
    LLNode *front, *back;
};

struct LLNode {
    void *data;
    LLNode *next;
};

LList* llist_new(LList **self);
void llist_add(LList *self, void *v);
void llist_remove(LList *self, LLNode *node);
void llist_insert(LLNode *node, void *v);
void llist_destroy(LList *self);

#endif

Here is the .c file:

// llist.c
#include <assert.h>
#include <stdlib.h>

#include "llist.h"

// Initialize a new, empty LList, in dynamically allocated memory.
LList *llist_new(LList **self) {
    *self = malloc(sizeof (LList));
    if (self == NULL) { return NULL; }

    (*self)->front = NULL;
    (*self)->back = NULL;

    return *self;
}


// Append a value to the LList.  Creates a new node.
void llist_add(LList *self, void *v) {
    LLNode *node = malloc(sizeof (LLNode));
    assert(node != NULL);

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

    // Put this node at the back of the list.
    if (self->front != NULL) {
        self->back->next = node;
        self->back = node;
    } else {
        self->back = node;
        self->front = node;
    }
}


// Iterate over the LList to locate a node, and then remove it from the list.
void llist_remove(LList *self, LLNode *node) {
    LLNode *iter_node = self->front;
    LLNode *prev_node = NULL;

    while (iter_node != NULL) {
        if (iter_node == node) {
            if (prev_node != NULL) { prev_node->next = iter_node->next; }
            else { self->front = NULL; }
            free(iter_node);
            return;
        }
        prev_node = iter_node;
        iter_node = iter_node->next;
    }

}


// Insert a value after a particular node.
void llist_insert(LLNode *node, void *v) {
    LLNode *next = node->next;
    LLNode *new_node = malloc(sizeof (LLNode));

    new_node->data = v;
    new_node->next = next;

    node->next = new_node;
}


void llist_destroy(LList *self) {
    LLNode *iter_node = self->front;

    while (iter_node != NULL) {
        LLNode *next = iter_node->next;
        free(iter_node);
        iter_node = next;
    }

    free(self);
}
\$\endgroup\$
2
\$\begingroup\$
// Initialize a new, empty LList, in dynamically allocated memory.
LList *llist_new(LList **self) {

Its odd to return the new list as a return value and by reference.

    *self = malloc(sizeof (LList));
    if (self == NULL) { return NULL; }

Doing this check after you've already dereferenced self seems kinda pointless. Maybe you meant *self?

    (*self)->front = NULL;
    (*self)->back = NULL;

    return *self;
}


// Append a value to the LList.  Creates a new node.
void llist_add(LList *self, void *v) {
    LLNode *node = malloc(sizeof (LLNode));
    assert(node != NULL);

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

    // Put this node at the back of the list.
    if (self->front != NULL) {

I'd add a comment to explain what having self->front NULL means.

        self->back->next = node;
        self->back = node;
    } else {
        self->back = node;
        self->front = node;
    }
}


// Iterate over the LList to locate a node, and then remove it from the list.
void llist_remove(LList *self, LLNode *node) {
    LLNode *iter_node = self->front;
    LLNode *prev_node = NULL;

    while (iter_node != NULL) {
        if (iter_node == node) {
            if (prev_node != NULL) { prev_node->next = iter_node->next; }
            else { self->front = NULL; }

I think putting the blocks on the same line like this makes it harder to read. I also think it fail if you delete the first node.

            free(iter_node);
            return;
        }
        prev_node = iter_node;
        iter_node = iter_node->next;
    }

}


// Insert a value after a particular node.
void llist_insert(LLNode *node, void *v) {
    LLNode *next = node->next;
    LLNode *new_node = malloc(sizeof (LLNode));

    new_node->data = v;
    new_node->next = next;

Why did you have the next local variable. It doesn't seem to have helped make the code clearer.

    node->next = new_node;
}


void llist_destroy(LList *self) {
    LLNode *iter_node = self->front;

    while (iter_node != NULL) {
        LLNode *next = iter_node->next;
        free(iter_node);
        iter_node = next;
    }

    free(self);
}
\$\endgroup\$
1
\$\begingroup\$

Seems good:

In llist_new() I would not pass a parameter.
It does not make the interface easier to use but it does add complexity to the tests.

LList *llist_new(LList **self) {

Just make it:

LList *llist_new()

Winsoton pointed out that checking self after the allocation was pointless.
Which is true. But I think you were testing to see if the return value from malloc() was NULL. If this is the case then you have forgotten the de-reference here:

if (self == NULL) { return NULL; }

I think you wanted

if ((*self) == NULL) { return NULL; }
//  ^^ De-reference to check if malloc() worked.

Note: If you change the interface this problems go away since you don't have a ** parameter in the first place.

In the llist_add() If you are going to assert() that the node was created you also need to make sure that the input parameter is valid. As the llist_new() can return NULL if malloc() fails. So you should probably assert on add if self is NULL (You should really chec kon all interfaces to make sure self is not NULL).

void llist_add(LList *self, void *v)
{
    assert(self != NULL);

    LLNode *node = malloc(sizeof (LLNode));
    assert(node != NULL);

I agree with Winston that you should use more explicit indention on the if to make it readable:

        if (prev_node != NULL)
        {   prev_node->next = iter_node->next;
        }
        else
        {   self->front     = iter_node->next;
        }           //        ^^^^^^^^^^^^^^^^ Fix this

Also the assignment should not be to NULL, but should set the new head of the list.

Also the interface to remove elements takes an LLNode pointer. But no other interface provides you with an LLNode pointer. So you are stuck in a chicken and egg situation and not able to use the interface.

void llist_remove(LList *self, LLNode *node) {
\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.