Singly Linked List

Question

I am a self taught programmer and, while I understand data structures at a theoretical level (as well as through optimizing my own code), I have never actually taken the time to write my own implementation of all the major ones.

So, here is my linked list. I would appreciate any feedback you guys can offer to me, especially when it comes to cleaner/faster/more idiomatic way of implementing some of these basic algorithms (for example, insert). I didn't look at any reference material because I wanted to see how close I would get without help. As such, I'm sure there are probably simpler ways of doing some things that I overlooked.

Also note that I have not optimized any of this; this is simply a first pass, took about an hour. I will be benchmarking this (and the others) at a later time, but like I said, space and time improvements are welcome.

linked_list.h

#ifndef LINKED_LIST_H
#define LINKED_LIST_H

#include <stddef.h>

typedef struct _node {
    int value;
    struct _node* next;
} node;

typedef struct _llist {
    node* head;
    node* tail;
} llist;

void init_node( node** new_node, int value );
void init_llist( llist** list );
size_t len( llist* list );
void push_back( llist* list, int value );
void push_front( llist* list, int value );
void insert( llist* list, int index, int value );
node* find( llist* list, int value );
void free_llist( llist* list );
void print_llist( llist* list );

#endif

linked_list.c

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

void init_node( node** new_node, int value ) {
    *new_node = (node*)malloc( sizeof(node) );
    (*new_node)->value = value;
    (*new_node)->next = NULL;
}

void init_llist( llist** list ) {
    *list = (llist*)malloc( sizeof(llist) );
    (*list)->head = NULL;
    (*list)->tail = NULL;
}

void push_back( llist* list, int value ) {
    node* new_node;
    init_node( &new_node, value );
    if( !list->head ) {
        /* empty list */
        list->head = new_node;
        list->tail = list->head;
    }
    else {
        list->tail->next = new_node;
        list->tail = new_node;
    }
}

void push_front( llist* list, int value ) {
    node* new_head;
    init_node( &new_head, value );
    new_head->next = list->head;
    list->head = new_head;
    if( !list->tail ) {
        /* was an empty list */
        list->tail = list->head;
    }
}

void insert( llist* list, int index, int value ) {
    int cur_idx = 0;
    node* new_node = NULL;
    node* prev_node = NULL;
    node* cur_node = list->head;    

    if( index < 0 ) return;
    if( index == 0 ) {
        push_front( list, value );
        return;
    }

    /* not sure what I should do here.
       should I hide the 'error' or force
       an assert to fail if the caller 
       tries to insert into an empty list 
       or an invalid position? */
    if( !cur_node ) {
        init_node( &cur_node, value );
        list->head = list->tail = cur_node;
        return;
    }

    while( cur_node && cur_idx < index ) {
        ++cur_idx;
        prev_node = cur_node;
        cur_node = cur_node->next;      
    }

    init_node( &new_node, value );

prev_node->next = new_node;    
    new_node->next = cur_node;
    if( !cur_node ) {
        /* new tail node, end of list */
        list->tail = new_node;
    }
}

node* find( llist* list, int value ) {
    node* tmp = list->head;
    while( tmp != NULL && tmp->value != value ) {
        tmp = tmp->next;
    }

    return tmp;
}

size_t len( llist* list ) {
    size_t len = 0;
    node* current = list->head;
    while( current ) {
        ++len;
        current = current->next;
    }

    return len;
}

void free_llist( llist* list ) {
    node* current = list->head;
    while( current ) {
        node* tmp = current->next;
        free( current );
        current = tmp;      
    }

    list->head = list->tail = NULL;
}

void print_llist( llist* list ) {
    node* cur = list->head;
    while( cur ) {
        printf( "%d\r\n", cur->value );
        cur = cur->next;
    }
}

And some trivial unit tests that should all pass, probably should be more comprehensive:

#include "linked_list.h"
#include <stdio.h>
#include <assert.h>

void test_push_back();
void test_push_front();
void test_len();
void test_insert();
void test_find();

int main( int argc, char* argv[] ) {
    test_push_back();
    test_push_front();
    test_len();
    test_insert();
    test_find();
    puts( "All Passed" );
    return 0;
}

void test_push_back() {
    llist* list;
    node* current;
    int i;
    int start = 0;
    int count = 100;
    init_llist( &list );

    for( i = start; i < count; ++i ) {
        push_back( list, i );
    }

    current = list->head;
    for( i = start; current; ++i ) {
        assert( current->value == i );
        current = current->next;
    }

    free_llist( list ); 
}

