Jun 21 2023

Implementation of a singly linked list in C

Jun 21 2023

Structure of a list
Functions of a list
Potential errors and how to avoid them
- Infinite loop
- No NULL pointer check after allocating memory
Conclusion
Additional links

A list is a linear collection of data that allows you to efficiently insert and delete elements from any point in the list. There are singly linked and doubly linked lists. If you'd like to learn more about theoretical basis for lists, main methods for handling them, as well as advantages and disadvantages of lists, take a look at this article [theory]. Here, however, we are going to implement a singly linked list in C. Click the link to see the full version of the code.

Structure of a list

A singly linked list consists of nodes. Each node contains data and a pointer to the next node:

typedef struct node_t
{
  struct node_t *next;
  int data;
} node_t;

A list is a combination of pointers to the first and to the last node:

typedef struct single_linked_list_t
{
  node_t *head;
  node_t *tail;
} single_linked_list_t;

Functions of a list

Initialization

We can use the add_item_to_end function for initialization. This function inserts an element at the end of the list. We need to pass a pointer to the list, the number of elements and the elements themselves into the initializing function:

int initialize_list(single_linked_list_t *list, int count, ...)
{
  list->head = list->tail = NULL;

  va_list number;
  va_start(number, count);
  for (int i = 0; i < count; ++i)
  {
    add_item_to_end(list, va_arg(number, int));
  }

  va_end(number);

  return 0;
}

Insertion at the beginning of a list

Let's create a new node to insert an element at the beginning of the list. The next to it is the node that was the first before the insertion. We also need to update the pointer to the first node. To do this, let's pass the list pointer to the add_item_to_begin function. Don't forget to update the last pointer if it was null before the insertion (if it was inserted into an empty list).

int add_item_to_begin(single_linked_list_t *list, int item)
{
  if (list == NULL) return -1;

  node_t *newNode = (node_t*) malloc(sizeof(node_t));
  if (newNode == NULL) return -2;

  newNode->data = item;
  newNode->next = list->head;

  list->head = newNode;
  if (list->tail == NULL)
  {
    list->tail = newNode;
  }

  return 0;
}

Insertion at the end of a list

If the list is empty, the insertion at the end is the same as the insertion at the beginning of the list. We just call the add_item_to_begin function that we implemented earlier.

Let's use the last pointer that has already been saved. This will allow us not to search for the last node of the list. The last thing to do is to create a new pointer and insert it after the last node.

int add_item_to_end(single_linked_list_t *list, int item)
{
  if (list == NULL) return -1;

  if (list->tail == NULL)
  {
    return add_item_to_begin(list, item);
  }

  node_t *newNode = (node_t *) malloc(sizeof(node_t));
  if (newNode == NULL) return -2;
  newNode->data = item;
  newNode->next = NULL;

  list->tail->next = newNode;
  list->tail = newNode;
  return 0;
}

Inserting elements at a random position of the list

If you want to insert elements at random positions of the list, use the add_item_after function. This function takes a pointer to the list, a pointer to the node after which an element will be inserted, and the element itself as its arguments.

int add_item_after(single_linked_list_t *list, node_t *pos, int item)
{
  if (list == NULL) return -1;
  if (pos == NULL) return add_item_to_end(list, item);

  node_t *newNode = (node_t *) malloc(sizeof(node_t));
  if (newNode == NULL) return -2;
  
  newNode->data = item;
  
  newNode->next = pos->next;
  pos->next = newNode;

  return 0;
}

Traversal

For the list traversal example, let's use the print_list function, which prints a list of space-separated elements:

void print_list(single_linked_list_t list)
{
  node_t *current = list.head;

  fputs("[ ", stdout);

  while (current)
  {
    printf("%d ", current->data);
    current = current->next;
  }

  fputs("]\n", stdout);
  fflush(stdout);
}

Search

To find an element, let's traverse the list until we find the needed data or until we reach the last node:

node_t* find_item(single_linked_list_t list, int item)
{
  node_t *current = list.head;

  while (current)
  {
    if (current->data == item)
    {
      return current;
    }
    current = current->next;
  }

  return NULL;
}

Deletion

To delete elements, we can use the delete_item_after function. To delete a node, let's update the next pointer of the previous node:

int delete_item_after(single_linked_list_t *list, node_t *node)
{
  if (list == NULL || list->head == NULL) return -1;
  if (node == NULL)
  {
    list->head = list->head->next;
    free(list->head);
    return 0;
  };

  if (node->next == NULL) return -3;
  node_t* nodeToDelete = node->next;
  node->next = node->next->next;

  free(nodeToDelete);
  return 0;
}

There is one peculiar thing — the deletion of the first node. It has no previous pointer, so pay close attention to this case.

We can delete the entire list with the help of the delete_list function. Let's iterate over the list, starting with its head, until we reach the null pointer:

int delete_list(forward_list_t list)
{
  if (list.head == NULL || list.tail == NULL) return -1;

  node_t *current = list.head;
  node_t *next;

  while (current)
  {
    next = current->next;
    free(current);
    current = next;
  }

  return 0;
}

Potential errors and how to avoid them

We research issues on Stack Overflow for the most common errors users face with when trying to implement lists. Let's look at some typical errors.

Infinite loop

Here is an example of such an error:

node_t* find_item(single_linked_list_t list, int item)
{
  node_t *current = list.head;

  while (current)
  {
    if (current->data == item)
    {
      return current;
    }
  }

  return NULL;
}

In this fragment, a programmer forgot to traverse to the next node of the list:

current = current->next;

This is a fairly common case when developers forget to traverse to the next item of the list. You can find such errors by carefully reviewing the code. However, you can also use the PVS-Studio analyzer, integrated into Compiler Explorer. It easily detects such errors and other types of errors as well. Here's what PVS-Studio issues for this code fragment:

<source>:125:1: warning: V1044 Loop break conditions do not depend on the number of iterations.

125 is the number of the line where the error has been found.

Indeed, the while loop condition will be true regardless of the number of iterations, resulting in an infinite loop.

No NULL pointer check after allocating memory

Programmers often don't check the pointer that the malloc function returns. The function can return NULL if not enough memory is allocated. This doesn't happen in small simple programs, so it seems that the code is written correctly. However, when developing large software solutions, you can't neglect those checks. More on this topic you can find here: "Four reasons to check what the malloc function returned".

Conclusion

In this article, we have discussed how to implement a singly linked list in C. With Compiler Explorer and PVS-Studio, you can learn programming and write lab reports.

Compiler Explorer makes it possible to experiment with code right in your web browser. PVS-Studio, integrated into Compiler Explorer, will help you quickly find various errors in code. Check out the article: "Why doesn't my code work?" — to anyone learning the art of programming and writing to the Stack Overflow community.