A linked-list implementation

Question

I am new to C, and this is my first attempt at creating a linked list.

If anyone has a minute and could point out any errors or bad practices in this small linked list program, it would be really helpful.

note: I'm using the get_choice function to run a loop to either delete, insert, locate, print-out links, or exit.

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


struct Link_Data {

    int value;

    struct Link_Data *prev;

    struct Link_Data *next;
};

int main(int argc, char *argv[]) {

    char declare[] = "Begin...";
    printf ("%s\n", declare);

    struct Link_Data *head = malloc( sizeof *head );
    head->prev = NULL;
    head->next = NULL;
    head->value = 0;
    get_choice(head);

    return 0;
}

int get_choice(struct Link_Data *head) {

    int choice;
    int value;

    while ( true ) {    

        printf ("Enter 1 to delete, 2 to insert, 3 to locate, 4 to print_all, or 0 to quit: ");
        scanf ("%d", &choice);

        switch (choice) {

            case(1): 
                printf ("Enter value: ");
                scanf ("%d", &value);                
                delete_node(head, value);
                break;            

            case(2):
                printf ("Enter value: ");
                scanf ("%d", &value);                
                insert_node(head, value);
                break;

            case(3):
                printf ("Enter value: ");
                scanf ("%d", &value);                
                locate_node(head, value);
                break;

            case(4):
                printf ("Printing list...\n");
                print_links(head);
                break;

            case(0):
                return 0;
        }
    }
}

int delete_node(struct Link_Data *node, int value) {

    if (node->next == NULL && node->prev == NULL) {

        printf ("List is empty!\n");
        return 0;
    }

    else if (node->next == NULL && node->value != value) {

        printf ("Value %d not in list!\n", value);
        return 0;
    }

    else {
        if (node->value == value && node->prev != NULL) {

            printf ("Deleting %d...\n", value);
            struct Link_Data *prev = node->prev;
            prev->next = node->next;
            free(node);
        }
        else {
            delete_node(node->next, value);
        }
    }        
    return 0;
}

int insert_node(struct Link_Data *node, int value) {

    if (node->next == NULL) {

        printf ("Inserting %d...\n", value);
        struct Link_Data *new_link = malloc( sizeof *new_link );

        new_link->value = value;
        new_link->prev = node;
        new_link->next = NULL;

        node->next = new_link;
    }

    else {

        insert_node(node->next, value);
    }

    return 0;
}

int locate_node(struct Link_Data *node, int value) {

    if (node->next == NULL && node->value != value) {

        printf ("Value %d not in list!\n", value);
    }
    else {
        if (node->value == value) {

            printf ("Locating %d...\n", value);
            printf ("Value %d in list!\n", value);
        }
        else {

            locate_node(node->next, value);
        }
    }

    return 0;
}

int print_links(struct Link_Data *node) {

    if (node->prev == NULL && node->next == NULL) {

        printf ("List is empty!\n");
        return 0;
    }
    else {
        if (node->prev != NULL) {

            printf ("Value: %d\n", node->value);
        }
        if (node->next == NULL) {

            return 0;
        }
        else {

            print_links(node->next);
        }
    }

    return 0;
}

Vedran Šego · Accepted Answer · 2013-10-18 08:08:53Z

I was never a fan of a "fake first element"-approach. And here is why:

Begin...
Enter 1 to delete, 2 to insert, 3 to locate, 4 to print_all, or 0 to quit: 2
Enter value: 17
Inserting 17...
Enter 1 to delete, 2 to insert, 3 to locate, 4 to print_all, or 0 to quit: 3
Enter value: 0
Locating 0...
Value 0 in list!

So, if you're going to do that approach, be careful not to "locate" it or do anything else with it.

My second complaint is that you traverse your list using recursions. This is both slow and memory consuming on large lists. Just imagine a list with 1000 elements. Your insert_node will have 1000 recursive calls, each with its variables node and value on stack, which takes time to create there, and - when done - remove from there. I suggest you do all the list traversing using for or while loops. For example:

int locate_node(struct Link_Data *node, int value) {

    node = node->next; /* skipping the fake first node */

    while (node && node->value != value) node = node->next;

    if (node) {
        printf ("Value %d in the list!\n", value);
        return 1;
    } else {
        printf ("Value %d not in the list!\n", value);
        return 0;
    }
}

Another thing I have added here is the return value. You should either have void functions or make their return values meaningful. I've used 1 as "there is an element in the list" and 0 as "there is no such element in the list".

I'd also suggest removing output from such functions. They should get the job done (delete, insert, locate) and return a meaningful value, while any user output should be done outside of them.

Last, you create a doubly-linked list, but you don't seem to use prev anywhere except when deleting (which can be done without it), and even there you do not use it properly:

Begin...
Enter 1 to delete, 2 to insert, 3 to locate, 4 to print_all, or 0 to quit: 2
Enter value: 17
Inserting 17...
Enter 1 to delete, 2 to insert, 3 to locate, 4 to print_all, or 0 to quit: 2
Enter value: 19
Inserting 19...
Enter 1 to delete, 2 to insert, 3 to locate, 4 to print_all, or 0 to quit: 2
Enter value: 23
Inserting 23...
Enter 1 to delete, 2 to insert, 3 to locate, 4 to print_all, or 0 to quit: 1
Enter value: 19
Deleting 19...
Enter 1 to delete, 2 to insert, 3 to locate, 4 to print_all, or 0 to quit: 1
Enter value: 23
Deleting 23...
Enter 1 to delete, 2 to insert, 3 to locate, 4 to print_all, or 0 to quit: 3
Segmentation fault

The problem is that you do not fix your prev field of a node after the deleted one, so when you delete two consecutive nodes, the second delete works with a prev that was already freed.

I suggest you make a completely new, recursion-less program, using an ordinary singly-linked list, and without a fake header, and then open a new review request. This seems like a decent tutorial for the lists in C.

One final comment: a print_list function (and the option) would really make it easier for you to test your program.

I was not liking the "fake element" to start the list either. I went off of just knowing the idea of "linked lists" and wasn't sure of where to start it. So wanting to get going with things, I didn't worry too much about it. I will need to think about a better technique and study up on other approaches ;) Your recursion point never occurred to me but, that is probably because I've never had a program with those kinds of numbers(I'll keep it in mind). I'm not sure though when you say "fake header" what do you mean by this? — tijko
– tijko, Commented Oct 18, 2013 at 8:19
"fake header" = "fake element at the start of the list". I suggest you do not reinvent the wheel, but search the web for the resources on linked lists and see how to do them. You can even look at the previous reviews on this site. — Vedran Šego
– Vedran Šego, Commented Oct 18, 2013 at 8:51
As for "those kinds of numbers"... the whole point of linked lists is in handling large amount of data. If you're keeping 10 or 100 elements (or much more, if they're small like integers), you can just use the arrays. The differences show on large amounts of data. — Vedran Šego
– Vedran Šego, Commented Oct 18, 2013 at 8:55

Stack Exchange Network

A linked-list implementation

1 Answer 1

You must log in to answer this question.

Hot Network Questions

A linked-list implementation

1 Answer 1

You must log in to answer this question.

Related

Hot Network Questions