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!