Skip to main content
Code Review

Return to Answer

Spelling
Source Link
John Bollinger
John Bollinger
  • 687
  • 3
  • 10

  • I don't see the point of check_valid_index(), especially given that it should not be emitting a diagnostic message (see above). You already have LinkedList.length. If the point is to handle negative indexes then,

    1. I probably wouldn't, even if I were sticking with indexed access, and
    2. the function is misnamed for that purpose.

  • _add_node() seems to be intended as an internal function. If it's not supposed to be used by functions outside the library, then make it static and omit it from the header. Then code from other source files won't even have a means to call it.

  • _add_node() should be implemented iteratively, not recursively. An iterative implementation would hardly be any more complex, and it would not depend on the compiler performing a tail-call optimization to avoid risk of stack overflow.

  • ... or consider adding a tail pointer to your linked list structure, so that you don't have to iterate through the whole list to find the end in the first place. Then _add_node(), if retained, wouldn't even need to loop.

  • Your sort() is downright awful. You've taken the worst version of the worst quadratic sort and made it even worse than that. Because your set() function has to iterate through the list to find the specified index, and you call it (twice) in the inner loop, your bubble sort requires up to O(n3) steps, up from O(n2) for a typical bubble sort.

    If you're determined to use bubble sort then there are at least two good ways to avoid set() in its implementation, but linked lists are very friendly to overall better sorting algorithms such as insertion sort and merge sort.

    Hint: consider reordering the list by manipulating nodes' next pointers instead of by moving data from one node to another.

  • Do not cast the return value of malloc() in C. It is unnecessary, and it can mask certain coding errors. Do, generally, use the variable to which the result is being asignedassigned to compute the allocation size, as this tends to be more resistant to errors arising during maintenance. And if you use an expression instead of a type name with the sizeof operator then the parentheses are optional. Like this:

         LinkedList *list = malloc(sizeof *list);

  • Avoid needless code duplication. I'm looking in particular at append(), in which most of the contents of the else block duplicate most of the contents of the if block. Factor out the common code. An improved version is already presented above.

  • Not duplication per se, but the if(list->length == 0) check in print_linked_list() is somewhat needless. Especially if that function also stops needlessly making a copy of each node before printing it. For example:

    void print_linked_list(LinkedList* list){
    printf("{");
    const char *delim = "";
    for (Node *current = list->head; current != NULL; current = current->next) {
        printf("%s%d", delim, current->data);
        delim = ", ";
    }
    printf("}\n");
}

    Lower code complexity for the same functionality is usually a win for avoiding bugs and reducing maintenance costs. It is often (but not always) better for performance, too.

  • I don't see the point of check_valid_index(), especially given that it should not be emitting a diagnostic message (see above). You already have LinkedList.length. If the point is to handle negative indexes then,

    1. I probably wouldn't, even if I were sticking with indexed access, and
    2. the function is misnamed for that purpose.

  • _add_node() seems to be intended as an internal function. If it's not supposed to be used by functions outside the library, then make it static and omit it from the header. Then code from other source files won't even have a means to call it.

  • _add_node() should be implemented iteratively, not recursively. An iterative implementation would hardly be any more complex, and it would not depend on the compiler performing a tail-call optimization to avoid risk of stack overflow.

  • ... or consider adding a tail pointer to your linked list structure, so that you don't have to iterate through the whole list to find the end in the first place. Then _add_node(), if retained, wouldn't even need to loop.

  • Your sort() is downright awful. You've taken the worst version of the worst quadratic sort and made it even worse than that. Because your set() function has to iterate through the list to find the specified index, and you call it (twice) in the inner loop, your bubble sort requires up to O(n3) steps, up from O(n2) for a typical bubble sort.

    If you're determined to use bubble sort then there are at least two good ways to avoid set() in its implementation, but linked lists are very friendly to overall better sorting algorithms such as insertion sort and merge sort.

    Hint: consider reordering the list by manipulating nodes' next pointers instead of by moving data from one node to another.

  • Do not cast the return value of malloc() in C. It is unnecessary, and it can mask certain coding errors. Do, generally, use the variable to which the result is being asigned to compute the allocation size, as this tends to be more resistant to errors arising during maintenance. And if you use an expression instead of a type name with the sizeof operator then the parentheses are optional. Like this:

         LinkedList *list = malloc(sizeof *list);

  • Avoid needless code duplication. I'm looking in particular at append(), in which most of the contents of the else block duplicate most of the contents of the if block. Factor out the common code. An improved version is already presented above.

  • Not duplication per se, but the if(list->length == 0) check in print_linked_list() is somewhat needless. Especially if that function also stops needlessly making a copy of each node before printing it. For example:

    void print_linked_list(LinkedList* list){
    printf("{");
    const char *delim = "";
    for (Node *current = list->head; current != NULL; current = current->next) {
        printf("%s%d", delim, current->data);
        delim = ", ";
    }
    printf("}\n");
}

    Lower code complexity for the same functionality is usually a win for avoiding bugs and reducing maintenance costs. It is often (but not always) better for performance, too.

  • I don't see the point of check_valid_index(), especially given that it should not be emitting a diagnostic message (see above). You already have LinkedList.length. If the point is to handle negative indexes then,

    1. I probably wouldn't, even if I were sticking with indexed access, and
    2. the function is misnamed for that purpose.

  • _add_node() seems to be intended as an internal function. If it's not supposed to be used by functions outside the library, then make it static and omit it from the header. Then code from other source files won't even have a means to call it.

  • _add_node() should be implemented iteratively, not recursively. An iterative implementation would hardly be any more complex, and it would not depend on the compiler performing a tail-call optimization to avoid risk of stack overflow.

  • ... or consider adding a tail pointer to your linked list structure, so that you don't have to iterate through the whole list to find the end in the first place. Then _add_node(), if retained, wouldn't even need to loop.

  • Your sort() is downright awful. You've taken the worst version of the worst quadratic sort and made it even worse than that. Because your set() function has to iterate through the list to find the specified index, and you call it (twice) in the inner loop, your bubble sort requires up to O(n3) steps, up from O(n2) for a typical bubble sort.

    If you're determined to use bubble sort then there are at least two good ways to avoid set() in its implementation, but linked lists are very friendly to overall better sorting algorithms such as insertion sort and merge sort.

    Hint: consider reordering the list by manipulating nodes' next pointers instead of by moving data from one node to another.

  • Do not cast the return value of malloc() in C. It is unnecessary, and it can mask certain coding errors. Do, generally, use the variable to which the result is being assigned to compute the allocation size, as this tends to be more resistant to errors arising during maintenance. And if you use an expression instead of a type name with the sizeof operator then the parentheses are optional. Like this:

         LinkedList *list = malloc(sizeof *list);

  • Avoid needless code duplication. I'm looking in particular at append(), in which most of the contents of the else block duplicate most of the contents of the if block. Factor out the common code. An improved version is already presented above.

  • Not duplication per se, but the if(list->length == 0) check in print_linked_list() is somewhat needless. Especially if that function also stops needlessly making a copy of each node before printing it. For example:

    void print_linked_list(LinkedList* list){
    printf("{");
    const char *delim = "";
    for (Node *current = list->head; current != NULL; current = current->next) {
        printf("%s%d", delim, current->data);
        delim = ", ";
    }
    printf("}\n");
}

    Lower code complexity for the same functionality is usually a win for avoiding bugs and reducing maintenance costs. It is often (but not always) better for performance, too.

