5
\$\begingroup\$

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);
}
\$\endgroup\$
2
  • 1
    \$\begingroup\$ This is actually pretty clean and concise. You can probably get away with something more concise which somehow merges the two structs into one, but most likely at the expense of readability, which I wouldn't recommend doing. \$\endgroup\$
    – wyas
    Feb 24 '15 at 19:24
  • 1
    \$\begingroup\$ This if(...) { ...; ...; } else ...; where the else is not a block isn't a particularly clear style to read. If the if has a block, the else should have a block too. The one in push_front is especially sneaky because the else has a statement immediately following it. \$\endgroup\$
    – Radiodef
    Feb 25 '15 at 5:51
11
\$\begingroup\$

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

\$\endgroup\$
3
  • \$\begingroup\$ I agree with all of your cases except the empty list. Couldn't you pass NULL as the node and it would technically be empty? \$\endgroup\$
    – Nick
    Feb 24 '15 at 21:28
  • \$\begingroup\$ Indeed you can. I will edit the answer. \$\endgroup\$ Feb 24 '15 at 21:35
  • 2
    \$\begingroup\$ I also agree with your critique, except for the style point. C prgrmrs hv a blf tht rmving ltrs frm wrds is smhow bttr bt it rly is nt. Keystrokes are cheap; don't be shy about using them. previous is perfectly clear. \$\endgroup\$ Feb 24 '15 at 22:42
4
\$\begingroup\$

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);
\$\endgroup\$
1
  • \$\begingroup\$ This is actually pretty informative. I appreciate the name collision advice. \$\endgroup\$
    – Nick
    Feb 25 '15 at 23:30
2
\$\begingroup\$

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.

\$\endgroup\$
2
\$\begingroup\$

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.

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.