10
\$\begingroup\$

I'm learning C, and wrote this program outside of my assignments in order to practice pointer manipulation and data structures, step by step. I want to ensure that this program follows well known conventions, has excellent style and readability, and uses pointers as efficiently as possible, before I move on to more complex structs.

I am aware I am not doing any error checking or type checking. I don't intend to export this code as-is, my intention is to practice with pointers. I found it easiest for now to keep the code as simple as possible and remove checking. This is also why I created the additional functions, just to help isolate parts of the code.

If appropriate, I'm also interested in modifying the freelist() function to work recursively, freeing the last node first. Currently, if the node order is {1,2,3}, 1 is freed first. I haven't been able to successfully call the function recursively to instead free the nodes from 3 then 2 then 1.

// This program stores N integers from user input into a 
// linked list, prints the list, and then frees each node. 

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

#define N 5

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

int getinteger(void);
void printlist(NODE **head);
void freelist(NODE *head);

int main(void)
{
    NODE *start = NULL;

    for (int i = 0, n = 0; i < N; i++)
    {
        n = getinteger();

        NODE *newnode = (NODE *) malloc(sizeof(NODE));
        newnode->value = n;
        newnode->next = NULL;

        if (start == NULL)
        {
            start = newnode;
        }
        else
        {
            NODE *p = NULL;
            for (p = start; p->next != NULL; p = p->next)
                ;
            p->next = newnode;
        }
    }

    printlist(&start);
    freelist(start);
}

int getinteger(void)
{
    int n = 0;
    printf("Enter integer: ");
    scanf("%i", &n);
    return n;
}

void printlist(NODE **head)
{
    NODE **tracer = head;
    while ((*tracer) != NULL)
    {
        printf("%i\n",(*tracer)->value);
        tracer = &(*tracer)->next;
    }
}

void freelist(NODE *head)
{
    NODE *p = head;
    while (p != NULL)
    {
        NODE *next = p->next;
        free(p);
        p = next;
    }
}
\$\endgroup\$
  • 3
    \$\begingroup\$ While I voted +1 on this question, I was torn because of the lack of error checking. Because C is very close to assembly and doesn't throw exceptions one should always perform error checking on possible errors that can cause the program to terminate. \$\endgroup\$ – pacmaninbw Sep 27 at 14:37
  • 1
    \$\begingroup\$ Note taken on error checking. I'll especially take this into consideration when posting for code reviews. I want to ensure that any time someone takes during review is spent wisely. Thank you. \$\endgroup\$ – Jim Diroff II Sep 27 at 20:56
12
\$\begingroup\$

Naming

It's unconventional to name a type with all-uppercase - we normally reserve those names for preprocessor macros, to warn readers that they need treating with care. Avoid such names for ordinary identifiers.

Avoid using identifiers that begin with an underscore - in many situations, those names are reserved for use by the implementation, which could conflict with your own uses.

Allocation

Let's look at this section:

    NODE *newnode = (NODE *) malloc(sizeof(NODE));
    newnode->value = n;
    newnode->next = NULL;

There's a serious bug here. Remember that malloc() can return a null pointer. It's essential to check that newnode is not null before we dereference it using * or ->.

Because malloc() returns a void*, it's not necessary or desirable to cast the result - we can assign it directly to newnode. Also, when computing the size, we can avoid repeating the type of the allocation by writing sizeof *newnode for the size (this has more value when the allocation is far from the declaration, but it's a good habit to be in).

That gives this replacement:

    Node *newnode = malloc(sizeof *newnode);
    if (!newnode) {
        fputs("Allocation failed\n", stderr);
        return EXIT_FAILURE;
    }

    newnode->value = n;
    newnode->next = NULL;

Reading input

Another function whose return value must be checked is scanf(). If I enter something that's not a number, or if I close the input stream, then we don't write to n here:

scanf("%i", &n);

We need to check the return value and test whether the expected number of items were successfully converted. Something like this:

int getinteger(void)
{
    int n = 0;
    printf("Enter integer: ");
    fflush(stdout);
    while (scanf("%i", &n) != 1) {
        if (feof(stdin)) {
            /* no point retrying! */
            fputs("Read failure\n", stderr);
            exit(EXIT_FAILURE);
        }
        printf("Invalid input! Enter integer: ");
        fflush(stdout);
        scanf("%*[^\n]");       /* discard rest of line */
        /* newline remains, but will be discarded by scanf("%i") */
    }
    return n;
}

Notice that there's a lot more code for dealing with the unexpected than with the "happy path" - that's a common experience when reading input using C.

Memory management

Apart from the lack of checking when malloc() is used, the memory management is great. No leaks, double-frees, or use of uninitialised, unallocated or released memory.

Efficiency

Notice that every time we add a node, we have to start from the head, and traverse the whole length of the list to get to the tail. This becomes more and more work as the list gets longer - sometimes likened to Schlemiel the Painter. We can make this more efficient, though at the cost of some extra storage, by maintaining a pointer to the tail of the list as well as the head.

Other improvements

We don't need to pass a pointer-to-pointer into printlist(); a plain Node * is fine:

void printlist(Node *p)
{
    for (;  p;  p = p->next) {
        printf("%i\n", p->value);
    }
}

When we're looking for the list tail, we can simplify by starting p at head rather than first assigning NULL:

        Node *p = start;
        while (p->next) {
            p = p->next;
        }
        p->next = newnode;

In the main loop in main(), n shouldn't be declared in the for initializer, as it's not part of the loop control.

