5
\$\begingroup\$

This program will create a linked list, set the values, and print the list by using command line options.

This is my first implementation of a linked list so I'm not sure if I did it correctly. The available options are:

-a to add nodes.

To add several nodes:-a "23 56 1" will add three nodes with the respective values

-p will print the nodes. It has to be used after -a or else it will result in an error message.

I'm not looking for any specific input, style, comments, functions used, anything.

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

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

struct node *head;

void add_node(int data);
void print_nodes(void);

int main(int argc, char *argv[]){
    int c;
    long node_value;
    char *ptr;
    char *token;
    const char s[2] = " "; /*Split optarg based on this string*/

    while((c = getopt(argc, argv, "pa:")) != EOF){
        switch(c){
        case 'p':
            print_nodes();
            break;
        case 'a':
            token = strtok(optarg, s); /*Split the string*/
            while(token != NULL){
                node_value = strtol(token, &ptr, 10); /*Convert each string to integer*/
                if((*ptr) != 10 && (*ptr) != 0){ /*If it's not a newline or a null then invalid input*/
                    fprintf(stderr, "Invalid number: %c", *ptr);
                    exit(EXIT_FAILURE);
                }
                add_node(node_value);
                token = strtok(NULL, s);
            }
            break;
        default:
            fprintf(stderr, "Unknown option %c, available options are '-p' and 'a'", c);
            break;
        }
    }
    argc -= optind;
    argv += optind;

    return 0;
}

void add_node(int data){
    struct node *temp = head;

    if(temp == NULL){
        head = malloc(sizeof(struct node));
        head->value = data;
        head->next_ptr = NULL;
        return;
    }

    while(temp->next_ptr != NULL){
        temp = temp->next_ptr;
    }

    if((temp->next_ptr = malloc(sizeof(struct node))) == NULL){
        fprintf(stderr, "Out of memory");
        exit(EXIT_FAILURE);
    }

    temp = temp->next_ptr;
    temp->value = data;
    temp->next_ptr = NULL;
}

void print_nodes(void){
    struct node *temp = head;
    if(temp == NULL){
            printf("Linked list is empty\n");
    }
    for(temp = head; temp != NULL; temp = temp->next_ptr){
        printf("%i\n", temp->value);
    }
}

I want to add more options, sort, search, delete and file integration, but I'd like to make sure this is working correctly first.

\$\endgroup\$
5
\$\begingroup\$

Your program largely accomplishes the core goal you set out to achieve: build and print linked lists from the command line. You seem to understand the singly-linked list data structure and related algorithms for adding nodes and traversing quite well. That said, there are several opportunities for improvement in your code related to the linked list implementation itself and for general programming practices.

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

unitstd.h is widely supported, but not a standard library. Consider replacing it for increased portability.

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

As @pacmaninbw mentioned, consider using a typedef here so you can later use just node instead of struct node. Exact naming is debatable.

struct node *head;

Try very hard to avoid global variables like this. Instead, it's almost always preferable to pass variables as function parameters. In this case, move head inside main and pass it as a new parameter to add_node and print_nodes.

Note that in order to change head as a local variable of main from either add_node or print_nodes you'll need to pass a struct node** instead of just a struct node. The reason for this is that parameters are local variables, so if add_node were to set its head parameter it would only be changing its copy and not the copy held by main. Instead, if the parameter is struct node** then main can pass a pointer to its local copy by passing &head and add_node can change the copy in main by indirection: *head = X.

void add_node(int data);
void print_nodes(void);

Forward-declaring functions is fine and in this small program a mostly stylistic choice that allows you to put main before add_node and print_nodes. Alternatively, you could put main last and avoid the forward declarations. One advantage of that approach is that you won't need to change two places when you change the signature of these functions, such as adding head as a parameter.

