HiveBrain v1.2.0
Get Started
← Back to all entries
patterncMinor

Linked list C implementation

Submitted by: @import:stackexchange-codereview··
0
Viewed 0 times
listimplementationlinked

Problem

I'm reading a data structure and algorithm book in C. I have implemented a generic single linked list in the C programming language, and I want to know your opinion on my implementation:

linked_list.h

#ifndef LINKED_LIST_H_INCLUDED
#define LINKED_LIST_H_INCLUDED

#define list_size(list) (list->size)    

#define list_head(list) (list->head)    
#define list_tail(list) (list->tail)
#define list_is_head(list, element) (element == list_head(list))
#define list_is_tail(list, element) (element == list_tail(list))

#define list_append(list, data)     list_ins_next(list, list->tail, data)
#define list_preprend(list, data)   list_ins_next(list, NULL, data)

#define list_data(element)  (element->data)
#define list_next(element)  (element->nextElmt)

typedef struct ListElmt_{
    void *data;
    struct ListElmt_ *nextElmt;
} ListElmt;

typedef struct List_{
    ListElmt *head;
    ListElmt *tail;
    size_t size;    
    void (*destroy)(void *data);
    int (*cmp)(const void *fdata,const void *sdata);
}List;

List *list_init(void (*destroy)(void *data), 
        int (*cmp)(const void *fdata, const void *sdata));
void list_destroy(List *list);
int list_ins_off(List *list, size_t off, void *data); 
int list_ins_next(List *list, ListElmt *element, void *data); 
int list_drem_next(List *list, ListElmt *element);
int list_rem_next(List *list, ListElmt *element, void ** data);
ListElmt * list_find(List *list, void *data, ListElmt *sElmt);

#endif


linked_list.c

```
#include

#include "linked_list.h"

List list_init(void (destroy)(void *data),
int (cmp)(const void fdata, const void *data))
{
List *rlist;

if((rlist = malloc(sizeof *rlist)) != NULL) {
rlist->head = NULL;
rlist->tail = NULL;
rlist->size = 0;
rlist->destroy = destroy;
rlist->cmp = cmp;
}

return rlist;
}

void list_destroy(List *list) {

ListElmt * el;
void *data;

while( (el=list_head(list)) != NULL) {
list

Solution

In order of appearance:

-
list_init

While destroy is definitely a property of the list, cmp is not; it is a property of a particular searc. Only find really cares of how to compare elements. It is better to pass a comparator to find directly.

-
list_desroy

may and should take advantage of knowing the list size. If perchance the list is corrupted, it is possible that the (el=list_head(list)) != NULL condition is never satisfied, and the loop becomes infinite. Counting iterations gives you an ability to fail gracefully.

-
Insertions

Naming is questionable. list_ins_next should be list_insert_after; list_ins_off should be list_insert_at. In any case, do not abbreviate insert.

-
Removals

The purpose of list_drem_next is quite unclear. Why to destroy data of the next element? It is much more straightforward to destroy data of this element. In any case, you must nullify the data pointer once data are destroyed.

The name itself is also questionable. list_destroy_data sounds better.

-
Missing functionality

There is no way to remove the head element.

Context

StackExchange Code Review Q#67953, answer score: 7

Revisions (0)

No revisions yet.