3
\$\begingroup\$

I posted a couple of weeks ago with a double linked list. It was recommended that I rewrite the code as a singlely linked list and replace the recursive parts with loops.

I've gone ahead and made several edits and was hoping to get another critique of the code.

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


struct file {
    int fd;
    struct file *next;
};

struct file *create_head(void) {
    struct file *first_link = malloc ( sizeof *first_link );
    return first_link;
}

void insert(struct file *node, int val) {
    while (node->next != NULL) {
        node = node->next;
    }
    struct file *tail = malloc ( sizeof *tail );
    node->next = tail;
    tail->fd = val;
    tail->next = NULL;
}

int delete(struct file *node, int val) {
    struct file *prev;
    while (node->fd != val) {
        if(!(node->next)) {
            return 1;
        }
        else {
            prev = node;    
            node = node->next;
        } 
    }
    prev->next = node->next;
    free(node);       
    return 0;
}

int locate(struct file *node, int val) {
    while (node->fd != val) {
        if (!(node->next)) {       
            return 1;
        }
        else {
            node = node->next;
        }        
    }
    printf ("Value %d in list\n", val);
    return 0;
}

void dump(struct file *node) {
    while (node->next) {
        printf ("Node: %d\n", node->fd);
        node = node->next;
    }
    printf ("Node: %d\n", node->fd); 
}

int get_choice(void) {
    int choice;
    int val;
    struct file *head = NULL;
    while ( true ) {
        printf ("\n[Choices - Insert=1, Delete=2, Locate=3, Dump=4, Exit=5]\n");
        printf ("\nEnter selection: ");
        scanf("%d", &choice);
        switch (choice) {
            case (1): 
                printf ("Enter value: ");
                scanf ("%d", &val);
                if (!(head)) {
                    head = create_head();
                    head->fd = val;
                    head->next = NULL;
                }
                else {
                    insert(head, val);
                }
                break;
            case (2):
                if (head) { 
                    printf ("Enter value: ");
                    scanf ("%d", &val); 
                    if (head->fd == val && head->next == NULL) {
                        head = NULL;    
                    }
                    else if (head->fd == val && head->next != NULL) {
                        free (head);
                        head = head->next;
                    }
                    else if (delete(head, val) == 1) {                
                        printf ("Value %d not in list\n", val);
                    }
                }
                else {
                    printf ("List is empty!\n");
                }
                break;
            case (3): 
                if (head) {
                    printf ("Enter value: ");
                    scanf ("%d", &val); 
                    if (locate(head, val) == 1) {
                        printf ("Value %d not in list\n", val);
                    }
                }
                else {
                    printf ("List is empty!\n");
                }
                break;
            case (4): 
                if (head) { 
                    dump(head);
                }
                else {
                    printf ("Nothing to dump!\n");
                }
                break;
            case (5): 
            return 0;
        }
    }
}

int main(void) {
    printf ("\nSingle Linked List: \n");
    get_choice();
    return 0;
}
\$\endgroup\$
3
\$\begingroup\$

Stylistic/Function

  1. Your list holds values of type int yet you named the node type very specific in relation to file descriptors which will be a bit weird if you make a list of lets say prime numbers you want to operate on. Consider renaming your node type to something more generic rather than file (especially sincere there is a FILE type in <stdio.h>)
  2. Your insert method actually doesn't insert an element, it appends it to the end so it should be named append.
  3. delete doesn't work when the node you want to delete is head. I know you handle that case separately in get_choice but it's still bad that the caller has to know that fact. It also clutters the code with lots of special handling.
  4. dump is a bit weird: It skips the first one, then prints all following nodes in order and then prints the first one. So while it prints out all nodes I'd say it's still unexpected from a usage point of view.
  5. None of your methods can deal with the fact if NULL is being passed in.
  6. If you typedef your structs then you can save some typing work.

Structural/Design

  1. Your list does not have a nice API to use. You can see that in get_choice which is cluttered with handling of many special cases.
  2. Some methods like insert (size/length would be a different candidate) are inefficient as you have to iterate the entire list first. You could avoid that by keeping a separate tail pointer.

I suggest you create a list object which holds head, tail and possibly length of the list and all your methods should operate on an object of that list type rather than nodes. Something along these lines:

typedef struct node_
{
    int value;
    struct node *next;
} node;

typedef struct list_
{
    struct node *head;
    struct node *tail;
    int length;
} list;

And then define some methods to operate on:

// creates a new empty list
list *new_list()
{
}

// deletes the list and all the nodes
void delete_list(list *l)
{
}

// appends new value to the list
void append(list *l, int value)
{
}

// insert a value at a given position
void insert(list *l, int value, int position)
{
}

// deletes the first node with the given value from the list
// return 1 if node found and deleted, 0 otherwise
int delete_item(list *l, int value)
{
}

// returns the first node with the given value or NULL if not found
node *find(list *l, int value)
{
}

// prints the content of the list
void print_list(list *l)
{
}

Your get_choice method would then look like this:

int get_choice(void) {
    int choice;
    int val;
    list *myList = new_list();
    while ( true ) {
        printf ("\n[Choices - Insert=1, Delete=2, Locate=3, Dump=4, Exit=5]\n");
        printf ("\nEnter selection: ");
        scanf("%d", &choice);
        switch (choice) {
            case (1): 
                printf ("Enter value: ");
                scanf ("%d", &val);
                append(myList, val);
                break;
            case (2):
                if (myList->length > 0) { 
                    printf ("Enter value: ");
                    scanf ("%d", &val); 
                    if (!delete_item(myList, val))
                    {               
                        printf ("Value %d not in list\n", val);
                    }
                }
                else {
                    printf ("List is empty!\n");
                }
                break;
            case (3): 
                if (myList->length > 0) {
                    printf ("Enter value: ");
                    scanf ("%d", &val); 
                    if (find(myList, val) == NULL) {
                        printf ("Value %d not in list\n", val);
                    }
                }
                else {
                    printf ("List is empty!\n");
                }
                break;
            case (4): 
                if (myList->length > 0) { 
                    print_list(myList);
                }
                else {
                    printf ("Nothing to dump!\n");
                }
                break;
            case (5): 
            return 0;
        }
    }
}
| improve this answer | |
\$\endgroup\$
  • \$\begingroup\$ these points are all very enlightening. Especially testing for NULL and having the separate list to track. \$\endgroup\$ – tijko Nov 3 '13 at 4:47

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.