int main(int argc, char *argv[]){
    int c;
    long node_value;
    char *ptr;
    char *token;
    const char s[2] = " "; /*Split optarg based on this string*/

It's generally considered good practice to declare variables as close to their usage as possible to limit their scope and reduce the number of variables readers and maintainers need to keep in their heads. In this case, only c needs to be declared at this point. The rest of the variables can be declared within the while loop's block or, by adding curly braces to make blocks inside the case labels.

    while((c = getopt(argc, argv, "pa:")) != EOF){

Note that if you drop the #include <unistd.h> you'll need to come up with an alternative to getopt. That should be pretty easy, but may complicate the code slightly. You may want to literally implement your own version of getopt but you may also settle for replacing this loop with a loop over the argv array that reads pairs of arguments at index i and i+1.

        switch(c){
        case 'p':
            print_nodes();

It's fine, and commonplace, to break out code into its own function. You may also prefer the aesthetics of it. However, for completeness, I'll mention one drawback. In this case print_nodes is only ever called from one place. You could copy its body here and avoid the function call. Most optimizing compilers will do this for you, so this won't result in a performance gain. What it will help, arguably, is readability.

Readers of main currently need to suspend their progress through this function and jump to another location in the file. They need to remember mappings of parameters to the corresponding values in main. Then when they're done reading print_nodes they need to remember where they were in main and jump back to that location in the file. Some text editors and IDEs can help with the jumping, but there is an increase in cognitive load that's caused by splitting out this code into another function and you might want to consider removing it until such time as you have multiple callers.

            break;
        case 'a':
            token = strtok(optarg, s); /*Split the string*/
            while(token != NULL){
                node_value = strtol(token, &ptr, 10); /*Convert each string to integer*/

As mentioned in some other code reviews, there are a couple of issues here. First is that strtol returns a long int and you're assigning it to just an int. Depending on the integer sizes of your platform, long int and int may not have the same size. You can fix this in several ways, but you may want to consider simply changing the values held in the linked list from int to long int. Alternatively, you may need to do some conversion and/or raise an error if the given value fits in long int but not in the sometimes-smaller int.

                if((*ptr) != 10 && (*ptr) != 0){ /*If it's not a newline or a null then invalid input*/

The second issue the lack of error checking. This error checking doesn't cover all of the error cases. If the user puts in a non-integer string such as foo then strtol will return 0. This is unfortunately difficult to detect as an error as 0 is a valid integer value. If the value is out of range, you can check errno to see if it's been set to ERANGE. This is expensive and awkward error handling, especially for such a simple function. You might consider writing your own version such as the one mentioned in the review by @pacmaninbw.

                    fprintf(stderr, "Invalid number: %c", *ptr);
                    exit(EXIT_FAILURE);

Also as mentioned in other reviews, calling exit is fine in such a small program but generally not a very good way to handle errors. This is especially true when handling program inputs that are outside of the code's control. Instead, most programs aim to gracefully fail by reporting the error (which you did) but then continue on. If the error is truly fatal to the program, as in this case, then exit may be warranted.

                }
                add_node(node_value);

As with print_nodes there is only one call site to add_node so you could consider moving its body here and removing add_node.

                token = strtok(NULL, s);
            }
            break;
        default:
            fprintf(stderr, "Unknown option %c, available options are '-p' and 'a'", c);
            break;

This error is handled by (indirectly) returning 0 (success). In the case of an invalid node value the error is handled by returning (via exit) the failure value. Since this is just as fatal of an error as above, you should return the same error code to indicate to the OS that the program has terminated with an error, not successfully.

        }
    }
    argc -= optind;
    argv += optind;

Changing these local variables is unnecessary at this point because neither is used before returning.

    return 0;

Like with your use of EXIT_FAILURE above, you should use EXIT_SUCCESS here. Doing so doesn't require the reader to know that 0 indicates success, even though that is common knowledge.

}

void add_node(int data){
    struct node *temp = head;

    if(temp == NULL){

head is never initialized by your code, so its value will be undefined the first time this function runs. Sometimes the compiler will initialize it to NULL for you, especially when building in "debug" mode so you may not have noticed this bug yet. When the compiler has not initialized head for you then it's exceedingly unlikely that it will happen to initially be NULL. In that case this if will be skipped and the (essentially random) memory pointed to by head will be accessed. It's also exceedingly unlikely that such memory will be available to your program, so the OS will almost certainly terminate your program with a "crash". The same goes for other uses of head, such as in print_nodes.

        head = malloc(sizeof(struct node));
        head->value = data;
        head->next_ptr = NULL;
        return;

Some programmers frown on "early returns" or "multiple returns". It's mostly a stylistic choice, but one you should be aware of. Instead, you could add an else and put the rest of the function in it.

    }

    while(temp->next_ptr != NULL){
        temp = temp->next_ptr;
    }

If you were to keep track of the "tail" or "end" of the list, as you do with head then you could skip this loop. It's actually an extremely expensive loop as it will continually read from memory scattered all through RAM. It's highly likely that every iteration of this loop will cause a CPU cache miss and the entire cache will need to be purged in order to be refilled with the memory at the next node's location. Keeping a "tail" pointer will require a tiny (4 or 8 byte) additional usage of memory but your code will execute much more quickly.

    if((temp->next_ptr = malloc(sizeof(struct node))) == NULL){
        fprintf(stderr, "Out of memory");
        exit(EXIT_FAILURE);
    }

Checking for a NULL return from malloc is usually a good idea, but in this case it is arguably unnecessary. If you're allocating a gigabyte then it's possible that the allocation will fail. If you're allocating one struct node (approximately 8-16 bytes) and the OS is unable to return that amount of memory then the computer is likely going to crash anyhow. You probably won't be able to even print the error as the system has basically no memory left. So in this case it's probably better to skip the check for the sake of reduced amount of code which means there's less to type, less to read, and the executable is smaller.

    temp = temp->next_ptr;
    temp->value = data;
    temp->next_ptr = NULL;
}

