Doubly linked-list implementation

Question

I come from a C++ background, and I recently got into C, and one of the first things I made was a double linked list since I though it would be good practice for me with pointers and memory allocation. It isn't too complex though, it's just with some basic functions.

Here's the overview of my list:

#include <stdlib.h>
#include <stdio.h>
typedef struct Node
{
 int val;
 struct Node* prev;
 struct Node* next;
} Node;
typedef struct
{
 int length;
 Node* head;
 Node* tail;
} double_list;
double_list* create_list(); // constructor
void destroy_list(double_list* const list); // destructor
void insert_pos(double_list* const list, int index, int val);
void insert_front(double_list* const list, int val);
void insert_back(double_list* const list, int val);
void remove_pos(double_list* const list, int index);
void remove_front(double_list* const list);
void remove_back(double_list* const list);
void sort_list(double_list* const list); // selection sort
void reverse_list(double_list* const list);

It just has basic insertion and removal, as well as a constructor, destructor, sort, and reverse functions.

Here's the actual definition for the functions:

#include <stdlib.h>
#include <stdio.h>
typedef struct Node
{
 int val;
 struct Node* prev;
 struct Node* next;
} Node;
typedef struct
{
 int length;
 Node* head;
 Node* tail;
} double_list;
double_list* create_list()
{
 double_list* list = malloc(sizeof(*list));
 list->length = 0;
 list->head = NULL;
 list->tail = NULL;
 return list;
}
void destroy_list(double_list* const list)
{
 list->length = 0;
 Node* node_ptr = list->head;
 while (node_ptr != NULL)
 {
 node_ptr = node_ptr->next;
 free(list->head);
 list->head = node_ptr;
 }
}
void insert_pos(double_list* const list, int index, int val)
{
 if (index < 0 || index > list->length)
 return;
 list->length += 1;
 if (list->head == NULL)
 {
 list->head = malloc(sizeof(*(list->head)));
 list->head->val = val;
 list->head->prev = NULL;
 list->head->next = NULL;
 list->tail = list->head;
 return;
 }
 if (index == 0)
 {
 Node* new_node = malloc(sizeof(*new_node));
 new_node->val = val;
 new_node->prev = NULL;
 new_node->next = list->head;
 list->head->prev = new_node;
 list->head = new_node;
 return;
 }
 if (index == list->length - 1)
 {
 Node* new_node = malloc(sizeof(*new_node));
 new_node->val = val;
 new_node->prev = list->tail;
 new_node->next = NULL;
 list->tail->next = new_node;
 list->tail = new_node;
 return;
 }
 
 Node* node_ptr = list->head;
 for (int a = 0; a < index; ++a)
 node_ptr = node_ptr->next;
 Node* new_node = malloc(sizeof(*new_node));
 new_node->val = val;
 new_node->next = node_ptr;
 new_node->prev = node_ptr->prev;
 node_ptr->prev->next = new_node;
 node_ptr->prev = new_node;
}
void insert_front(double_list* const list, int val)
{
 insert_pos(list, 0, val);
}
void insert_back(double_list* const list, int val)
{
 insert_pos(list, list->length, val);
}
void remove_pos(double_list* const list, int index)
{
 if (index < 0 || index >= list->length)
 return;
 list->length -= 1;
 if (index == 0)
 {
 Node* node_ptr = list->head;
 list->head = list->head->next;
 list->head->prev = NULL;
 free(node_ptr);
 return;
 }
 if (index == list->length)
 {
 Node* node_ptr = list->tail;
 list->tail = list->tail->prev;
 list->tail->next = NULL;
 free(node_ptr);
 return;
 }
 
 Node* node_ptr = list->head;
 for (int a = 0; a < index; ++a)
 node_ptr = node_ptr->next;
 node_ptr->prev->next = node_ptr->next;
 node_ptr->next->prev = node_ptr->prev;
 free(node_ptr);
}
void remove_front(double_list* const list)
{
 remove_pos(list, 0);
}
void remove_back(double_list* const list)
{
 remove_pos(list, list->length - 1);
}
void sort_list(double_list* const list)
{
 Node* index_ptr = list->head;
 Node* small_ptr = list->head;
 Node* node_ptr = list->head;
 while (index_ptr->next != NULL)
 {
 while (node_ptr != NULL)
 {
 if (node_ptr->val < small_ptr->val)
 small_ptr = node_ptr;
 node_ptr = node_ptr->next;
 }
 int hold = index_ptr->val;
 index_ptr->val = small_ptr->val;
 small_ptr->val = hold;
 index_ptr = index_ptr->next;
 node_ptr = index_ptr;
 small_ptr = index_ptr;
 }
}
void reverse_list(double_list* const list)
{
 Node* node_ptr = list->head;
 list->head = list->tail;
 list->tail = node_ptr;
 while (node_ptr != NULL)
 {
 Node* temp = node_ptr->prev;
 node_ptr->prev = node_ptr->next;
 node_ptr->next = temp;
 node_ptr = node_ptr->prev;
 }
}

