Moving an element in a linked list

Question

Given I have a linked list, and I want to move a given node to the end of the list, is there a more elegant way of doing this, than what I've done here?

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

typedef struct node {
  int val;
  struct node *next;
} node_t;

void insert(node_t **head, int val)
{
  node_t *new_node = malloc(sizeof(node_t));
  node_t *tmp;

  new_node->val = val;
  new_node->next = NULL;

  // Empty list?
  if(*head == NULL) {
    *head = new_node;
    return;
  }

  tmp = *head;

  while(tmp->next != NULL)
    tmp = tmp->next;

  tmp->next = new_node;
}

void movetoend(node_t **head, int val)
{
  node_t *curr;
  node_t *tmp = NULL;
  node_t *old = NULL;

  // Find val in list
  for(curr = *head; curr != NULL; old = curr, curr = curr->next) {
    if(curr->val == val) {
      // Matched node is the only one in the list, don't do anything
      if(curr->next == NULL)
        return;

      // Matched node is first, set next to jump over
      if(old == NULL)
        *head = curr->next;

      // Matched node is in the middle, set next to jump over
      else
        old->next = curr->next;

      // Set a pointer to matched node for later use
      tmp = curr;

      // Loop through the rest of the list
      // "old" will have the pointer to last node
    }
  }

  // No matches?
  if(tmp == NULL)
    return;

  // Terminate list
  tmp->next = NULL;

  // Append matched node
  old->next = tmp;
}

void print(node_t *head)
{
  while(head) {
    printf("%d\n", head->val);
    head = head->next;
  }
}

int main()
{
  node_t *head = NULL;

  insert(&head, 10);
  insert(&head, 20);
  insert(&head, 30);
  movetoend(&head, 10);
  print(head);

  return 0;
}

EDIT: Added comments, modified movetoend function a bit slimmer.

Answer 1

There's more elegant ways, although not necessarily more efficient. The common idiom for fiddling with this kind of linked list in C is to add one more layer of indirection and fiddle with pointers-to-node-pointers, like this:

void insert(node_t **head, int val)
{
    node_t *new_node = malloc(sizeof(node_t));
    new_node->val = val;
    new_node->next = NULL;

    node_t **ptmp = head;
    while (*ptmp != NULL) {
        ptmp = &(*ptmp)->next;
    }
    *ptmp = new_node;
}

Given that example, I think you can figure out how to rewrite movetoend in just a few additional lines: much shorter than the page of code you have now.

However, whether this will be equally fast depends on your compiler and optimization levels. When in doubt, check the assembly code! If you see a lot of additional memory loads in the inner loop, that's a bad sign.

In C++, but I think not in C yet, you could eliminate even the appearance of extra memory loads by doing

void insert(node_t **head, int val)
{
    node_t *new_node = malloc(sizeof(node_t));
    new_node->val = val;
    new_node->next = NULL;

    node_t **ptmp = head;
    while (node_t tmp = *ptmp) {
        ptmp = &tmp->next;
    }
    *ptmp = new_node;
}

Answer 2

  for(curr = *head; curr != NULL; old = curr, curr = curr->next) {
    if(curr->val == val) {

I'd consider

  // iterate until we find val or run out of nodes
  for (curr = *head; curr != NULL && curr->val != val; old = curr, curr = curr->next) ;

  if (current == NULL) {
      // no matches -- nothing to move
      return;
  }

  if (current->next == NULL) {
      // already at end of list -- no need to move
      return;
  }

  // remove current from list
  if (old == NULL) {
      // current at the beginning of the list
      *head = current->next;
  } else {
      old->next = current->next;
  }

  current->next = NULL;

  for (old = old->next; old->next != NULL; old = old->next) ;

  old->next = current;

Now we don't need tmp.

Also, we don't iterate over curr when we just want to change old.

I prefer the block form of control structures. I find it easier to read, and it is more robust in the face of future changes.

But I used the statement form for the two empty for loops.

I prefer to write out current.

Answer 3

A more elegant way of doing this. Make insert() more efficient.

Rather than use a NULL terminated linked list, have the tail point to the first element (head). Also have the pointer to the linked list point to the last element - so it becomes the tail pointer. Net effect, a circular linked list.

Consider insert(). 1) Allocate to the size of the referenced data,not the type. This is easier to code right, maintain and review. 2) Test the allocation. 3) Notice insert() now has no loop! It is now O(1) rather than O(n).

int insert(node_t **tail, int val) {
  node_t *new_node = malloc(sizeof *new_node);
  if (new_node == NULL) return FAIL; 
  new_node->val = val;

  if(*tail) {
    new_node->next = (*tail)->next;
    (*tail)->next = new_node;
  } else {
    new_node->next = new_node;
  }
  *tail = new_node;
  return SUCCESS;
}

void movetoend() needs a similar re-write to employ this new approach. It will remain O(n). Further, it should return a value indicating SUCCESS (found) or FAIL (not found).

void movetoend() could be coded calling 2 helper functions: int append(node_t **tail, int val) and int remove(node_t **tail, int val). int append(node_t **tail, int val) is very similar to insert() and also O(1).

print(node_t *head) re-write.

void print(const node_t *tail) {
  if (tail) {
    const node_t *ll = tail->next;
    while (printf("%d\n", ll->val), ll != tail) {
      ll = ll->next;
    }
  }
}