void test_push_front() {
    llist* list;
    node* current;
    int i;
    int start = 0;
    int count = 100;
    init_llist( &list );

    for( i = start; i < count; ++i ) {
        push_front( list, i );
    }

    current = list->head;
    for( i = count - 1; current; --i ) {
        assert( current->value == i );
        current = current->next;
    }

    free_llist( list ); 
}

void test_len() { 
    llist* list;
    init_llist( &list );

    assert( len( list ) == 0 );
    push_back( list, 1 );
    assert( len( list ) == 1 );

    free_llist( list );
    assert( len( list ) == 0 );
}

void test_insert() {
    llist* list;
    init_llist( &list );

    /* insert into empty list */
    insert( list, 0, 1 );
    assert( list->head->value == 1 && list->tail->value == 1 );

    /* insert at the end */
    insert( list, 1, 3 );
    assert( list->tail->value == 3 );

    /* insert in the middle */
    insert( list, 1, 2 );
    assert( list->head->next->value == 2 );

    free_llist( list );
    init_llist( &list );

    push_back( list, 1 );
    push_back( list, 2 );
    push_back( list, 3 );

    /* insert to front of already populated list */
    insert( list, 0, -1 );
    assert( list->head->value == -1 );
    assert( list->tail->value == 3 );

    /* invalid index, too large, place at end */
    insert( list, 100, 100 );
    assert( list->tail->value == 100 );

    free_llist( list );
}

void test_find() {
    llist* list;
    node* found_node;
    init_llist( &list );

    /* not present, shoudl return NULL */
    found_node = find( list, 0 );
    assert( found_node == NULL );

    push_back( list, 1 );
    push_back( list, 2 );
    push_back( list, 3 );

    found_node = find( list, 1 );
    assert( found_node == list->head && found_node->value == 1 );

    found_node = find( list, 2 );
    assert( found_node->value == 2 );

    found_node = find( list, 3 );
    assert( found_node == list->tail && found_node->value == 3 );

    free_llist( list ); 
}

Answer 1

Your question is tagged c, and your file ends in .c. So here's some thoughts from that angle:

• Don't bother casting void * to another pointer type. This is a C++ thing. In C, void * can be implicitly cast to any pointer type.

• There is no such thing as a namespace, so don't use collision-prone names like node or len(). Add some kind of prefix.

• malloc can fail. You will want to bubble up that error status. All your functions that end up calling malloc further down the stack will need a means to return error status as well. Typically the way to do this is return NULL (if your function returns a pointer type) or make the function return bool (<stdbool.h> in C99) or int and have some convention where a certain value means failure. (In POSIX it's typically int returning 0 on success. Windows will typically have a boolean where nonzero means success. Returning error codes is also popular.)

Some other thoughts:

• Consider an alternate allocation scheme for struct llist. Personally I would prefer the structure itself (not the nodes of course) to be caller-allocated. Is it worth doing a malloc for something only the size of two pointers in llist_init? I would say no. Further, consider the memory layout if you want to include a list inside a structure: why bother having a pointer to it when you can just have the struct llist be a member of the larger structure?

• The use of whitespace seems inconsistent. At times you put an extra newline between declarations and statements, and at times you don't. It's of course subjective which one of these you choose (I would rather more space personally), but it's important to be consistent.

Answer 2

My first bug bear is identifiers should not begin with an underscore:

typedef struct _node {
typedef struct _llist {

See: what-are-the-rules-about-using-an-underscore-in-a-c-identifier

Rather than having any output parameters I think it is easier to see behavior by returning results:

node* init_node(int value )
{
    node* new_node  = (node*)malloc( sizeof(node) );
    new_node->value = value;
    new_node->next  = NULL;

    return new_node;
}

/* not sure what I should do here. should I hide the 'error' or force an assert to fail if the caller tries to insert into an empty list or an invalid position? */

I don't think an assert is appropriate as that forces the program to exit.
But some form of error indication may be useful. Or you can document the behavior and decide what it done. I personally would say (in the documentation) an insert where index is beyond the end of the array is equivalent to a push_back() and leave it at that. Then inserting into an empty list and beyond the end have the same behavior.

Then length as currently implemented:

size_t len( llist* list ) {

Is actually an O(n) operation. It would be a simple to make this O(1) and store the size.

The method that frees the list does not free up the container object:

void free_llist( llist* list ) // frees all the nodes.

I would also expect it to free the object allocated by init_llist.