void print_nodes(void){
    struct node *temp = head;
    if(temp == NULL){
            printf("Linked list is empty\n");
    }
    for(temp = head; temp != NULL; temp = temp->next_ptr){
        printf("%i\n", temp->value);
    }
}

This is a "textbook" implementation of a singly-linked list in its simplest form. If, however, you wanted to go further there is an optimization that would greatly increase its performance and memory utilization efficiency. As I mentioned in the comment about traversing the list being extremely slow, this is largely due to each node existing in essentially a random location in memory. The exact location is beyond your control as malloc makes this decision. Also, malloc is likely to allocate a "block" of memory much larger than the 8-16 bytes you requested, which decreases your memory utilization efficiency. You're also making one call to malloc per node, which is quite slow in itself as malloc is quite slow and will result in even more cache misses.

To combat these problems, you could change how you allocate the nodes of the linked list. Currently you're allocating them one-by-one as you parse the command line arguments. Instead, you could count the number of command line arguments and allocate an array of that many nodes. This would be trivial if you also adjust the format of the command line parameters so that the node values are passed individually rather than as a single string containing all of them.

Once you have allocated this array of nodes it should be a simple matter of assigning each node's next_ptr to the address of the next node in the array and the value to whatever you parsed from the corresponding command line argument. Of course the last node's next_ptr should be set to NULL.

The advantage of this scheme is that all of the nodes will be stored sequentially in memory. When you access the first one, the CPU will cache the next several nodes in much faster memory such as L1 or L2 cache. As you traverse the list, you'll be accessing that cache instead of fetching from main system memory which is usually an order of magnitude slower.

This is, of course, an optional optimization that will slightly complicate your code just like keeping a tail pointer around. There are tradeoffs in complexity, memory, and performance to consider as I mentioned above and it's up to you to weight these concerns. Overall, good job on this program and I hope this code review was helpful!

\$\endgroup\$
  • \$\begingroup\$ Nice. Very thorough. \$\endgroup\$ – user127566 Apr 23 '17 at 9:27
6
\$\begingroup\$

Nice formatting, good variable and function names. I learned more about getopt() from the program (I used to have to write my own command line parsers)! Good use of system macros such as EXIT_FAILURE.

Using Typedef

If the code used typedef for the definition of node, the code might be slightly shorter and more readable:

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

Node *head;

void add_node(int data){
    Node* temp = head;

    /* ... */
}

void print_nodes(void){
    Node* temp = head;

    /* ... */
}

By using typedef a new type is created. This also might decrease the possibility of future errors by forgetting to put the struct in at some point. This stackoverflow question discusses why it might be good to use typedef.

Global Variables

Generally the use of global variables are frowned upon. When creating, reading and debugging code global variables can be affected by side affects and it can be very difficult to find where the problem is actually occurring. This stackoverflow question talks about when it is proper to use global variables.

It might be better if the global variable NODE *head was declared in main() and then passed by reference into each function that modified it, and passed by value into each function that only used it and didn't change it.

Passing head into each of the functions would make the following changed necessary:

        case 'p':
    /*+>*/  print_nodes(head);      /* Pass by value */
            break;


            while(token != NULL){
                node_value = strtol(token, &ptr, 10); /*Convert each string to integer*/
                if((*ptr) != 10 && (*ptr) != 0){ /*If it's not a newline or a null then invalid input*/
                    fprintf(stderr, "Invalid number: %c", *ptr);
                    exit(EXIT_FAILURE);
                }
    /* ++> */   add_node(node_value, &head);        /* Pass by reference */
                token = strtok(NULL, s);
            }


void add_node(int data, Node **head){
    Node* temp;

    if(*head == NULL){
        *head = malloc(sizeof(struct node));
        (*head)->value = data;
        (*head)->next_ptr = NULL;
        return;
    }

    temp = *head;
    while(temp->next_ptr != NULL){
        temp = temp->next_ptr;
    }

    if((temp->next_ptr = malloc(sizeof(struct node))) == NULL){
        fprintf(stderr, "Out of memory");
        exit(EXIT_FAILURE);
    }

    temp = temp->next_ptr;
    temp->value = data;
    temp->next_ptr = NULL;
}

void print_nodes(Node* head){
    Node* temp = head;
    if(temp == NULL){
        printf("Linked list is empty\n");
    }
    for(temp = head; temp != NULL; temp = temp->next_ptr){
        printf("%i\n", temp->value);
    }
}

This example might make the program safer and easier to debug and read.

Implicit Type Conversion

My compiler flagged the following line as an implicit type conversion:

            add_node(node_value);

because node_value is declared as a long rather than int,

    long node_value;

