1
\$\begingroup\$

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;
}
\$\endgroup\$
1
\$\begingroup\$

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

\$\endgroup\$
  • \$\begingroup\$ Nice suffix idea for LINKED_LIST_H_093e74eeda... \$\endgroup\$ – chux - Reinstate Monica Apr 26 '16 at 23:10
1
\$\begingroup\$

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);
\$\endgroup\$

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.