1
\$\begingroup\$

I'm learning Algorithms, Data structures and C.This is an exercise set by myself to implement a simple linked list data structure with insertion algorithm in C, to better understand the subject.

All answers are highly appreciated, here's the code.

linkedlist.h / linkedlist.c

#ifndef LINKEDLIST_H_
#define LINKEDLIST_H_

typedef struct Node {
    int value;
    struct Node *prev_node;
    struct Node *next_node;
}NodeT;

typedef struct Token {
    struct Node *head_node;
    struct Node *tail_node;
}TokenT;

void init_node_iterators( NodeT *node );
void init_token_iterators( TokenT *token );
void create_node( TokenT *token, int value );
void add_node( TokenT *token, NodeT *new_node );
void clean_heap_memory( TokenT *token );
int  check_heap_space( NodeT *node );

#endif

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

void init_node_iterators( NodeT *node )
{
    node->prev_node = NULL;
    node->next_node = NULL;
}

void init_token_iterators( TokenT *token )
{
    token->head_node = NULL;
    token->tail_node = NULL;
}

void add_node( TokenT *token, NodeT *new_node )
{ //  Add the Node to linked list
    if ( token->head_node == NULL ){

        token->head_node = new_node;
        token->tail_node = new_node;

    }else{

        token->tail_node->next_node = new_node;
        new_node->prev_node = token->tail_node;
        token->tail_node = new_node;
    }
}

void create_node( TokenT *token, int value )
{ /* Create and add new node to the linked list,
     if there is enogh space on heap */

    NodeT *new_node = (NodeT*)malloc(sizeof(NodeT));

    if ( check_heap_space(new_node) ){

        new_node->value = value;
        init_node_iterators( new_node );
        add_node( token, new_node );

    }else 
        puts("Cant allocate more memory on Heap\n");
}

void clean_heap_memory( TokenT *token )
{ // Clean Heap memory for each node in the linked list

    TokenT *iterator = token;

    /* As long as head node is pointing to a next node
       - Set the head node to the next node
       - Clear the previous node
       - At the end of the loop clear the head node */

    while( iterator->head_node->next_node != NULL ){

        iterator->head_node = iterator->head_node->next_node;
        free( iterator->head_node->prev_node );
    }

    free( iterator->head_node );
}

int check_heap_space( NodeT *node )
{ /* If malloc returns a NULL pointer return false(0),
     in any other case return true(1) */
    if ( node == NULL )
        return 0;
    return 1;
}

test.h / test.c

#ifndef TEST_H_
#define TEST_H_

typedef struct {
    int value;
    int node_count;
    int linked_list_size;
    int node_quantity;
}TestConfig;

void test( TestConfig *config );
void print_node( NodeT *node, TestConfig *config );

#endif

#include <stdio.h>
#include "linkedlist.h"
#include "test.h"

void test( TestConfig *config )
{
  //Declare and Initialize tokens
    TokenT token;
    init_token_iterators(&token);

  /*created a node and increased node count, 
    value and linked list size  before a loop.  */
    create_node(&token, config->value);
    config->node_count++;
    config->value++;
    config->linked_list_size += sizeof(NodeT);

  /*Loop counter is (1) because one node is created.
    At the start of the loop created a new node, therefore having
    two nodes at first loop iteration.
    Now tail_node->prev_node->next_node is pointing to last node
    print the information about tail_node->prev_node.
    Increase the value, node_count and linked list size.
    Do this until loop condition is true. */

  for( int c = 1; c < config->node_quantity; ++c )
  {

      create_node(&token, config->value );
      print_node( token.tail_node->prev_node, config );

      config->value++;
      config->node_count++;
      config->linked_list_size += sizeof(NodeT);
  } 

  //Print the last node
  print_node( token.tail_node, config );

  clean_heap_memory(&token);
  puts("--------------------------------\n");
  printf("[ Cleaned %ib on heap memory ]\n\n", 
      config->linked_list_size);
}

void print_node( NodeT *node, TestConfig *config )
{ 

    printf("Node(%i) \n", config->node_count );
    puts("--------------------------------\n");

    printf("   [THIS] mem-address: %p\n", node );
    printf("   [PREV] mem-address: %p\n", node->prev_node );
    printf("   [NEXT] mem-address: %p\n", node->next_node );
    printf("  [VALUE] %i\n", node->value );
    printf(" [LLSIZE] %ib\n\n", config->linked_list_size );

}

main.c

#include <stdio.h>
#include <stdlib.h>
#include "linkedlist.h"
#include "test.h"


