Simple linked list implementation

Question

I am learning C and tried to make a basic singly linked list. I am looking for some feedback on my implementation. I have implemented deletion and reversal functions. Be hard on me as I am trying to improve.

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

//very basic linked list implimentation in C. 
//basic node structure. No typedef.
struct node
{
  int val;
  struct node *next;
};

struct node *deleteNode(struct node *first, int num)
{
  struct node *prev=NULL;
  struct node *root = first;
  while (root != NULL)
  {
    if (root->val == num)
    {
      if (prev != NULL && root->next != NULL) //middle elements
      {
        prev->next = root -> next;
        free(root);
      }
      else if (prev == NULL) //first element
      {
        free(first);
        first = root->next;
        root = root->next;
      }
      else if (root->next == NULL) //last element
      {
        prev->next = NULL;
        free(root);
      }
    }
    prev = root;
    root = root -> next;
  }
  return first;
}

struct node *reverseList(struct node *root)
{
  struct node *temp= NULL;
  struct node *prev= NULL;

  while (root!= NULL)
  {
    temp = root->next;
    root->next = prev;
    prev = root;
    root = temp;
  }
  return prev;
}

void printList(struct node *root)
{
 while (root!= NULL)
 {
   printf("Value: %d\n", root -> val);
   root = root -> next;
 }
}

int main()
{
 struct node *root = NULL, *tail = NULL;

 int i=1;
 for (;i<=20; ++i)
 {
     struct node *current = malloc(sizeof(struct node));
     current -> val = i;
     current -> next = NULL;

     if (root==NULL) root = current;
     else tail -> next = current;

     tail = current;
 }

 //delete first,last and middle element 
 root = deleteNode(root, 20);
 root = deleteNode(root, 1);
 root = deleteNode(root, 10);
 root = reverseList(root);
 printList(root);

 return 0;
}

Answer 1

I suggest using this declaration:

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

After that, you can declare node *t instead of struct node *t. Also, you'll use sizeof(node) instead of sizeof(struct node).

Your delete is buggy. I'll quote just a bit:

struct node *deleteNode(struct node *first, int num)
{
  struct node *prev=NULL;
  struct node *root = first;
  while (root != NULL)
  {
    if (root->val == num)
    {
      ...
      else if (prev == NULL) //first element
      {
        free(first);
        first = root->next;
        root = root->next;
      }
      ...
    }
    ...
  }
  return first;
}

So, you have root = first, then you free the memory of first, and then you access root->next which is the same as first->next, which is a value contained in the already freed memory.

I'd write it in two parts:

1. Delete all there is to be deleted from the list start.

2. Delete all there is to be deleted, but is not at the list start.

Like this:

node *deleteNodes(node *first, int num) {
  node *prev, *active;

  while (first && first->val == num) {
    node *tmp = first;
    first = first->next;
    free(tmp);
  }

  if (!first) return NULL;

  prev = first;
  active = first->next;

  while (active)
    if (active->val == num) {
      prev->next = active->next;
      free(active);
      active = prev->next;
    } else {
      prev = active;
      active = active->next;
    }

  return first;
}

I have changed the name of the function because you seem to want to remove all the nodes containing the value num.

A matter of personal choice: I prefer to transverse through a list the same way I do with arrays -- by using a for loop.

void printList(node *root) {
  node *t;
  for (t = root; t; t = t->next)
    printf("Value: %d\n", t->val);
}

If you really want to reuse root, you can, but one or few additional variables (like my t (stands for "temporary") in the above code) can make your code much more readable.

It may be useful to finish void functions with return;, as it helps you detect certain problems in code (i.e., if you change the return value to something else, such return will result in error and warn you to fix it).

This

node *current = malloc(sizeof(node));

can be written like this like this:

node *current = (node*)malloc(sizeof(node));

Read about using such a cast here and decide for yourself. I prefer to use it.

You should always release all your memory (i.e., delete the remaining list) when you program ends, instead of relying on the OS to do it properly.

Answer 2

you can make the list more generic by using void * val and taking a pointer to a comparison function as argument of the deleting function (check out qsort from the standard library to see how it works)

like so:

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

struct node *deleteNode(struct node * first, 
                        void * val_to_delete, 
                        int (*cmp)(const void *, const void*))

where cmp is user-defined function that takes to void pointers, casts them to the actual type used and compares them. this way you can store and delete any value (e.g. another list) as a value.

Answer 3

A few comments:

• It is generally considered best practice to define one variable per line.
• Be consistent with variable names (eg tmp and temp, root and first)

• Use const and static where possible (eg printList should have a const parameter

• Your delete_list fails if first is NULL (tries to free tmp). Define tmp inside the loop where it is first used.

---

Your deleteNodes (derived from the answer from @VedranŠego) is still too complicated and you introduce a fault by omitting the answer's check if (!first) return NULL;

And easier solution is this:

static struct node *deleteNodes (struct node *n, int num)
{
    struct node start = {.next = n};
    struct node *prev = &start;

    while (n) {
        if (n->val == num) {
            prev->next = n->next;
            free(n);
            n = prev->next;
        } else {
            prev = n;
            n = n->next;
        }
    }
    return start.next;
}