C single-linked list with remove

Question

Can you please point out any problems with this C forward list with remove node functionality?

I believe this can be way simpler ( removeNode function ) but I somehow cannot grasp it

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

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

node* newNode(int val)
{
  node* n = (node*)malloc(sizeof(node));
  n->val = val;
  n->next = NULL;
  return n;
}

void printList(node* head)
{
  if (head == NULL) return;

  do
  {
    printf("%d, ", head->val);
    head = head->next;
  } while (head->next);

  printf("\n");
}

void clean(node* head)
{
  while (head)
  {
    node* curr = head;
    if (head->next == NULL)
    {
      free(head);
      return;
    }

    head = head->next;
    free(curr);
  }
}

void insert(node* head, int val)
{
  while (head)
  {
    if (head->next)
    {
      head = head->next;
    }
    else
    {
      head->next = newNode(val);
      return;
    }
  }
}

void removeIf(node** head, int val)
{
  if (head == NULL) return;
  if (*head == NULL)
  {
    head = NULL;
    return;
  }

  while (*head && (*head)->val == val)
  {
    if ((*head)->next == NULL)
    {
      free(*head);
      *head = NULL;
      return;
    }
    node* tofree = *head;
    *head = (*head)->next;
    free(tofree);
  }

  node* curr = (*head)->next;
  node* prev = *head;

  while (curr)
  {
    if (curr->next == NULL) return;

    if (curr->val == val)
    {
      prev->next = curr->next;
      node* tofree = curr;
      curr = curr->next;
      free(tofree);
    }
    else
    {
      prev = prev->next;
      curr = curr->next;
    }
  }
}

int size(node* root)
{
  if (root == NULL) return 0;
  int sz = 1;
  while (root->next)
  {
    root = root->next;
    ++sz;
  }

  return sz;
}

void tests();

int main()
{
  tests();
}

/*
 * Here are the tests for lists functionalities
 */
void tests()
{
  {
    node* root = newNode(1);
    insert(root, 2);
    assert(size(root) == 2);
    clean(root);
  }
  {
    node* root = newNode(8);
    insert(root, 2);
    insert(root, 2);
    assert(size(root) == 3);
    clean(root);
  }
  {
    node* root = newNode(8);
    insert(root, 123);
    insert(root, 123);
    insert(root, 123);
    insert(root, 123);
    assert(size(root) == 5);
    clean(root);
  }
  {
    node* root = newNode(8);
    insert(root, 123);
    assert(size(root) == 2);
    removeIf(&root, 1);
    assert(size(root) == 2);
    clean(root);
  }
  {
    node* root = newNode(1);
    insert(root, 1);
    insert(root, 1);
    insert(root, 1);
    insert(root, 2);
    insert(root, 3);
    insert(root, 3);
    insert(root, 4);
    insert(root, 4);
    insert(root, 5);
    assert(size(root) == 10);
    removeIf(&root, 1);
    assert(size(root) == 6);
    clean(root);
  }
  {
    node* root = newNode(1);
    insert(root, 1);
    insert(root, 1);
    insert(root, 1);
    insert(root, 2);
    insert(root, 3);
    insert(root, 3);
    insert(root, 4);
    insert(root, 4);
    insert(root, 5);
    assert(size(root) == 10);
    removeIf(&root, 3);
    assert(size(root) == 8);
    clean(root);
  }
  {
    node* root = newNode(1);
    insert(root, 1);
    assert(size(root) == 2);
    removeIf(&root, 1);
    assert(size(root) == 0);
    clean(root);
  }
  {
    node* root = newNode(1);
    insert(root, 1);
    insert(root, 1);
    insert(root, 1);
    assert(size(root) == 4);
    removeIf(&root, 1);
    assert(size(root) == 0);
    clean(root);
  }
}

Answer 1

No need to peek ahead for the loop condition. Especially not AFTER incrementing it already. Coincidence that this function was not part of the test suite?

void printList(node* head)
{
  if (head == NULL) return;

  while(head)
  {
    printf("%d, ", head->val);
    head = head->next;
  };

  printf("\n");
}

---

Too much redundant code:

void clean(node* head)
{
  while (head)
  {
    node* curr = head;
    head = head->next;
    free(curr);
  }
}

---

In void insert(node* head, int val), no need to branch inside the loop. Do it step by step. First find the tail, then append.

---

void removeIf(node** head, int val) would become already much simpler if it did just add a temporary head to the list, as the special handling for removing a chain at the head wouldn't be necessary in that case. Finally destroy the temporary head again, and overwrite head unconditionally.

---

In int size(node* root), why call it root all of a sudden and no longer head?

Also, unnecessary lookahead and branching again:

int size(node* head)
{
  int sz = 0;
  while (head)
  {
    ++sz;
    head = head->next;
  }
  return sz;
}

---

In terms of code style only one remark, and that is on the location of the * when working with pointer types.

I know, placing it next to the type feels more natural, but it's semantically inaccurate, and it will trip you the first time you attempt to declare multiple variables at once. Placing it where there compiler would sort it helps preventing these mistakes.

Answer 2

Here's a simple remove implementation. When deleting node foo, you need to

1. free foo

2. make whatever was pointing to foo (either the node** head passed as a parameter to the function, or the next pointer of the previous node) point to foo.next

This becomes much easier if you realize that those two cases are identical, all you are doing is freeing something and changing what a pointer points to. To change what a pointer points to, you can simply keep a pointer to the pointer that needs changing.

The pointer to pointer starts off as the input node **head and becomes a pointer to the next pointer of the previous node while iterating down the list. That way when you find the element you just save its next pointer, free the element, and use your pointer to pointer to update the previous element OR node **head to point to the new next.

void removeIf(node **head, int val) {
  node **curr = head;
  while (*curr != NULL) {
    if ((*curr)->val == val) {
      node *next = (*curr)->next;
      free(*curr);
      *curr = next;
    } else {
      curr = &((*curr)->next);
    }
  }
}

Answer 3

Cleaner printList() results

This is a very minor nitpick, but as your printList() function is currently written, you will always have a trailing comma and space characters at the end of the list (i.e., 1, 2, 3, 5, 8,). If you slightly reorganize the logic as such (note the ", %d" string in the loop printf()):

void printList(node* head) {
   if (head == NULL) return;
   printf("%d", head->val);
   while (head = head->next) {
      printf(", %d", head->val);
   }
   printf("\n");
}

Your printed results won't have the trailing comma + space.

Rename insert() to append()

Simple. As written, your insert() method actually appends to the end of the list. Rename it to append() so its name reflects its function.

Do you need to insert an element into the middle of the list? If so, insert() would be and excellent name for that function.

Cleaner struct {} and typedef struct ... usage

Again, this is very minor, but the following struct node and typedef are valid, and a bit cleaner:

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

Consider creating a List container structure

You have the beginnings of a good linked list library. However, it suffers from a key performance issue: the amount of time it takes to add a node to the end of the list (and the amount of time it takes to report the list size() as well) is directly proportional to the number of elements in the list. In other words, append() and size() are O(n), which quickly gets to be unacceptable from a performance standpoint.

If you define a structure that contains some metadata about the list, as well as the root pointer to the list nodes, you can keep track of the number of elements and the end of the list:

struct List {
   node *head;
   node *tail;
   size_t length;
};

Then adjust your creation, insertion, deletion functions to keep list->length and list->tail up-to-date. Then calls to size() and append() just reference the length and tail members directly, so those functions execute in O(1) time.