int main( int argc, char *argv[] )
{
    TestConfig config = { 5, 0, 0, 0 };

    char *pointer;
    long int result;

    //argv[1] is need to set the number of nodes to create
    if ( argv[1] ) {
        // Try to convert argv[1] string to long int
        result = strtol( argv[1], &pointer, 10 );

        /*If the conversion is successful set number 
          of nodes to create to result and run test */
        if ( result ){
            config.node_quantity = result;
            test(&config );
        }else
            puts("Cannot convert string to number");
    }else
        puts("Program needs an argument - argv[1] of type(int)");

    return 0;
}

What i'm interested the most, from answers:

  • Naming convention of the code.
  • I'm freeing the memory the right way ( clean_heap_memory() )
  • Practice applied to the code. Is it good or bad ?
  • Your professional opinion of the code
  • Things i can use to improve the above code.
\$\endgroup\$
2
\$\begingroup\$

Here are some things that may help you improve your code.

Use better variable names

The variable name result is OK, but the name pointer is not. The first name explains something about what the variable means within the context of the code, but the latter adds no useful information. Similarly NodeT is a reasonable type name but TokenT is not as good.

Understand library functions

The above-mentioned pointer variable can simply and easily be eliminated. The only use is currently this:

result = strtol( argv[1], &pointer, 10 );

Howver, if you don't need it, neither does the library. It will just as happily accept the NULL pointer:

result = strtol( argv[1], NULL, 10 );

Use const references where practical

The code currently has this function definition:

void print_node( NodeT *node, TestConfig *config );

However, the print_node function doesn't (and shouldn't) alter either passed structure, so it should instead be declared as:

void print_node( const NodeT *node, const TestConfig *config );

Be careful with pointers

The print_node function starts with this (with the above suggestion applied):

void print_node( const NodeT *node, const TestConfig *config ) { 
    printf("Node(%i) \n", config->node_count );

However, what if config is NULL? This will probably result in a program crash. There are two ways to deal with this, and I advocate doing both. First, check for NULL for both pointers and simply return without printing anything if either pointer is NULL:

if (node == NULL || config == NULL) {
    return;
}

The other thing to do is the following suggestion.

Make functions static where practical

There does not appear to be much reason to call print_node except from within test because it relies on the latter's TestConfig structure. For that reason, I'd advise making it static and omitting it from test.h. This will make the function invisible outside that translation unit (that is, the test.c file) and means that only other functions in that file may call it. For that reason, you may be able to relax the pointer checking above, but as I say, I'd suggest doing both.

Avoid obfuscation

The check_heap_space function is both superfluous and poorly named. It's poorly named because it does not really check heap space, it checks the specifically pass pointer. It's superfluous because the only place it's used is here:

NodeT *new_node = (NodeT*)malloc(sizeof(NodeT));
if ( check_heap_space(new_node) ){

That's much more simply and clearly written like this:

NodeT *new_node = malloc(sizeof(NodeT));
if ( new_node != NULL ){

Note also that the void * returned by malloc or calloc does not need an explicit cast.

Think about the user

The user of a linked list library may want to use that structure without necessarily wanting or needing to know about the implementation details. The code design should accomodate that. So for instance, instead of clean_heap_memory() which doesn't give any useful indication about how it's intended to be used, how about list_delete()? Likewise, I'd suggest list_create() and list_append() and/or list_insert() instead of init_token_iterators() and create_node() plus add_node(). It would also be wise to create separate list_print and node_print functions rather than having the print_node function do some of each.

Omit return 0

When a C or C++ program reaches the end of main the compiler will automatically generate code to return 0, so there is no need to put return 0; explicitly at the end of main.

Note: when I make this suggestion, it's almost invariably followed by one of two kinds of comments: "I didn't know that." or "That's bad advice!" My rationale is that it's safe and useful to rely on compiler behavior explicitly supported by the standard. For C, since C99; see ISO/IEC 9899:1999 section 5.1.2.2.3:

[...] a return from the initial call to the main function is equivalent to calling the exit function with the value returned by the main function as its argument; reaching the } that terminates the main function returns a value of 0.

For C++, since the first standard in 1998; see ISO/IEC 14882:1998 section 3.6.1:

If control reaches the end of main without encountering a return statement, the effect is that of executing return 0;

All versions of both standards since then (C99 and C++98) have maintained the same idea. We rely on automatically generated member functions in C++, and few people write explicit return; statements at the end of a void function. Reasons against omitting seem to boil down to "it looks weird". If, like me, you're curious about the rationale for the change to the C standard read this question. Also note that in the early 1990s this was considered "sloppy practice" because it was undefined behavior (although widely supported) at the time.

So I advocate omitting it; others disagree (often vehemently!) In any case, if you encounter code that omits it, you'll know that it's explicitly supported by the standard and you'll know what it means.

\$\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.