And here's a small sample of how my list would be used:

double_list* list = create_list();
insert_back(list, 1);
insert_back(list, 2);
insert_back(list, 3);
sort_list(list);
destroy_list(list);

My main area's of concern are:

1. Are the constructor and destructor doing their job properly? Is the destructor leaking memory, and is there a better way to do the constructor?

2. Are the remove() and insert() functions efficient? Is there a better way to do that, like making a more generic remove() function so I don't have to have special test cases for index of 0 and stuff like that?

3. Are the sort() and reverse() functions okay at least? I know selection sort isn't the best algorithm to use. And is the reverse() function implemented correctly? Is there a better way to reverse the list?

Sorry I'm being a little too broad with my question. I can edit it to focus on a more specific question if needed.

Thanks

• Craig Estey: Side note: After just a quick glance ... In insert_pos [and delete_pos] at the point where you actually traverse the list using the next pointer ... Since your list has a length, you could check for index > (list->length / 2) and if that's true, traverse [backwards] from list->tail using the prev link

Answer 1

Good question, well formatted, well worked out and implementation seems to work!

First to answer your questions:

Q1:

Constructor:

• Check return value of malloc, it could be NULL if it failed (out of memory)

Destructor:

• just pass double_list *list, the const there doesn't make sense (not sure why you put it there).
• you leak memory, because you don't free list, which you have allocated in the constructor

Edit 1:

If you pass in double_list *const list that means the value of list (the pointer) cannot be changed, which doesn't make sense here because the user of this interface holds on to the pointer.

If the const is before the type const double_list *list this means the content of where list is pointing cannot change.

For example if you have a function that takes a string and you want to communicate to the user of this function that the content of the string is not going to change, you should do void foo(const char *bar). If the function is only foo(char *bar) the user cannot be sure that the content of the string bar is still the same afterwards.

Q2:

• I don't see any issues with the remove and insert functions regarding performance. Insert in the middle is always going to be O(n). Removing/inserting at head and tail is O(1) which you achieve in your code.
• It would be a bit more intuitive if you implemented the simple case of removing head/tail in the function remove_front/remove_back and used these functions in the generic remove_pos function.

Q3:

sorting

• sort_list: what you could do is setting a flag when the list is ordered so that if it gets ordered again, it's fast (unset the flag when an element is added)
• otherwise I don't see any issues with the sorting implementation

reverse

Your list reverse implementation is O(n) but since you have a doubly linked list you could simple make use of this. You could have two sets of operations on the list, one operates in forward direction, the other one in reverse. Whenever the reverse_list is called you would swap the function set. See the example below:

