Doubly linked list implementation in C

Question

I'm quite new to C, and I'm looking for feedback on this (doubly) linked list code.

Once I get to the add and remove methods, I feel like the code goes downhill. I'm looking for any potential errors I haven't spotted, and improvements that could be made for efficiency/tidiness.

struct node {
 int data;
 struct node *next;
 struct node *previous;
};
struct listset {
 struct node *head;
 struct node *tail;
 int current_elements;
};
struct listset * new_listset(){
 struct listset *new_list = malloc(sizeof(struct listset));
 new_list ->head = NULL;
 new_list ->tail = NULL;
 return new_list;
};
struct node *listset_lookup(struct listset *this, int item){
 struct node *curr_elem = this->head;
 if(!curr_elem) return NULL;
 while(item != curr_elem->data){
 if(curr_elem->next==NULL)return NULL;
 curr_elem = curr_elem->next;
 }
 return curr_elem;
}
void listset_add(struct listset *this, int item){
 struct node *new_node = malloc(sizeof(struct node));
 new_node -> data = item;
 new_node ->next = NULL;
 if(!this->head) {
 new_node->previous = NULL;
 this->head = this->tail = new_node;
 }
 else{
 this->tail->next = new_node;
 }
 this->current_elements++;
}
void listset_remove(struct listset *this, int item){
 struct node *elem_remove = listset_lookup(this, item);
 if(!elem_remove) return;
 if(elem_remove->next && elem_remove->previous) elem_remove->previous->next = elem_remove->next;
 else if (elem_remove->previous && !elem_remove->previous){
 elem_remove->previous->next=NULL;
 this->tail = elem_remove->previous;
 }
 else{
 this->tail = NULL;
 this->head = NULL;
 }
 free(elem_remove);
}

• rolfl: In the listset_add you do not change the tail in the else block: this->tail = new_node

Answer 1

Your code is actually "off-topic" because it doesn't work. You should really include a short main that illustrates its use and allows it to be tested. All the same, here are some comments.

Be consistent with spacing. My preference is for no spaces around -> and for a space after keywords (if, while etc).

Variable naming. Your names are not to my taste, often too long:

• Rename previous as prev, current_elements as n_elements
• Rename this globally as list - this means nothing whereas list is clearly a list.
• Rename item as data. It is called data within the node structure so why not be consistent?
• new_listset would perhaps be more consistent with the other functions if named listset_new. It also needs a void parameter list.

Function listset_lookup tests the wrong condition in the loop. Better to test for the end of the list:

struct node *listset_lookup(const struct listset *list, int data)
{
 struct node *n = list->head;
 while (n) {
 if (data == n->data) {
 break;
 }
 n = n->next;
 }
 return n;
}

