Singly Linked List C implementation

Question

I'm a C beginner. I'm studying and implementing some data structures. I'd like to get feedback about my style and decisions I made.

This is a Singly Linked List. I decided to keep things as simple as possible writing just the basic operations for the list.

In main there is some test code.

All the code is in one file because I'd like to store all these implementations in single files (as snippets) for future reference.

By the way this is the first time I post here, please don't be kind.

/*
 * Singly Linked List C implementation.
 *
 * Linear collection of data. Each element (node) contains data and a link to
 * the next node.
 * The first element is often called "head" and (a pointer to it) must be
 * preserved since without it, it's not possible to traverse the list.
 * The last element is linked (points) to nothing (NULL).
 *
 * ----------- ----------- ----------- ----------- ------
 * | 17 | --|---->| 3 | --|---->| 22 | --|---->| 11 | --|---->|NULL|
 * ----------- ----------- ----------- ----------- ------
 * ^
 * HEAD
 *
 * Search: O(n): search operations are performed in linear time.
 * Insert: O(1): since all new nodes will replace the head.
 * Delete: O(n): since we are deleting the first occurrence of a specific data.
 */
#include <stdlib.h>
typedef struct node
{
 int data;
 struct node *next;
} node;
/*
 * insert: creates and inserts a new node (storing data) in the list pointed by
 * the pointer stored at address head.
 * Returns the pointer of the new node or NULL if the process failed.
 */
node *insert(node **head, int data)
{
 if (head == NULL) {
 return NULL;
 }
 node *new = malloc(sizeof(*new));
 if (new != NULL) {
 new->data = data;
 new->next = *head;
 *head = new;
 }
 return new;
}
/*
 * delete: delete the first occurrence of data (i.e the first node which has
 * data in its data field) in the list pointed by the pointer stored at
 * address head.
 * Returns 1 if a node has been deleted, 0 otherwise.
 */
int delete(node **head, int data)
{
 if (head == NULL) {
 return 0;
 }
 node *prev = NULL;
 node *curr = *head;
 while (curr != NULL) {
 if (curr->data == data) {
 if (prev == NULL) {
 *head = curr->next;
 } else {
 prev->next = curr->next;
 }
 free(curr);
 return 1;
 }
 prev = curr;
 curr = curr->next;
 }
 return 0;
}
/*
 * destroy: delete all nodes in the list pointed by the pointer stored at
 * address head, then sets *head to NULL implying an empty list.
 */
void destroy(node **head)
{
 if (head == NULL) {
 return;
 }
 node *curr = *head;
 node *next;
 while (curr != NULL) {
 next = curr->next;
 free(curr);
 curr = next;
 }
 *head = NULL;
}
/*
 * find: returns 1 if there is at least one occurrence of data in the list
 * pointed by head, 0 otherwise.
 */