added omitted words
Source Link
John Bollinger
John Bollinger
  • 687
  • 3
  • 10

  • I don't see the point of check_valid_index(), especially given that it should not be emitting a diagnostic message (see above). You already have LinkedList.length. If the point is to handle negative indexes then,

    1. I probably wouldn't, even if I were sticking with indexed access, and
    2. the function is misnamed for that purpose.

  • _add_node() seems to be intended as an internal function. If it's not supposed to be used by functions outside the library, then make it static and omit it from the header. Then code from other source files won't even have a means to call it.

  • _add_node() should be implemented iteratively, not recursively. An iterative implementation would hardly be any more complex, and it would not depend on the compiler performing a tail-call optimization to avoid risk of stack overflow.

  • ... or consider adding a tail pointer to your linked list structure, so that you don't have to iterate through the whole list to find the end in the first place. Then _add_node(), if retained, wouldn't even need to loop.

  • Your sort() is downright awful. You've taken the worst version of the worst quadratic sort and made it even worse than that. Because your set() function has to iterate through the list to find the specified index, and you call it (twice) in the inner loop, your bubble sort requires up to O(n3) steps, up from O(n2) for a typical bubble sort.

    If you're determined to use bubble sort then there are at least two good ways to avoid set() in its implementation, but linked lists are very friendly to overall better sorting algorithms such as insertion sort and merge sort.

    Hint: consider reordering the list by manipulating nodes' next pointers instead of by moving data from one node to another.

  • Do not cast the return value of malloc() in C. It is unnecessary, and it can mask certain coding errors. Do, generally, use the variable to which the result is being asigned to compute the allocation size, as this tends to be more resistant to errors arising during maintenance. And if you use an expression instead of a type name with the sizeof operator then the parentheses are optional. Like this:

         LinkedList *list = malloc(sizeof *list);

  • Avoid needless code duplication. I'm looking in particular at append(), in which most of the contents of the else block duplicate most of the contents of the if block. Factor out the common code. An improved version is already presented above.

  • Not duplication per se, but the if(list->length == 0) check in print_linked_list() is somewhat needless. Especially if that function also stops needlessly making a copy of each node before printing it. For example:

    void print_linked_list(LinkedList* list){
    printf("{");
    const char *delim = "";
    for (Node *current = list->head; current != NULL; current = current->next) {
        printf("%s%d", delim, current->data);
        delim = ", ";
    }
    printf("}\n");
}

    Lower code complexity for the same functionality is usually a win for avoiding bugs and reducing maintenance costs. It is often (but not always) better for performance, too.

  • I don't see the point of check_valid_index(), especially given that it should not be emitting a diagnostic message (see above). You already have LinkedList.length. If the point is to handle negative indexes then,

    1. I probably wouldn't, even if I were sticking with indexed access, and
    2. the function is misnamed for that purpose.

  • _add_node() seems to be intended as an internal function. If it's not supposed to be used by functions outside the library, then make it static and omit it from the header. Then code from other source files won't even have a means to

  • _add_node() should be implemented iteratively, not recursively. An iterative implementation would hardly be any more complex, and it would not depend on the compiler performing a tail-call optimization to avoid risk of stack overflow.

  • ... or consider adding a tail pointer to your linked list structure, so that you don't have to iterate through the whole list to find the end in the first place. Then _add_node(), if retained, wouldn't even need to loop.

  • Your sort() is downright awful. You've taken the worst version of the worst quadratic sort and made it even worse than that. Because your set() function has to iterate through the list to find the specified index, and you call it (twice) in the inner loop, your bubble sort requires up to O(n3) steps, up from O(n2) for a typical bubble sort.

    If you're determined to use bubble sort then there are at least two good ways to avoid set() in its implementation, but linked lists are very friendly to overall better sorting algorithms such as insertion sort and merge sort.

    Hint: consider reordering the list by manipulating nodes' next pointers instead of by moving data from one node to another.

  • Do not cast the return value of malloc() in C. It is unnecessary, and it can mask certain coding errors. Do, generally, use the variable to which the result is being asigned to compute the allocation size, as this tends to be more resistant to errors arising during maintenance. And if you use an expression instead of a type name with the sizeof operator then the parentheses are optional. Like this:

         LinkedList *list = malloc(sizeof *list);

  • Avoid needless code duplication. I'm looking in particular at append(), in which most of the contents of the else block duplicate most of the contents of the if block. Factor out the common code. An improved version is already presented above.

  • Not duplication per se, but the if(list->length == 0) check in print_linked_list() is somewhat needless. Especially if that function also stops needlessly making a copy of each node before printing it. For example:

    void print_linked_list(LinkedList* list){
    printf("{");
    const char *delim = "";
    for (Node *current = list->head; current != NULL; current = current->next) {
        printf("%s%d", delim, current->data);
        delim = ", ";
    }
    printf("}\n");
}

    Lower code complexity for the same functionality is usually a win for avoiding bugs and reducing maintenance costs. It is often (but not always) better for performance, too.

  • I don't see the point of check_valid_index(), especially given that it should not be emitting a diagnostic message (see above). You already have LinkedList.length. If the point is to handle negative indexes then,

    1. I probably wouldn't, even if I were sticking with indexed access, and
    2. the function is misnamed for that purpose.

  • _add_node() seems to be intended as an internal function. If it's not supposed to be used by functions outside the library, then make it static and omit it from the header. Then code from other source files won't even have a means to call it.

  • _add_node() should be implemented iteratively, not recursively. An iterative implementation would hardly be any more complex, and it would not depend on the compiler performing a tail-call optimization to avoid risk of stack overflow.

  • ... or consider adding a tail pointer to your linked list structure, so that you don't have to iterate through the whole list to find the end in the first place. Then _add_node(), if retained, wouldn't even need to loop.

  • Your sort() is downright awful. You've taken the worst version of the worst quadratic sort and made it even worse than that. Because your set() function has to iterate through the list to find the specified index, and you call it (twice) in the inner loop, your bubble sort requires up to O(n3) steps, up from O(n2) for a typical bubble sort.

    If you're determined to use bubble sort then there are at least two good ways to avoid set() in its implementation, but linked lists are very friendly to overall better sorting algorithms such as insertion sort and merge sort.

    Hint: consider reordering the list by manipulating nodes' next pointers instead of by moving data from one node to another.

  • Do not cast the return value of malloc() in C. It is unnecessary, and it can mask certain coding errors. Do, generally, use the variable to which the result is being asigned to compute the allocation size, as this tends to be more resistant to errors arising during maintenance. And if you use an expression instead of a type name with the sizeof operator then the parentheses are optional. Like this:

         LinkedList *list = malloc(sizeof *list);

  • Avoid needless code duplication. I'm looking in particular at append(), in which most of the contents of the else block duplicate most of the contents of the if block. Factor out the common code. An improved version is already presented above.

  • Not duplication per se, but the if(list->length == 0) check in print_linked_list() is somewhat needless. Especially if that function also stops needlessly making a copy of each node before printing it. For example:

    void print_linked_list(LinkedList* list){
    printf("{");
    const char *delim = "";
    for (Node *current = list->head; current != NULL; current = current->next) {
        printf("%s%d", delim, current->data);
        delim = ", ";
    }
    printf("}\n");
}

    Lower code complexity for the same functionality is usually a win for avoiding bugs and reducing maintenance costs. It is often (but not always) better for performance, too.

Source Link
John Bollinger
John Bollinger
  • 687
  • 3
  • 10

Design considerations

  • Linked lists are the wrong choice for indexed / random access. Use a dynamically-allocated array instead if that's an important access mode for you.

  • In fact, consider whether get() and set() are the right interfaces for a linked list at all. People choosing a linked list generally do so with the understanding and expectation that they will iterate over it, insert nodes at various positions, and delete nodes at various positions. Your list does not provide support for much of that. Users can roll their own, of course, but if they must do that, then its unclear whether your implementation provides much to interest them.

  • Even if you want to support indexed access, it is not useful to store indexes in the nodes, because some of the existing nodes' indexes change (or should) when you add or remove a node other than at the end. One of the main features of linked lists is that it's cheap to add or remove elements at other positions, and if you're prepared to give that up then why choose a linked list at all?

  • Generally speaking, libraries such as this should not emit diagnostic messages unless as a prelude to aborting the program. And they should not be wantonly aborting programs, so for the most part, they should not emit diagnostic messages at all. Instead, when they detect an error of some kind, they should inform their caller programmatically. Typically that takes the form of returning a special value or updating an out parameter in a particular way.

  • It is therefore relevant that although at least one of your functions (allocate_linked_list()) has a natural means to provide a distinguished error-indicator, you'll have to think harder about some of the others, such as get(). You should aim for consistency in this regard.

  • When I see a pop(), I expect to see a push(), too. If you prefer append() to push() then you should also prefer remove_last() or similar to pop().

  • Many of your function names are very generic (get, set, sort, ...), and so are prone to collision with other functions of the same name. It is common to mitigate such issues by choosing and consistently using an identifying prefix for all your external names, thus providing a rough form of namespacing. For instance, ll_get, ll_set, etc.

  • I usually favor implementing linked lists with a dummy, non-data carrying head node. Doing this makes all data-bearing nodes internal, so that you don't need special cases for operations involving a data-bearing node that happens to be at the head. Such as append() has. For instance, consider this:

    typedef struct LinkedList {
    Node head; // not a pointer
    int length;
} LinkedList;

