C Doubly Linked List

Question

It works, but it seems a bit long winded. I'd like some critiquing.

#include <stdio.h>
#include <stdlib.h>

struct node
{
  int data;
  struct node * previous;
  struct node * next;
};

struct linked_list
{
  struct node * first;
  struct node * last;
};

struct linked_list * init_list(struct node * node)
{
  struct linked_list * ret = malloc(sizeof(struct linked_list));
  ret->first = node;
  ret->last = node;
  return ret;
}

struct node * create_node(int data)
{
  struct node * ret = malloc(sizeof(struct node));
  ret->data = data;
  ret->previous = NULL;
  ret->next = NULL;
  return ret;
}

void destroy_list(struct linked_list * list)
{
  struct node * node = list->first, *next = NULL;
  while(node != NULL)
  {
    next = node->next;
    free(node);
    node = next;
  }
  free(list);
}

void push_front(struct linked_list * list, struct node * node)
{
  if(list->first != NULL)
  {
    node->next = list->first;
    list->first->previous = node;
  }
  else list->last = node;
  list->first = node;
}

void push_back(struct linked_list * list, struct node * node)
{
  if(list->last != NULL)
  {
    node->previous = list->last;
    list->last->next = node;
    list->last = node;
  }
  else push_front(list, node);
}

void insert_after(struct node * node, struct node * to_add)
{
  to_add->previous = node;
  to_add->next = node->next;
  node->next = to_add;
}

void remove_node(struct node * node)
{
  node->previous->next = node->next;
  node->next->previous = node->previous;
  free(node);
}

Answer 1

As mentioned in the comments this code is not long winded at all. It is very clean in general. Too clean in fact as you will see below.

• You cannot create an empty linked list with your init_list. However, in other parts of your code you assume list may be empty. It is useful to be able to create an empty linked list since you may not know what you want your first node to be in advance. I'd suggest changing init_list.

• I personally like symmetry in linked list code. You can always create the dual of one function by swapping all prevs with nexts and all heads with tails. I don't think your push_back code should call push_front. You can handle the else condition just like you did in push_front except by swapping variable names.

• insert_after is incomplete. Remember this is a doubly linked list. Also the function doesn't handle the case when you insert after the current list->last. You need to add the linked list to the function arguments.

• remove_node does not handle all cases. What if node was the head of the list? What if it was the tail of the list? What if it was both the head and the tail? You don't actually have to write three different cases to handle this but you can.

• As simply a style choice I would rename previous to prev

• I am ignoring that you never check for your pointers being NULL

Edit:

This code actually can produce an empty list by passing NULL in as an argument to init_list

Answer 2

You've done a good job of breaking your list manipulating into small, logic functions typical of a doubly linked list. I do think you need to take it a step farther though: the manipulation (allocation, setting, etc) of node is an implementation detail. What you're really wanting to operate on are ints, and node should just be used to traverse the list (if you wanted to go all out you could even encapsulate the traversal so node is completely hidden, but meh... I think that's taking it a bit too far since doubly linked lists are so simple).

---

You seem to have forgotten insert_before. I would expect it to be there since insert_after is there and this is a doubly linked list.

---

Though it's not worth worrying about it unless you're working on non-trivial C programs or developing a library others will use, you should be mindful of potential name collisions and use a prefix.

For example, if you remove the requirement that the list be initialized with an element, you'll end up with init_list(void) as a signature which is fairly likely to exist in some other library. This is the reason that libraries all use some kind of prefix (curl_, apr_, ev_, etc).

Though it's not important as long as you're aware of the possibility and willing to run that risk, it becomes incredibly important in anything that's a non-trivial program or even a trivial program with dependencies. In addition, if you are to ever publish code for someone else to use, you can't predict what kind of collisions they might have. In short, if this code were to be 'real' code, it would need to have some kind of (ideally unique) prefix on method/type names.

---

enum linked_list_result { LINKED_LIST_SUCCESS = 0, LINKED_LIST_ERR_MEM = 1 };

struct linked_list * init_list(void);

void destroy_list(struct linked_list * list);

/* Your functions now return a result type instead of void since the malloc could fail */
enum linked_list_result push_front(struct linked_list * list, int value);

enum linked_list_result push_back(struct linked_list * list, int value);

enum linked_list_result insert_before(struct node * node, int value);

enum linked_list_result insert_after(struct node * node, int value);

void remove_node(struct node * node);

/* This becomes hidden in the implementation file */
static struct node * create_node(int data);

Answer 3

In addition to the bugs that twohundredping already pointed out, I want to further point out that the insert_after and remove_node functions are flawed in concept because they don't pass the list to the function. Therefore, you can wind up with a list that has incorrect first and last pointers if you use those functions.

I think both those functions should take a list argument and should update list->first and list->last as appropriate.

Answer 4

A good practice is to always either check the return value of any malloc and return NULL as to not crash. Or at least do an assert(ret != NULL);.

Also assert for what should be considered errors by incorrectly using the API. For example passing a NULL node to the remove_node or insert_after functions.