int find(node *head, int data)
{
 node *trav = head;
 while (trav != NULL) {
 if (trav->data == data) {
 return 1;
 }
 trav = trav->next;
 }
 return 0;
}
#include <stdio.h>
void print_list(node *head);
int main(void)
{
 int n;
 node *head = NULL;
 for (n = 0; n < 10; n++) {
 insert(&head, n);
 }
 print_list(head);
 printf("Deleting all elements...\n");
 for (n = 0; n < 10; n++) {
 delete(&head, n);
 }
 print_list(head);
 printf("Inserting other elements...\n");
 insert(&head, 25);
 insert(&head, 49);
 insert(&head, 57);
 insert(&head, 22);
 insert(&head, 90);
 insert(&head, 27);
 insert(&head, 22);
 print_list(head);
 for (n = 20; n < 30; n++) {
 printf("Looking for %i: ", n);
 if (find(head, n)) {
 printf("%i is in the list\n", n);
 } else {
 printf("%i is not in the list\n", n);
 }
 }
 printf("\n");
 n = 57;
 printf("Deleting first occurrence of %i...\n", n);
 delete(&head, n);
 print_list(head);
 n = 22;
 printf("Deleting first occurrence of %i...\n", n);
 delete(&head, n);
 print_list(head);
 printf("Deleting head...\n");
 printf("Current head: pointer: %p data: %i\n", head, head->data);
 delete(&head, head->data);
 printf("Head after deletion: pointer: %p data: %i\n", head, head->data);
 print_list(head);
 n = 25;
 printf("Deleting last node...\n");
 delete(&head, n);
 print_list(head);
 printf("Trying functions with NULL head or not stored data...\n");
 printf("insert(NULL, 33) returns %p\n", insert(NULL, 33));
 printf("find(NULL, 90) returns %i\n", find(NULL, 90));
 printf("delete(NULL, 90) returns %i\n", delete(NULL, 90));
 node *null_h = NULL;
 printf("\nnode *null_h = NULL;\ndelete(&null_h, 90) returns %i\n\n",
 delete(&null_h, 90));
 printf("delete(&head, 33) returns %i\n", delete(&head, 33));
 printf("destroy(NULL)\n");
 destroy(NULL);
 print_list(head);
 printf("Destroying the list\n");
 destroy(&head);
 print_list(head);
}
void print_list(node *head)
{
 printf("List: ");
 if (head == NULL) {
 printf("is empty");
 } else {
 node *trav = head;
 while (trav != NULL) {
 printf(" %i ", trav->data);
 trav = trav->next;
 }
 }
 printf("\n\n");
 return;
}

• Deduplicator: I suggest you not swallow errors. Doing so just makes debugging harder.
• MarcoLucidi: @Deduplicator You mean in main? Can you be more specific?
• Deduplicator: No, I mean insert and destroy simply returning when not handed a list.
• MarcoLucidi: @Deduplicator well, insert returns NULL (failure), probably I should change destroy to return a bool (or int) though. Anyway, what do you suggest for "not swallow errors"?
• MarcoLucidi: @Deduplicator programming error. I see your point now (I guess), you are suggesting to not test head against NULL because if that will ever happen would be a programming error indeed, hard to detect, and so, leave the program crash while dereferencing, would be better in order to spot the error. Did I understand well?

Answer 1

Include all library headers near the beginning of the file

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

This has the following advantages:

• Gives readers a quick glance at the libraries used throughout the source file.
• Results in more comprehensible error messages when your declarations clash with those in an included header.
• Avoids potential surprises if a header file alters macro definitions or compiler settings that affect subsequent code.

Avoid identifiers that clash with keywords of similar languages

new and delete are C++ keywords and C code is commonly included in C++ programs. Therefore it would be better to avoid these and other identifiers that happen to be C++ keywords.

You can use something like new_node to refer to a newly created node structure instead.

See the next section for a better name for delete.

Use more descriptive function names

insert, delete and destroy (and other verbs) aren't very descriptive because they're ambiguous on what to [verb]. Use something like [verb]+[noun], e. g. insert_element, delete_element, destroy_list. You already do that with print_list.

Use puts or fputs to print fixed strings

puts("Deleting all elements...");

or

fputs("Deleting all elements...\n", stdout);

You can use puts or fputs instead of printf to print fixed strings. The former are simpler than the latter and have no drawback in the absence of format arguments. Additionally, you don't need to quote % characters.

Some compilers (e. g. GCC) will optimise calls to printf with fixed strings without format specifiers to calls to puts/fputs.

Watch out that puts appends a new-line character at the end of the string while fputs doesn't.

• MarcoLucidi: Yeah, the headers, since I want to store these implementations as snippets for future reference, I'd like that only the headers required by the implementation are at the top. stdio.h is not necessary for the list itself, (neither print_list nor that main), I added it only for test purpose, that's why it is at the bottom. Probably I should have specified it better, my bad, I'm sorry. Definitely I'm going to change those trivial and ambiguous names and thank you for the puts advice, I'll use it from now on!