struct list_operations
{
 void (*insert_front)(double_list* const list, int val);
 // more functions
};
static const struct list_operations list_operations_forward = 
{
 .insert_front = insert_front_forward,
 // more functions
};
static const struct list_operations list_operations_reverse = 
{
 .insert_front = insert_front_reverse,
 // more functions
};
void reverse_list(double_list* list)
{
 if (NULL == list)
 {
 return
 }
 list->operations = (list->operations == &list_operations_forward)?&list_operations_reverse:&list_operations_forward;
}

More general feedback:

Hide private information

You leak some of the the details in the h file. You probably don't want that a user of your double_list library can mess with the nodes, therefore you should hide it and add functions to get the value. The h file would look like follows:

typedef struct double_list_s double_list_t;
double_list* create_list();
void destroy_list(double_list* list);
void insert_pos(double_list *list, int index, int val);
void insert_front(double_list *list, int val);
void insert_back(double_list *list, int val);
void remove_pos(double_list *list, int index);
void remove_front(double_list *list);
void remove_back(double_list *list);
int get_pos(double_list *list, pos);
int get_front(double_list *list);
int get_back(double_list *list);
void sort_list(double_list *list); // selection sort
void reverse_list(double_list *list);

Remove the const

You are passing double_list* const list, what are you exactly trying to achieve with the const?

Inclusion guard missing

You should add the following:

#ifndef __DOUBLE_LIST_H__
#define __DOUBLE_LIST_H__
// snip
#endif

Remove the includes in the h file

The includes should go in the c files only. Otherwise you can run into cyclic inclusions.

the pointer star sticks to the variable

e.g. not good: char* b

better: char *b

otherwise it looks weird if you have following declaration:

char* b, *a vs (char *b, *a)

Check for NULL

Check the list argument for NULL in the functions

Check for NULL after allocating

When you allocate the nodes, you should also check if malloc returned NULL.

Testing

When you add to your list, you add the element in 1,2,3 order, so sort_list is not doing much.

Naming the functions

When it comes to naming functions it certainly comes down to personal taste but I would stick with common expressions. For example back and front are a bit uncommon, I think head and tail describe better what the functions to.

Also it makes your interface a bit cleaner if you name them consistently

list_create()
list_destroy()
list_pos_insert()
list_head_insert()
list_tail_insert()
list_pos_remove()
list_head_remove()
list_tail_remove()
list_sort()
list_reverse()

Just let me know if something is unclear, codereview "forgot" half of my text so I rushed it a bit to write it down again.

• Alex: Oh cool thanks! Just a question though, I have the const there since I though it prevent the pointer from begin reassigned? Isn't that good practice?
• Frode Akselsen: @DynamicSquid I've added a short paragraph about the const, It's certainly good to use const when possible but in your case it doesn't make sense since the user holds on to the list pointer.
• Lundin: @DynamicSquid It doesn't make sense to use type * const name on parameters because that pointer is a local copy of the original, and nobody cares if your function reassigns that local copy somewhere. It doesn't affect the original pointer on the caller side.

Answer 2

regarding:

typedef struct
{
 int length;
 Node* head;
 Node* tail;
} double_list;

Most debuggers use the 'tag' name of a struct to be able to access the individual fields. Suggest inserting a 'tag' name

the main() function is missing. Perhaps that is where you would place the calls:

double_list* list = create_list();
insert_back(list, 1);
insert_back(list, 2);
insert_back(list, 3);
sort_list(list);
destroy_list(list);

strongly suggest keeping the list sorted at 'insert()' rather than as a separate operation

• Frode Akselsen: you probably don't want to sort when adding an item. If you add at the tail you want to get the same item when you get an item from the tail. Otherwise, the list should be called sorted_double_list (and functions like insert_pos, insert_back, insert_front would be superfluous (replace by simple insert function).
• user3629249: simplicity of code is always a very desirable objective

Answer 3

I would treat Node as a class, as you did with double_list. I.e. create functions node_create(), node_destroy() etc.
Let node_...() functions modify/sanity check the Node's content.