void add_node(int data) { /* ... */

If node_value needs to be a long because that's what strtok() is returning, it might be better to either change the input type for add_node() or to explicitly cast node_value in the call:

            add_node((int) node_value);

The actual warning message I get is implicit conversion loses integer precision: 'long to int' (Xcode 8.2 on El Capitan).

Functions that might be helpful

To implement a full linked list program some functions that might be helpful are:

NodePointer new_node(int value);
NodePointer delete_node_by_value(int value, NodePointer head);
NodePointer delete_node_by_pointer(NodePointer delete_target, NodePointer head);
NodePointer find_node(int value, NodePointer head);
void print_node(int value, NodePointer head);       // called by print_nodes

Use of the exit() Function

The use of the exit() function can be problematic, in a large software system that one is writing only a piece of, it would be better to return an error code from the add_node() function rather than call exit. In some cases such as operating systems calling exit() can have dire consequences (shut down).

The C programming language was originally created to implement operating systems and in some cases is still used for that purpose. While C doesn't have the exception throwing capabilities of C++, Java, C# and other more modern languages errors can be handled, either by returning error codes or using setjmp() and longjmp().

\$\endgroup\$
  • \$\begingroup\$ I object to your first point. Capital letters are usually reserved for macro names. typedef struct tag{} name is widely used, but simple struct name{} is also widely used, e.g. UNIX socket library. \$\endgroup\$ – Vorac Apr 22 '17 at 15:55
  • 1
    \$\begingroup\$ @Vorac I agree on both comments, all caps is definitely generally reserved for macro names. Sometimes it is important to point newer programmers at things they might not know such as typedef. \$\endgroup\$ – pacmaninbw Apr 22 '17 at 16:00
  • 1
    \$\begingroup\$ @Vorac based on your comment I changed the typedef from NODE to Node, and added references to a typedef tutorial and a stackoverflow question on when to use typedef. \$\endgroup\$ – pacmaninbw Apr 22 '17 at 16:08
  • 1
    \$\begingroup\$ Type-defining pointers has its place, but I would not recommend it for this application as hiding a variable's pointer nature tends to create errors. Example: This answer suggests NodePointer *head;, making head a pointer to a pointer to a structure. A compilation of that answer's code generates "warning: initialization from incompatible pointer type [-Wincompatible-pointer-types]". \$\endgroup\$ – chux - Reinstate Monica Apr 22 '17 at 17:08
  • \$\begingroup\$ @chux That was bothering me from the beginning, I've seen other people create typedef TYPE * TYPEPointer, I've never done it myself because it hides the pointer. I've removed the NodePointer type. \$\endgroup\$ – pacmaninbw Apr 22 '17 at 17:34
2
\$\begingroup\$

Only a bit to add beyond @pacmaninbw answer:

  1. Better to write code that gets to the point and avoid magic numbers. Then the comment becomes unnecessary. A new-line is not specified to be 10.

    // if((*ptr) != 10 && (*ptr) != 0){ /*If it's not a newline or a null then invalid ...
    
    if(*ptr != '\n' && *ptr != '\0') {
    
  2. Note: Code lacks robust error detection/handling in "string to long to int" conversion. Could use you own strtoi() or this or roll your own conversion like below:

    // return true if error
    bool parse_int(const char *token, int *value_int) {
      char *endptr;
      errno = 0;
      long value_long = strtol(token, &endptr, /* base */ 10);
      if (token == endptr) { // no conversion
        *value_int = 0;
        return true; 
      }
    
      #if INT_MAX < LONG_MAX
      if (value_long > INT_MAX) {
        *value_int = INT_MAX;
        errno = ERANGE;
        return true;
      }
      #endif
      #if INT_MIN > LONG_MIN
      if (value_long < INT_MIN) {
        *value_int = INT_MIN;
        errno = ERANGE;
        return true;
      }
      #endif 
    
      *value_int = (int) value_long;
      if (errno) {
        return true; // outside long range or other ID error
      }
      if (*endptr != '\n' && *endptr != '\0') { // junk at the end
        return true; 
      }
      return false;
    }
    
  3. By keeping variables local to where they are needed, rather than declaring them far above, it is easier to review.

    // long node_value;
    .... 12 lines
        while(token != NULL){
            long node_value = strtol(token, &ptr, 10); /*Convert each string to integer*/
            ...   
            add_node(node_value);
    

[Edit]

  1. Consider the following allocation styles. With OP's style, sizeof(struct node), is best validated as the right size by checking the head declaration some 50 lines above. Should head type change, through maintenance, there is an obligation to change code 50 lines below. The alternate style has neither of those short-comings. It is easier to code correctly, review and maintain.

    // OP's
    head = malloc(sizeof(struct node));
    
    // Alternate
    head = malloc(sizeof *head);
    
\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy