2
\$\begingroup\$

Being completely new to the world of C, I started off with the excercise of building a singly linked list of integers:

/*
  Single linked list test
*/
#include <stdlib.h>
#include <stdio.h>


typedef struct ListElement {
    int         value;
    struct ListElement  *next;
} ListElement;


void printList(ListElement *root) {
    ListElement *current;
    current = root;

    while (current->next) {
        printf("Value: %i\n", current->value);
        current = current->next;
    }

    printf("Value: %i\n", current->value);
}


int freeLast(ListElement *root) {
    int retval;
    retval = 1;
    ListElement *previous;
    ListElement *current;
    current = root;

    while (current->next) {
        previous = current;
        current = current->next;
    }

    if (current == root) {
        retval = 0;
    }

    previous->next = NULL;
    printf("Freeing %i\n", current->value);
    free(current);
    return retval;
}


void freeList(ListElement *root) {
    while(freeLast(root));
}


ListElement * createList(int size) {
    ListElement *root;
    ListElement *current;
    root = malloc(sizeof(ListElement));

    if (root != NULL) {
        root->value = 0;
        current = root;
        int i;

        for (i = 1; i < size; i++) {
            current->next = malloc(sizeof(ListElement));

            if (current->next != NULL) {
                current->next->value = i;
                current = current->next;
            } else {
                freeList(root);
                return NULL;
            }
        }

        return root;
    } else {
        return NULL;
    }
}


int main() {
    ListElement *root = createList(100);
    printList(root);
    freeList(root);
}

While the code compiles and runs as intended I'd like to have some feedback on the coding style, program structure and possibly existing quirks with the memory handling in C, which I hope I got right.

\$\endgroup\$
3
\$\begingroup\$

This is pretty good. Minor points:

You can return just root in createList:

ListElement * createList(int size) {
    ListElement *root;
    ListElement *current;
    root = malloc(sizeof(ListElement));

    if (root != NULL) {
        root->value = 0;
        current = root;
        int i;

        for (i = 1; i < size; i++) {
            current->next = malloc(sizeof(ListElement));

            if (current->next != NULL) {
                current->next->value = i;
                current = current->next;
            } else {
                freeList(root);
                return NULL;
            }
        }
    }

    return root;
}

And your freeList is O(n^2) complex, because you are removing from the end. Removing from the beginning would make it O(n).

\$\endgroup\$
  • \$\begingroup\$ Did you mean O(n^2) instead of O(!n)? \$\endgroup\$ – etarion Aug 9 '17 at 16:33
  • \$\begingroup\$ Why? To delete last you walk over n elements, then to delete one before last you walk n-1 elements and so on up to first one. This gives 1*2*...*n iterations. \$\endgroup\$ – arrowd Aug 9 '17 at 17:13
  • \$\begingroup\$ 1+2+...+n, not 1*2*....*n. \$\endgroup\$ – etarion Aug 9 '17 at 17:15
  • \$\begingroup\$ Oh, silly me. You are absolutely right. \$\endgroup\$ – arrowd Aug 9 '17 at 17:16
2
\$\begingroup\$

Consider p = malloc(sizeof *p * n); idiom.


Assume typedef struct ListElement { ... *next; } ListElement; exists in some other file like ListElement.h

You are reviewing/maintaining code in the some .c file and code compiles OK,


Is sizeof(ListElement) the correct size?

current->next = malloc(sizeof(ListElement));

To make sure, 1) find the definition of current. OK that is ListElement *current;. 2) now find the definition of ListElement and its member next. With a good naming convention, it should be in ListElement.h, or it might might exist elsewhere. OK find that and see the member is struct ListElement *next; 3) Check to insure ListElement is a typedef for struct ListElement. Now done - all OK.


How about less work? Is sizeof *(current->next) the correct size? --> Yes - of course. No need to check the type of current->next. Done.

current->next = malloc(sizeof *(current->next));

Minor

createList(0) acts like createList(1). I'd expect createList(0) to have no elements - empty list.


Using root as the name of the linked-list describes the inner works of the type. Instead, the name of the linked-list should describe the list itself and abstract its inner workings.

#define DECK_SIZE 52
ListElement *CardDeck = createList(DECK_SIZE);
\$\endgroup\$
1
\$\begingroup\$

I'm not a C programmer, so I have only minor comments.

Node instead of ListElement simply because it's shorter.

[EDIT: the idea in the paragraph below is not valid. See comments.]

In createList it would be possible to only do one malloc(sizeof(ListElement) * size) and set the next pointers by simple arithmetic. It would have the advantage of also keeping the memory layout compact. But I have no idea if this would be considered good practice in C. Looking for someone to comment on this.

\$\endgroup\$
  • 1
    \$\begingroup\$ I also thought of this, but then it would be impossible to free arbitrary elements. \$\endgroup\$ – arrowd Aug 9 '17 at 16:01
  • \$\begingroup\$ Each element is referred from the next of its predecessor (which you have to setup in createList) and the head node is just the pointer returned by createList. So freeing elements is the same as before. \$\endgroup\$ – toto2 Aug 9 '17 at 16:42
  • \$\begingroup\$ you cannot free from the middle of a contiguous block of memory. it's not a question of "good practice," it is simply not how the machine works. \$\endgroup\$ – j. andrew shusta Aug 9 '17 at 17:05
  • \$\begingroup\$ Thanks. As I said I'm not a C programmer. \$\endgroup\$ – toto2 Aug 9 '17 at 17:15

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.