linked list in c code

Question

I have implemented linked list data structure in c.

linkedlist.h

#ifndef LINKED_LIST
#define LINKED_LIST

#include <stdbool.h>

struct linkedlist {
    int key;
    struct linkedlist* next;
    struct linkedlist* prev;
};

bool list_insert(struct linkedlist** p,int k);
struct linkedlist* list_search(struct linkedlist* p,int k);
bool list_delete(struct linkedlist** p,int k);
void list_show(struct linkedlist* p);
void memory_map(struct linkedlist* p);

#endif

list.c

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

bool list_insert(struct linkedlist** p,int k) {
    struct linkedlist* x = malloc(sizeof (struct linkedlist));
    if(!x) 
    {
        return false;       
    }
    x->key = k;
    x->prev = NULL;
    x->next = *p;   

    if(*p)
    {
        (*p)->prev = x;
    }   
    *p = x;
    return true;
}

struct linkedlist* list_search(struct linkedlist* p,int k) {
    if(!p) 
    {
        return NULL;
    }

    while(p != NULL)
    {
        if(p->key == k)
        {
            return p;       
        }
        p = p->next;        
    }
    return NULL;
}

bool list_delete(struct linkedlist** p,int k) {
    struct linkedlist* x = list_search(*p,k);
    if(!x) 
    {   
        return false;
    }   
    if(x->prev)
    {
        x->prev->next = x->next;
    }
    if(x->next)
    {
        x->next->prev = x->prev;
    }

    free(x);
    return true;
}

void list_show(struct linkedlist* p) {
    printf("\n[linkedlist][");
    while(p) 
    {
        printf("%d ",p->key);
        p = p->next;
    }
    printf("]");
}
void memory_map(struct linkedlist* p) {
        printf("\n[memory map for linkedlist]");
        while(p)
        {
                printf("\n%d : [%p]", p->key,p);
                p = p->next;
        }
}

main.c

#include <stdio.h>
#include "linkedlist.h"

int main() 
{
    struct  linkedlist* head = NULL;
    int i;
    for(i = 0; i < 5; i++) 
    {
        if(!list_insert(&head,i+1))
            printf("list_insert operation fails");
    }
    list_show(head);
    memory_map(head);   
    list_delete(&head,2);
    list_delete(&head,1);
    list_delete(&head,3);
    list_insert(&head,18);
    list_show(head);
    memory_map(head);
    return 0;
}

Answer 1

Naming

You should consider renaming or removing Your memory_map() function, all functions from Your linkedlist library does have a prefix list_, and this one does not. Also, it's kind a misleading. For user of Your library it might look like something related to mmap().

What does p, k, x mean? Please, consider using proper names for Your variables.

Verbosity

Just returning false in case of error usually is not verbose enough. I'd suggest considering proper error codes and/or proper error logger, for example something like this:

#ifndef LLIST_LOG
#define LLIST_LOG(format, ...) \
    fprintf(stderr, "LLIST_LOG: %s(): " format "\n", \
          __FUNCTION__, ##__VA_ARGS__)
#endif /* LLIST_LOG */

Consistency

Spacing and indentation is inconsistent. You should decide, how many spaces do You put between functions, how and when You separate if() {}, while() {}, arithmetical operations, etc blocks from each other or other logical parts of Your code. Or even better, use already defined C coding style, for example Linux kernel one.

Input verification

Rule of thumb, user of Your library is going to be dumb. And/or it will get messy debugging bigger project with Your library included. So, really, verify ALL the inputs. For example, Your list_delete(NULL, 1) segfaults.

Generic practices

Back to memory_map(), in general it's quite common to provide iterator function which calls some callback with every single element of the structure as a parameter instead. It's way more versatile.

It's common to suffix include guards by some randomly generated gibberish or hash, especially for such a common names as LINKED_LIST. Also, for compatibility with some compilers it usually defines it to some specific value. For example:

#ifndef LINKED_LIST_H_093e74eeda79fcc4c29e9d2986f5b701
#define LINKED_LIST_H_093e74eeda79fcc4c29e9d2986f5b701 1

Also, You should consider adding function list_create() and list_destroy() for Your library user not to mess with malloc() and free() directly and handle errors properly there.

Generic rant

There is a memory leak in Your example ;)

Answer 2

Some things to add to @Kamiccolo's fine answer.

Unneeded field struct linkedlist* prev. The only place this is really used, given the code set's limited functionality is in list_delete(). By noting the previous node, as code walks the list in that function, the prev field becomes redundant.

Unneeded code

struct linkedlist* list_search(struct linkedlist* p,int k) {
    // Removal of the below line does not change code functionally.
    // if(!p) { return NULL; }

    while(p != NULL) {
       ...
    }
    return NULL;
}

const Consider functions that do not change the list to use a const signature.

void list_show(const struct linkedlist* p) {

include To help show that "linkedlist.h" does not need a prior include in the example code of main(), swap order.

// #include <stdio.h>
// #include "linkedlist.h"
#include "linkedlist.h"
#include <stdio.h>

Style Minor: IMO, calling malloc() with a sizeof *pointer is easier to maintain and write.

// struct linkedlist* x = malloc(sizeof (struct linkedlist));
struct linkedlist* x = malloc(sizeof *x);

Clarity list_insert() inserts at the beginning of the list rather than at the end (or elsewhere). This property should be noted in the *.h file.

Naming Inconsistent naming list, linkedlist, LINKED_LIST, linkedlist.h, list.c. Recommend a consistent style (this adds to K's answer).

format printf() expects a format string, not a general string. Too easy to have a '%' appear in a future version of the string.

// printf("\n[linkedlist][");
fputs("\n[linkedlist][", stdout);
// or
printf("%s", "\n[linkedlist][");

Nit "%p" is for printing void*. Using a prefixed '\n' rather than a suffixed one, may not flush the buffer. Add fflush().

// printf("\n%d : [%p]", p->key,p);
printf("\n%d : [%p]", p->key, (void*)p);
....
fflush(stdout);

Debug For debug or security purposes, scrubbing memory, before free-ing, can help

#ifndef NDEBUG 
  memset(x, 0, sizeof *x);
#endif
free(x);