// ...

void append(LinkedList *list, int item) {
    Node *p_node = malloc(sizeof *p_node);

    if (p_node != NULL) {
        p_node->data = item;
        p_node->next = NULL;
        _add_node(&list->head, p_node, 0);
        list->length++;
    }

    return p_node;
}

    That would require adjustments throughout, of course.

Errors and Bugs

  • free_linked_list() is buggy. Here ...

            Node* node_to_be_freed = current;
        free(node_to_be_freed);
        current = current->next;

    ... the last statement accesses *current after the previous statement has freed that object. It does not matter that free() is passed the value of a different variable, because that (pointer) value is the same as the value of current. You must extract any data you need from the node -- that is, its next pointer -- before you free it.

  • possibly not buggy now, but likely to become so as the library gains more features, index-based get() and set() should count nodes, not rely on their recorded indexes, because, as described above, the indexes are prone to becoming wrong. Counting is not any more expensive anyway.

  • new_linked_list()'s null check is pointless, because if the memory allocation fails then the function goes ahead and uses the resulting null pointer anyway. The behavior is undefined in that case, so it is not certain that the diagnostic it prints (but should not) will actually be seen anyway. Better would be for this function to do nothing but return the null pointer (a natural error-indicator) in the event that allocation fails.

  • Similar applies to the null checks in append() (and consider the alternative implementation above).

  • Identifiers beginning with underscores (such as _add_node) are reserved for use as ordinary identifiers with file scope. Avoid using reserved identifiers. Since you'll be using other, more reliable means to control access to _add_node() (see below), you don't need that Pythonesque naming convention anyway.