Answer 2

Hm... is the use of names like new and delete intentional? While perfectly legal, it might provoke confusion (in a "mixed" project), or even become a hindrance one day when re-using library code.

Suggestion: maybe find could return a node* (or NULL). So one could easily use the return value for editing the node value, deleting the node, or inserting before the node.

• Edward: To be clear, this is because new and delete are keywords in C++. In a pure C project, there's nothing inherently wrong with them.
• MarcoLucidi: Silly me, the thing is that I never programmed in C++ nor in a "mixed" project of course. Definitely I'm going to change those trivial and ambiguous names. Thank you for the find suggestion, maybe I'll implement in that way, but I guess you mean insert after the node, since I have only the next pointer. Even deleting a node would be tricky knowing only the pointer returned by find. Am I wrong?
• jvb: @MarcoLucidi Then you've got a good taste in naming functions ;) If you return trav in find, one could use it to change the "found" value. Less obvious: "insert before" is possible, too (by the way, it's the standard behaviour in C++). I'll refer to the found item as current here, as in node *current=find(head, val). Of course, insert can't change the pointer to current... but you can copy "current" data/next into the new item, then the value to be inserted into "current", and let current->next point to the new item.
• MarcoLucidi: @jvb ahh yeah, that's fair! Though doing that could "invalidate" a variable storing the pointer of a specific node (because of the data change), but I guess is an uncommon case.

Answer 3

a typedef is handy to define a linked list type:

typedef node* llist;

and use that in place of **node.

There is an advantage to NOT storing any data in the Head of a list, instead putting a sentinel value in it instead (like -1, or INT_MAX) and defining a few utility functions.

is_head(node *n) { return (n->data == INT_MAX); }
is_last(node*n) { return (n->next == NULL); }
is_empty(llist l){ return ( (*l)->next == NULL);} 

You just have to remember to skip over the head nodeto head->next every time you are accessing the list.

It is notable that your insert function inserts at the beginning and not at the end of the list. This is how a stack works, but stacks use push() and pop() , removing the beginning. Most singly linked-lists append data to the end with their next pointer set to NULL, unless stack behavior is wanted, and keep the list head stable for the life of the list. Changing the head node to a new struct every insert, while no problem for the computer is more likely to be a problem later on if you send your list into a function which changes it, and sends back a different address.

It looks as if you are duplicating the find function inside the delete function. It may be more useful for find() to return a node* to the node found or NULL if not found, and have delete take the list and the node to delete as parameters.

node* n = find( 100); 
if(n) delete(list, n); 

The thing about a singly-linked list that has an advantage over an array is that insertion and deletion leave all the other nodes in the same place and any variables pointing to any individual node are still valid. To insert or delete data into the middle of an array requires resizing it and shifting every item after the insert or delete, and all the data after is in a different memory location, unless you only insert at the very end. So you need to write a couple of node functions:

insert_after() /* after a node */
insert_before() /* before a node */
append() /* insert at end */
prepend() /* insert after head */
set_data() /* change the data, leave the node */
get_data() /* get the data from the node */
push() /* stack prepend to top*/
pop() /* get_data and delete from top */
swap() /* if you want to sort a list. */

