Remove a node from a linked list in almost O(1)

struct node {
  int data;
  /* ... */
  struct node *next;
};
typedef struct node NODE;

Suppose that we have a singular list of NODE or a circular list of NODE⁠. To remove a node from the list, we'd like to implement following function:

/* Remove NPTR from the list pointed by HEAD, and return it. */
NODE *list_extract(NODE **head, NODE *nptr);

The node that we need to extract from the list is pointed by nptr⁠. So we need to make sure that the next field of the node before nptr should point the node after nptr⁠. One way to find the previous node is to iterate all nodes from head to find the node whose next field is the node pointed by nptr⁠:

NODE *before;
for (before = head; before != 0; before = before->next)
  if (before->next == nptr)
    break;

However, it may not be so efficient to traverse lots of node before nptr if the list is very very long. There is another way to extract a node from a list without iterating the list to find the previous node.

head           nptr
[10] -> ... -> A:[12] -> B:[34] -> ...

Suppose we have a list like the above. head and nptr is the pointer to the head of the node and the node that needs to be extracted respectively. Let the node points by nptr is node A, and the next node of node A is node B. Node A has an integral data, 12, and node =⁠B= has 34⁠.

Instead of finding the node before nptr⁠, we like to swap the contents of the node A and node B. To do that, I'll introduce a temporary node, T⁠, and copy the contents of node =⁠A= into it.

head           nptr
[10] -> ... -> A:[12] -> B:[34] -> ...

                           ^
                           |
               T:[12] -----+

Note that we copied every fields of node A into node T⁠, so =⁠next= field of node T also points the same node as node A points. Then, we copy all fields of node B into node A:

head           nptr
[10] -> ... -> A:[34] -------------+
                                   |
                                   V
               T:[12] -> B:[34] -> ...

Then, we copy all fields of node T into node B⁠:

head           nptr
[10] -> ... -> A:[34] -----------> ...

                            +----+
                            |    |
                            V    |
               T:[12] -> B:[12] -+

Since we copyied next field from node =⁠T= to node B⁠, node =⁠B= turns to be a circular list of its own node, which we don't intent. So set next field of node B to NULL⁠.

head           nptr
[10] -> ... -> A:[34] -----------> ...

               T:[12] -> B:[12] -|

Now the node that we wanted to extracted is copyied to node B, which is accessible by next field of node T. And the list has successfully removed the contents of node pointed by nptr⁠.

However, when the target nptr is the last node, we cannot use this trick since there is no next node. In that case, we use the well known solution, to iterate all nodes to find the previous node.

The full source code of list_extract() is here:

NODE *
list_extract(NODE **head, NODE *nptr)
{
  NODE t;
  NODE *prev;

  if (*head == nptr) {
    if (nptr->next == NULL) {
      *head = 0;
      return nptr;
    }
    else {
      *head = nptr->next;
      nptr->next = NULL;
      return nptr;
    }
  }

  if (nptr->next) {
    memcpy(&t, nptr, sizeof(t));
    memcpy(nptr, nptr->next, sizeof(t));
    memcpy(t.next, &t, sizeof(t));
    t.next->next = 0;
    return t.next;
  }

  for (prev = *head; prev != NULL; prev = prev->next) {
    if (prev->next == nptr)
      break;
  }
  if (!prev)
    return 0;

  prev->next = nptr->next;
  nptr->next = 0;

  return nptr;
}

And the time complexity will be: