Sparse linked list insert function

Question

I wrote this sparse linked list insert function, and there are nine return statements. Is this a code smell? Is this badly implemented? I fear that it's hard to read, or hard to maintain.

/* NOT BUGS, TESTED AND WORKS CORRECTLY
 * insert an element into a list
 * list is ordered using pos
 * if position pos is already occupied, the value of the node
 * should be updated with val
 * if val=0, then the element should be deleted
 * return 0 if operation is succesfull
 *        1 if malloc failed */
int insert_element(ElementNode_handle *list_handle, int pos, int data)
{
  /*Record the head*/
  ElementNode *current = *list_handle;

  /* If data is 0, stop */
  if (data == 0)
  {
    return 1;
  }

  /* If list is empty, crate new list*/
  if (current == NULL)
  {
    /* Create new list */
    ElementNode *new_node = make_node(pos, data);
    /* Malloc fail check*/
    if (new_node == NULL)
    {
      return 0;
    }
    new_node->data = data;
    new_node->pos = pos;
    *list_handle = new_node;
    return 1;
  }
  /* If head pos == pos, replace and done*/
  if (current->pos == pos)
  {
    current->data = data;
    return 1;
  }
  else if (current->pos > pos)
  {
    /* Create new node between current and next */
    ElementNode *new_node = make_node(pos, data);
    if (new_node == NULL)
    {
      return 0;
    }
    new_node->next = current;
    *list_handle = new_node;
    return 1;
  }
  /*Walk the list, until next hits the end*/
  while (current->next != NULL)
  {
    if (current->next->pos == pos)
    { /* If next pos equals post, replace, done*/
      current->next->data = data;
      return 1;
    }
    else if (current->next->pos > pos)
    {
      /* Create new node between current and next */
      ElementNode *new_node = make_node(pos, data);
      if (new_node == NULL)
      {
        return 0;
      }
      ElementNode *next     = current->next;
      current->next         = new_node;
      new_node->next        = next;
      return 1;
    }
    /*walk the list*/
    current = current->next;
  }
  /* Append to the tail */
  ElementNode *new_node = make_node(pos, data);
  if (new_node == NULL)
  {
    return 0;
  }
  current->next = new_node;
  return 1;
}

=== EDIT === Refactored based on @user1118321

/**
 * @brief insert an element into a list
 * @details
 * list is ordered using pos if position
 * pos is already occupied, the value of
 * the node should be updated with data
 * @param p_list_handle Opaque pointer to list
 * @param pos Position to insert
 * @param data data at position
 * @return 0 = success, 1 = failed
 */
int insert_element(ElementNode_handle *p_list_handle, int pos, int data)
{
  /*Record the head*/
  ElementNode *current = *p_list_handle;
  /*Record previous*/
  ElementNode *previous = NULL;
  /*End result*/
  int result = -1;

  if (data == 0)
  {
    delete_element(p_list_handle, pos);
    return 0;
  }

  if (current == NULL)
  {
    return make_list(p_list_handle, pos, data);
  }

  while ((current != NULL) && (result == -1))
  {
    if (current->pos == pos)
    {
      current->data = data;
      result = 0;
    }
    else if (current->pos > pos)
    {
      ElementNode *new_node = make_node(pos, data);
      if (new_node == NULL)
      {
        result = 1;
      }
      if (previous == NULL)
      {
        *p_list_handle = new_node;
      }
      else
      {
        previous->next = new_node;
      }
      new_node->next = current;
      result = 0;
    }
    previous = current;
    current = current->next;
  }
  if (result == -1)
  {
    ElementNode *new_node = make_node(pos, data);
    if (new_node == NULL)
    {
      result = 0;
    }
    previous->next = new_node;
  }
  return result;
}

Answer 1

This is a good question. Code smells tend to be subtle, and I think you're right to ask about this code. In my opinion, yes, it's a code smell. There's a general rule that programmers are taught to only have a single return statement in their functions in order to reduce the amount of spaghetti code we write. It's a good rule of thumb, but it can be taken too far. It often makes sense to have an early return when the inputs are invalid, or there's no action to take. That can actually make the code clearer.

That said, I think your code has a little of both. It has a few reasonable early returns and a several unnecessary ones. I also think the code could be restructured to make it shorter without reducing its readability. (And actually, your code's readability is pretty good.) Here are my suggestions:

Comments Are Out of Date

It looks like the comment at the top of the function doesn't match the implementation. It mentions a parameter named val, but there's no val in the code. I assume it means data. And if that is correct, then the comment is still wrong in that it says that when val (data) is 0, the node at pos should be deleted, but it isn't. You just return 1 at that point. So at least make the comments match the code.

Early Returns

As mentioned above, I think early returns are fine. If a value of 0 for data means do nothing, then the first return is fine. The next 2 are OK, but could be improved. I would do that by making a function for creating a new list. (Another good rule of thumb is to only do allocations in a single function and have all other functions that need to allocate memory call that function.) I would make a function like this:

int create_list(Elementnode_Handle *list_handle, const int pos, const int data)
{
    /* Create new list */
    ElementNode *new_node = make_node(pos, data);
    
    /* Malloc fail check*/
    if (new_node == NULL)
    {
      return 0;
    }
    
    new_node->data = data;
    new_node->pos = pos;
    *list_handle = new_node;
    
    return 1;
}

Then, I would make your second check look like this:

if (current == NULL)
{
    return create_list(list_handle, pos, data);
}

That improves the readability a lot, and reduces those 2 early returns into 1.

Don't Repeat Yourself

The next thing the code does is checks the head node of the list to see if either pos matches the first node, or is at an earlier position than the first node. Then it goes into a loop and checks the exact same condition for every other node in the list (at least until it finds the right spot). You can rearrange your loop so that you don't need the extra copy for the first node. I'd do it something like this:

ElementNode *nextNode = current;
ElementNode *prevNode = NULL;
while (nextNode != NULL)
{
    if (nextNode->pos == pos)
    {
        nextNode->data = data;
        return 1;
    }
    else if (nextNode->pos > pos)
    {
          /* Create new node between current and next */
          ElementNode *new_node = make_node(pos, data);
          if (new_node == NULL)
          {
            return 0;
          }
          
          if (prevNode == NULL)
          {
              *list_handle = new_node;
          }
          else
          {
              prevNode->next = new_node;
          }
          new_node->next = nextNode;
          return 1;
    }
    prevNode = nextNode;
    nextNode = nextNode->next;
}

Note: I haven't actually run the above code, so double-check it to make sure I didn't mess up the insertion. But the point remains that you can eliminate the first copy of those checks.

You could further reduce the number of early returns by doing something like the following before the loop:

int result = -1;
while ((nextNode != NULL) && (result == -1))
{
    // ... loop from above, but set result to 0 or 1 
    // instead of returning 0 or 1
}

// If we didn't find the node in the list, append it to the end
if (result == -1)
{
    ElementNode *new_node = make_node(pos, data);
    if (new_node == NULL)
    {
        return 0;
    }
    prevNode->next = new_node;
}

return result;

That will eliminate 3 other early returns.

Make Unchanging Arguments const

One last thing. Since you never change the value of pos or data in your function, you should mark them as const. That tells both the compiler and the reader that the function does not modify them either locally or alter their values upon return of the function. That can make it easier to understand a function's purpose at a glance.

Answer 2

Do what you say

 * return 0 if operation is succesfull
 *        1 if malloc failed */

So if a malloc fails, you are supposed to return 1. But when you do the actual check:

    ElementNode *new_node = make_node(pos, data);
    /* Malloc fail check*/
    if (new_node == NULL)
    {
      return 0;
    }

You return 0.

You return 1 on success -- the exact opposite of the comment. You should either update the comment to match the code or change the code to match the comment. Or remove the comment--if you have to read the code anyway, why bother?

Keep it simple

      ElementNode *next     = current->next;
      current->next         = new_node;
      new_node->next        = next;

Why do you need next? Consider

      new_node->next = current->next;
      current->next = new_node;

You save an assignment and a variable declaration by just changing the order in which two lines happen.

Answer 3

@user1118321 provided an excellent review. One small point: loops usually implement important algorithms, and deserve their own name. In this case I recommend to factor out finding a predecessor. Consider:

    ElementNode * predecessor = find_predecessor(list_handle, pos);

    if (predecessor && predecessor->pos == pos) {
        predecessor->value = value;
        return 1;
    }

    ElementNode * new_node = make_node(pos, value);
    if (new_node == 0) {
        return 0;
    }

    if (predecessor) {
        new_node->next = predecessor->next;
        predecessor->next = new_node;
    } else {
        new_node->next = listHandle;
        *listHandle = new_node;
    }
    return 1;

Answer 4

When dealing with linked lists, there is a trick to avoid the following code of yours:

if (prevNode == NULL)
{
    *list_handle = new_node;
}
else
{
    prevNode->next = new_node;
}

It is described in http://cslibrary.stanford.edu/105/LinkedListProblems.pdf:

Many list functions need to change the caller's head pointer. To do this in the C language, pass a pointer to the head pointer. Such a pointer to a pointer is sometimes called a "reference pointer".

The above code then becomes:

ElementNode **ref_node = &head;
…
*ref_node = new_node;