Doubly linked list in C

Question

While I'm training to get better at C, I tried my hand at making a doubly linked list implementation.

linkedlist.h

#ifndef LINKED_LIST_H_
#define LINKED_LIST_H_
#include <stdlib.h>
typedef struct node {
 void* data;
 struct node *next;
 struct node *prev;
} node;
typedef node* pnode;
typedef struct List {
 pnode head, tail;
} *List;
List init_list();
void push_back(List, void*);
void* pop_back(List);
void push_front(List, void*);
void* pop_front(List);
void foreach(List, void (*func)(void*));
void free_list(List);
void clear(List);
int size(List);
#endif /* LINKED_LIST_H_ */

linkedlist.c

#include "linkedlist.h"
List init_list() {
 List list = (List)malloc(sizeof(struct List));
 list->head = NULL;
 list->tail = NULL;
 return list;
}
void push_back(List list, void* data) {
 pnode temp = (pnode)malloc(sizeof(struct node));
 temp->data = data;
 temp->next = NULL;
 temp->prev = NULL;
 if(!(list->head)) {
 list->head = temp;
 list->tail = temp;
 } else {
 list->tail->next = temp;
 temp->prev = list->tail;
 list->tail = list->tail->next;
 }
}
void push_front(List list, void* data) {
 pnode temp = (pnode)malloc(sizeof(struct node));
 temp->data = data;
 temp->next = NULL;
 temp->prev = NULL;
 if(!(list->tail)) {
 list->head = temp;
 list->tail = temp;
 } else {
 list->head->prev = temp;
 temp->next = list->head;
 list->head = list->head->prev;
 }
}
void* pop_front(List list) {
 if(!(list->tail)) return NULL;
 pnode temp = list->head;
 if(list->head == list->tail) {
 list->head = list->tail = NULL;
 } else {
 list->head = list->head->next;
 list->head->prev = NULL;
 }
 void* data = temp->data;
 free(temp);
 return data;
}
void* pop_back(List list) {
 if(!(list->head)) return NULL;
 pnode temp = list->tail;
 if(list->tail == list->head) {
 list->tail = list->head = NULL;
 } else {
 list->tail = list->tail->prev;
 list->tail->next = NULL;
 }
 void* data = temp->data;
 free(temp);
 return data;
}
void free_list(List list) {
 while(list->head) {
 pop_back(list);
 }
 free(list);
}
void clear(List list) {
 while(list->head) {
 pop_back(list);
 }
}
void foreach(List list, void(*func)(void*)) {
 pnode temp = list->head;
 if(temp) {
 while(temp) {
 (*func)(temp->data);
 temp = temp->next;
 }
 }
}
int size(List list) {
 int i = 0;
 pnode temp = list->head;
 while(temp) {
 i++;
 temp = temp->next;
 }
 return i;
}

Can you please point out any flaws, errors, stupid mistakes, general improvements, which can make this code better and "C'ish"?

• Calak: Why are you defining struct type aliases?
• Bhargav Kulkarni: @Calak Because, I don't want to keep writing struct again and again.

Answer 1

Welcome on Code Review

Generalities

Includes

You don't need #include <stdlib.h> in linkedlist.h, so remove it and instead, just add it in linkedlist.c right after #include linkedlist.h.

Name collisions

I'll discuss no more this subject after but be aware that names like node, list, size or clear for example, are very usual and subject to collisions. Consider using more robust names, maybe with a prefix.

Usable interface

Since the user look at your header file to know how to use your functions, a good habit is to to name the arguments, that's make the interface more explicit. Furthermore, adding documentation as comments about your interface help them to use it correctly.

Use the const keyword

Read this and this to know when et how.

Assertions and error-checking

You could use assertions to check preconditions, postconditions and invariants. It make your code more explicit and you avoid possibly broke you code when modifying.

• How to use assertions in C

• How and When to Use C's assert() Macro

• Why should I use asserts? (for C++ but still applicable)

---

struct node

[typedef] struct [tag] { ... } [alias];

Personally, I try to avoid to use sames ''struct tag'' and ''typedef name'' if I have to typedef a struct. It's completely a matter of taste, since "modern" compilers (for more than 20 years) can handle this easily, but so, user know when he work with the tag or the alias.

But there are many others "conventions":

• Some prefer "untagged aliased struct" (if there are no self-referencing members).
• Where others says to never typedef a struct.
• ...

Consistency

No matter where you place asterisk for pointers, try to be consistent through your code:

void* data;
 ^ LEFT-ALIGNED
struct node *next;
 ^ RIGHT-ALIGNED

(here is another talk on this endless debate)

So IMHO, this is cleaner:

typedef struct node node_t;
typedef node_t* node_ptr;
struct node {
 void* data;
 node_ptr next;
 node_ptr prev;
};

---

struct List

Consistency

The first letter of the struct node is lowercase, while the first of the struct List is uppercase.

Variables declaration

Try to don't declare several variables on the same line, it will avoid you many problems.

typedef struct list list_t;
typedef list_t* list_ptr;
struct list {
 node_ptr head;
 node_ptr tail;
};

---

init_list(), push_back(), push_front()

• There's no need to cast the return type of malloc from void* since it's implicitly converted to any pointer type.

• You can also omit the struct as you aliases it.

• Optionally, you could make more concise using calloc and rid of the manual initialization of next and prev (with few costs).

• Since you have a free_list function, consider renaming init_list to alloc_list

• For push_* function, you should use sizeof *list->head instead of using the type. It's easier to maintain. (e.g. if you modify the node type latter, the change here is automatic)

• For push_* function, you could return an int, an enum or a bool (via <stdbool.h>) to indicate the success of the insert (since the malloc can fail) or a pointer to the new created node (and so NULL in case of fail). No matter how but you should always handle errors when using malloc

pop_back(), pop_front()

• I find multiples assignments on same line less readable, but that's my opinion.
• For info: On some not-wide-used platforms (PalmOS, 3BSD, and other non ANSI-C compatibles), you should check for NULL before freeing to avoid crashes.

clear()

• You could rewrite the cleaning algorithm to be more efficient since you discard return values.

free_list()

• Simply use clear before freeing, to avoid code duplication.

• sineemore: @Calac, awesome answer! I'm not the OP, but I really enjoyed reading the post. Thanks!

Answer 2

The method free_list(list) should internally use clear(list), instead of duplicating the code for clearing the list.

The method clear(list) should not use pop_back(list), which does a lot of checks and pointer assignments, which are discarded by the next pop_back() call. Instead, maintain a local variable and loop over the list and free the nodes directly. Then, unconditional set head & tail to NULL. Eg:

void clear(List list) {
 pnode curr = list->head;
 while (curr) {
 pnode temp = curr;
 curr = curr->next;
 free(temp);
 }
 list->head = NULL;
 list->tail = NULL;
}