Notice also that the parameter list is const (as you don't alter it). Also note that writing this with a short variable name makes it much more readable compared to the dense text that results from a longer name. In a ten line function with only 3 variables there is really nothing wrong (and a lot right) with using such a short name.

Your listset_add is missing two terms in the else clause and should test for malloc failure (and return something to show whether it failed). I would also rename new_node as simple n - again, it is a short function (as most should be) and so this is ok.

static struct node* listset_add(struct listset *list, int data)
{
 struct node *n = malloc(sizeof(struct node));
 if (n) {
 n->data = data;
 n->next = NULL;
 if (!list->head) {
 n->prev = NULL;
 list->head = list->tail = n;
 } else {
 n->prev = list->tail; // new
 list->tail->next = n;
 list->tail = n; // new
 }
 list->n_elements++;
 }
 return n;
}

Your listset_remove is hard to read and wrong. Again, a shorter variable name would help. You should also avoid long lines such as:

if(elem_remove->next && elem_remove->previous) elem_remove->previous->next = elem_remove->next;

This is much clearer as:

if (n->next && n->previous) {
 n->previous->next = n->next;
}

All the same, it is perhaps wrong. And this:

else if (elem_remove->previous && !elem_remove->previous){

is quite clearly not sensible. You also don't decrement the element count. The correct function is:

static void listset_remove(struct listset *list, int data)
{
 struct node *n = listset_lookup(list, data);
 if (!n) return;
 if (n->prev) {
 n->prev->next = n->next;
 } else {
 list->head = n->next;
 }
 if (n->next) {
 n->next->prev = n->prev;
 } else {
 list->tail = n->prev;
 }
 list->n_elements--;
 free(n);
}

Here's what I used to test it:

static void listset_print(const struct listset *list)
{
 struct node *n = list->head;
 while (n) {
 printf("%d ", n->data);
 n = n->next;
 }
 printf(" : ");
 n = list->tail;
 while (n) {
 printf("%d ", n->data);
 n = n->previous;
 }
 printf("\n");
}
int main(void)
{
 struct listset *list = new_listset();
 listset_add(list, 1);
 listset_add(list, 2);
 listset_add(list, 3);
 listset_add(list, 4);
 listset_add(list, 5);
 listset_print(list);
 listset_remove(list, 6);
 listset_print(list);
 listset_remove(list, 1);
 listset_print(list);
 listset_remove(list, 5);
 listset_print(list);
 listset_remove(list, 3);
 listset_print(list);
 listset_remove(list, 2);
 listset_print(list);
 listset_remove(list, 4);
 listset_print(list);
 return 0;
}

Answer 2

The code of the list looks correct but the coding style is not neat yet. There are some suggestions:

• There are different recommendations on how to format the type of the pointers, but probably all agree that the character * is the part of the type. So it is better to always keep it near the type.
• The code is unreasonably compacted. It is good if you want to have a whole algorithm on one screen but most likely you will spend most of the time focusing on its particular aspects so the readability of the individual fragments prevails.
• develop a good habit of putting constants at the first place in logical expressions.
• it is cool that you know this trick a = b = NULL but you do not use it consistently in the code - anyway, it is better to not use it.
• prefer positive constructions in ifs because it is very easy to overlook just the single ! in the boolean expression.
• current_elements is not a quite right name for the variable that contains the size of the list. size is much better :)
• avoid unnecessary shorten variable names: is there a strong reason to use curr_elem instead of just current or element?

Logic

• consider calloc - it clears the memory so you do not need to null all the structure variables - they will be set to zeroes.
• listset_add should be revised - it does not set this->tail and new_node->previous if NULL != this->head
• listset_remove should be revised - it does not set elem_remove->next->previous correctly, elem_remove->previous && !elem_remove->previous is never true.
• list_free that releases all the elements and list itself in one operation will be very handy.

• William Morris: I don't agree that '*' is part of the type. If I define int *a, b; and int* a, b;, the second (which would be logical if the * is part of the type) gives the impression that b is a pointer to int, which it clearly isn't. Defining two variables in this way would be unwise, but is legal.
• TeaDen: Thank you for writing this up. By putting constants first do you mean for example: if(NULL == x) rather than if(x == NULL)?
• Alex Netkachov: The if (NULL == x) is better because the compiler will warn you if you forget one = and write if (NULL = x). The if (x = NULL) is valid construction that can be easy overlooked.
• Alex Netkachov: @WilliamMorris I understand you point but it is about C syntax which is clumsy sometimes, not about the concept. The code review is all about helping other to avoid what is legal and syntactically correct but unwise, isn't it?
• Corbin: Depends on the compiler. The short answer though is to just crank up warnings as high as they'll go and it will surely be included.

Answer 3

I will try not to repeat what was said in the comments and in Alex' answer.

In new_listset() you forgot to initialize current_elements to zero. If you replace malloc with calloc, you will not need to do that. In that case, you can also remove initializations of head and tail, since NULL == (void*)0.

I find your lookup a bit counter-intuitive. I'd do it like this:

struct node *listset_lookup(struct listset *this, int item){
 struct node *curr_elem = this->head;
 while (curr_elem) {
 if (curr_elem->data == item) return curr_elem;
 curr_elem = curr_elem->next;
 }
 return NULL;
}

or, even more intuitive (for me, at least):

struct node *listset_lookup(struct listset *this, int item){
 struct node *curr_elem;
 for (curr_elem = this->head; curr_elem; curr_elem = curr_elem->next)
 if (curr_elem->data == item) return curr_elem;
 return NULL;
}

There are several reasons I like it this way better.

1. This is a standard "go through the whole list and do something" loop, instead of your "do something special (loop until the element is found)".

2. My code doesn't have check for NULL on two places.

3. Each step is dealing with the "current" element. In your code, you have if checking the next element, which is an approach I prefer to avoid if it is reasonably possible.

Mind you, this is not a big deal, and it is alright if you want to keep your version.

Maybe a bit more important remark is regarding the listset_remove() function. I'd make it return int, which would be the count of the elements removed. This way, wherever you've called it, you would know if it has removed anything. You could also add a third parameter which would say how many items can be removed at most (zero for all of them), so that more than one item can be removed if some are equal among themselves.

By the way, you forgot to decrease this->current_elements in that function.

Lastly, I suggest adding checks if your malloc/calloc calls were successful.