3
\$\begingroup\$

How is this Implementation of a list in C?

Please tell me whether it is good or please mention any problems. It is a singly linked List and I tried to do it recursively.

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

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

void add(struct node *lst, int num){
    if(lst->next == NULL){
        lst->value = num;
        lst->next = (struct node*)malloc(sizeof(struct node*));
        lst->next->next = NULL;
    }else{
        add(lst->next, num);
    }
}

void print_lst(struct node *lst){
    if(lst->next == NULL){

    }else{
        printf("\n%d", lst->value);
        print_lst(lst->next);
    }
}

int length(struct node *lst){
    if(lst->next == NULL){
        return 0;
    }else{
        return 1 + length(lst->next);
    }
}

int get(struct node *lst, int pos){
    if(pos < 0 ||  pos >= length(lst)){
        fprintf(stderr ,"\nIndexOutOfBoundsException\n");
    }else if(pos > 0 && pos <length(lst)){
        pos += -1;
        get(lst->next, pos);
    } else if (pos == 0){
        return  lst->value;
    }
}

int main ( ) {

    struct node lst;
    lst.next = NULL;
    add(&lst, 13);
    add(&lst, 12);
    add(&lst,  1);
    add(&lst, 10);
    add(&lst, 10);
    add(&lst, 4);
    //print_lst(&lst);
    printf("\n%d", get(&lst, 2));
    printf("\n%d", get(&lst, 5));
    printf("\n%d", get(&lst, 13));

    printf("\n\n%d", length(&lst));
    return 0;
}
\$\endgroup\$
4
\$\begingroup\$
  • Do not cast the result of malloc. If your code does #include <stdlib.h>, the cast is redundant. If it does not, the cast just masks the warning, which may lead to hard to find bugs.

  • Prefer sizeof(object) to sizeof(type). The latter leads to the double maintenance problem, in case the type is changed.

  • I strongly recommend to have a constructor-like function to create a node:

    struct node * create_node(int num)
    {
        struct node * node = malloc(sizeof(*node));
        node->value = num;
        node->next = NULL;
        return node;
    }
    

    It will spare you plenty of trouble when the definition of struct node changes.

  • You should get a warning that get doesn't always return a value (if you do not, enable all warnings, or change the compiler). It is a very serious warning, and in real life the code with such a problem leads to some dire consequences. You must return get(lst->next, pos); in a recursive clause.

    The fact that your main printed expected values is an unlucky coincidence.

    What to return in the IndexOutOfBound situation is a different matter. Consider returning an error code along with the value.

  • Calling length(lst) at each level of recursion degrades performance to quadratic.

  • As a side note, rather than testing for position < 0, consider passing a position as some unsigned type. size_t is the most obvious candidate.

  • Along the same line, a low level utility function such as get should refrain from printing anything.

  • I strongly advise agains recursion when an iterative solution is immediately available.

\$\endgroup\$
  • \$\begingroup\$ Thanks for the statement. Now I can improve my List. Thanks \$\endgroup\$ – Markus Pfeifenberger Nov 3 at 13:05

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.