If we define main() last, the definitions of the other functions can act as their declarations, so no need to forward-declare them.


Improved code

Note: I haven't addressed the issue mentioned above in "Efficiency".

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

/* number of nodes to create in list */
#define N 5

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

/* Prompt on stdout, and read a number from stdin */
int getinteger(void)
{
    printf("Enter integer: ");
    fflush(stdout);

    int n;
    while (scanf("%i", &n) != 1) {
        if (feof(stdin)) {
            /* no point retrying! */
            fputs("Read failure\n", stderr);
            exit(EXIT_FAILURE);
        }
        printf("Invalid input! Enter integer: ");
        fflush(stdout);
        scanf("%*[^\n]");       /* discard rest of line */
        /* newline remains, but will be discarded by scanf("%i") */
    }

    return n;
}

void printlist(Node *p)
{
    for (;  p;  p = p->next) {
        printf("%i\n", p->value);
    }
}

void freelist(Node *p)
{
    while (p) {
        Node *next = p->next;
        free(p);
        p = next;
    }
}


int main(void)
{
    Node *start = NULL;

    for (int i = 0;  i < N;  ++i) {
        int n = getinteger();

        Node *newnode = malloc(sizeof *newnode);
        if (!newnode) {
            fputs("Allocation failure\n", stderr);
            return EXIT_FAILURE;
        }

        newnode->value = n;
        newnode->next = NULL;

        if (!start) {
            start = newnode;
        } else {
            Node *p = start;
            while (p->next) {
                p = p->next;
            }
            p->next = newnode;
        }
    }

    printlist(start);
    freelist(start);
}
\$\endgroup\$
  • \$\begingroup\$ Thank you very much for this feedback. I especially appreciate the integer checking and allocation error. I'm going to spend some time reviewing your feedback and incorporating changes into my program. \$\endgroup\$ – Jim Diroff II Sep 27 at 20:54
  • 2
    \$\begingroup\$ In theory malloc() can return a null pointer. In practice, MacOS and Linux both use memory overcommit, so malloc() won't fail except in highly unusual circumstances (eg. you're trying to allocate tens of terabytes of memory). Windows doesn't do overcommit, but the available swap space is usually so huge that by the time you run out, the user will have already rebooted the computer because it was getting unbearably slow. \$\endgroup\$ – Mark Sep 27 at 22:12
  • \$\begingroup\$ scanf("%*[^\n]"); /* discard pending input */ is a slight misnomer as a '\n' remains unconsumed. Not an issue for a following scanf("%i", &n), but scanf("%*[^\n]") is not a complete "discard pending input". \$\endgroup\$ – chux - Reinstate Monica Sep 28 at 14:34
  • \$\begingroup\$ @Mark, you can avoid overcommit, either with a suitable sysctl (to fix it globally) or with ulimit (for a process tree). Even on a system with unlimited overcommit, failing to check system call return values is a bad habit that should be unlearned. \$\endgroup\$ – Toby Speight Sep 30 at 7:42
  • \$\begingroup\$ @chux, yes, if we had a read that didn't ignore leading whitespace, we'd need to also discard the newline (either by adding %*c to the format string or with a separate getchar(). Do you have a suggestion for a better comment that's not too verbose? \$\endgroup\$ – Toby Speight Sep 30 at 7:44
7
\$\begingroup\$

Hi Jim Diroff II and welcome to CodeReview,

Your code looks sane and I didn't spot any leaks.

In printlist() why are you using a double pointer? This is only required if you intend to modify the pointer value, which you don't. Better use a normal pointer here:

void printlist(NODE *head)
{
    NODE *tracer = head;
    while (tracer != NULL)
    {
        printf("%i\n", tracer->value);
        tracer = tracer->next;
    }
}

If you move the definitions of your helper functions above main(), you can save yourself the forward declarations.

To get freelist() to work in the opposite direction, I suggest making it a doubly linked list, which also would be a nice additional task to learn more about pointers. Having a recursive cleanup function has the potential to trash your programm with longer lists and will also add a lot performance overhead:

void freelist(NODE* head)
{
    if (head)
    {
         freelist(head->next);
         free(head);
    }
}

Also, don't avoid error handling. It's the biggest issue I see in code, that someone didn't want to check that one return value.

\$\endgroup\$
  • 1
    \$\begingroup\$ "If you move the definitions of your helper functions above main(), you can save yourself the forward declarations." -- I wouldn't suggest that. It's easier to read if you can see the entry point of the program first. \$\endgroup\$ – JL2210 Sep 27 at 11:06
  • 2
    \$\begingroup\$ @JL2210 It's a personal choice in a program of this size. While I wouldn't have stated it in a review, my first impression was the same as the reviewers. \$\endgroup\$ – pacmaninbw Sep 27 at 14:31
  • 1
    \$\begingroup\$ As the payload does not have any complex destruction, the order really does not matter. But if it matters for a modified version, using an in-place-reversal and than destructing from the head is better than moving to double-linkage just for that. \$\endgroup\$ – Deduplicator Sep 27 at 20:32
  • \$\begingroup\$ Thank you all for your comments. I really appreciate the thorough and detailed responses, as well as the discussion on specifics. On the topic of the helper functions, in the class I'm taking, the preferred style is to declare functions before main() and define functions after main(). That is fine for the class, but in real-world programming, which method is more conventional? If I'm reading the feedback correctly, we have a few votes for declaring and defining functions before main(). Also, note taken on the error handling and checking. Will remember for future posts. \$\endgroup\$ – Jim Diroff II Sep 27 at 21:13

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.