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;
}

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.

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.

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. */

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.

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.

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.