Other areas for improvement

  • I don't see the point of check_valid_index(), especially given that it should not be emitting a diagnostic message (see above). You already have LinkedList.length. If the point is to handle negative indexes then,

    1. I probably wouldn't, even if I were sticking with indexed access, and
    2. the function is misnamed for that purpose.

  • _add_node() seems to be intended as an internal function. If it's not supposed to be used by functions outside the library, then make it static and omit it from the header. Then code from other source files won't even have a means to

  • _add_node() should be implemented iteratively, not recursively. An iterative implementation would hardly be any more complex, and it would not depend on the compiler performing a tail-call optimization to avoid risk of stack overflow.

  • ... or consider adding a tail pointer to your linked list structure, so that you don't have to iterate through the whole list to find the end in the first place. Then _add_node(), if retained, wouldn't even need to loop.

  • Your sort() is downright awful. You've taken the worst version of the worst quadratic sort and made it even worse than that. Because your set() function has to iterate through the list to find the specified index, and you call it (twice) in the inner loop, your bubble sort requires up to O(n3) steps, up from O(n2) for a typical bubble sort.

    If you're determined to use bubble sort then there are at least two good ways to avoid set() in its implementation, but linked lists are very friendly to overall better sorting algorithms such as insertion sort and merge sort.

    Hint: consider reordering the list by manipulating nodes' next pointers instead of by moving data from one node to another.

  • Do not cast the return value of malloc() in C. It is unnecessary, and it can mask certain coding errors. Do, generally, use the variable to which the result is being asigned to compute the allocation size, as this tends to be more resistant to errors arising during maintenance. And if you use an expression instead of a type name with the sizeof operator then the parentheses are optional. Like this:

         LinkedList *list = malloc(sizeof *list);

  • Avoid needless code duplication. I'm looking in particular at append(), in which most of the contents of the else block duplicate most of the contents of the if block. Factor out the common code. An improved version is already presented above.

  • Not duplication per se, but the if(list->length == 0) check in print_linked_list() is somewhat needless. Especially if that function also stops needlessly making a copy of each node before printing it. For example:

    void print_linked_list(LinkedList* list){
    printf("{");
    const char *delim = "";
    for (Node *current = list->head; current != NULL; current = current->next) {
        printf("%s%d", delim, current->data);
        delim = ", ";
    }
    printf("}\n");
}

    Lower code complexity for the same functionality is usually a win for avoiding bugs and reducing maintenance costs. It is often (but not always) better for performance, too.