• Cody Gray: I have to disagree with the very first suggestion in this answer. It is almost never a good idea to hide a pointer behind a typedef. It just creates confusion and invites bugs.
• MarcoLucidi: I thought about not storing anything in the head but it looked like a wasted node and for simplicity I stated that NULL represents an empty list. Inserting a node at the end, would require to traverse the list at each insertion since I'm not storing the tail (again for simplicity). In order to make delete work that way I have to traverse the list twice since I'll lose the pointer to the previous node (Am I right?). I'll write those functions when and if I'll need them because this is meant to be a minimal implementation.
• Chris Reid: A deletion of a node involves 3 node pointers. parent->next , current , current->next There's only one way to do it usually; its in all the books. Why reinvent the wheel? Some of these things you learn by copying.
• MarcoLucidi: @ChrisReid I think I'm aware about the pointers involved in a deletion. I'm asking, following your suggestion, where do I take parent to change parent->next without loop through the list again? (by the way, that's why I duplicated a bit of find in delete).

Answer 4

1. As the insert(node **head, int data) function receives pointer to the head node as its first argument you could rather use bool or int as a return value, to check whether the operation was successful.

   unless you are doing the other way around (depending on returne value to modify head node), the return value (node *) has the same significance of any other type that holds status. so why not use int. (like the other subroutines).

2. As others have mentioned indentation of 4 spaces is optimal for statements inside a block.

3. Make good use of the return values if they deserve.

   
   

   minor

   I'd prefer not to make single statement as block. Both are the same it's just a choice you have.

• MarcoLucidi: Yeah, probably would be better return a bool (or int) for success or failure in insert. Thank you for the suggestions.

Answer 5

1. Put all your #includes at the top of your source file.
2. Use variable names that are full words - let the IDE do the repetitive typing via autocompletion.
3. destroy() seems kind of weird as a name - why not free_list()?
4. In print_list and other places, trav, for "traverse", should also be named as current, as in the rest of the code.
5. It is standard practice to put the declaration (interface) in a separate header file - however, it seems you're aware of this and you've avoided doing this deliberately for good reason, so I won't dwell on this further.
6. Your indentation is non-standard: 4 spaces to a tab is considered standard by most programmers.
7. You do not follow a consistent bracing style between functions and statement blocks - use the same for both.
8. You sometimes leave a useless line break after the body of the if - if this is intentional, be consistent.
9. An explicit return is not required at the end of a method of return type void, as in print_list.
10. Try not to use new or delete as variable names - it makes your code uncompilable by a C++ compiler as they are C++ keywords which occur in identifier positions in your code, although the rest of the code is undoubtedly valid C++, too.
11. Use the Boolean data type to indicate true/false conditions - in a C99-compliant (or above) compiler (say, gcc with the std=c99 option passed to it), the type bool and the macro literals true and false are available from the header file stdbool.h.

Given all the above, there are no logical issues with your code that I can find.

• MarcoLucidi: Thank you for all your points, I'd like to reply to few of them: 4. I used trav when only a pointer was sufficient, prev, curr and next when multiple pointers were required; 6. 7. I try to follow the "Linux Kernel style"; 8. is intentional when the line after the if is long or a bit "cryptic" or when the first character is *, since, without a full blank line it doesn't look "clean" (to me) on my editor.
• Tamoghna Chowdhury: 4. My advice about using whole names for variables still holds; I was not aware of your specific issues, so I gave generalized advice.

Answer 6

in printList(), this line:

if (head == NULL) {

is not correct for determining if the list is empty. After all, that is the address of the head variable in main(), not the contents of head. I.E. the pointer needs to be dereference to get the contents of 'head'. Suggest:

if ( NULL == *head ) {

Note. placing the literal on the right in such a comparison is highly prone to the keypunch error of typing = instead of == not being caught by you. By placing the literal on the left, the compiler will flag such a keypunch error rather than you having to develop lots of gray hairs trying to debug the problem.

• MarcoLucidi: The declaration for print_list is void print_list(node *head);. head is a simple pointer, not a pointer to pointer. With your suggestion, the code doesn't even compile (have you try it?). If you notice, the functions that "write" the list (i.e add or delete nodes) take a pointer to pointer, while functions that only need to "read" the list, take a simple pointer.
• user3629249: @MarcoLucidi, regarding: my statement about the checking of the POINTER to head, in printlist(), , the parameter head is defined as *head. So the actual contents of the pointer is NOT the contents of the callers' head, but rather the address of the callers' head, so checking that address for 'NULL' is an error while checking the contents of head because it 'could' be NULL.