# Implementation of a singly linked list in C

A [list](https://pvs-studio.com/en/blog/terms/6681/) 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](https://godbolt.org/z/ooPfd8ja7) 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:

```cpp
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:

```cpp
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:

```cpp
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\)\.

```cpp
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\.

```cpp
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\.

```cpp
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:

```cpp
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:

```cpp
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:

```cpp
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:

```cpp
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:

```cpp
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:

```cpp
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](https://godbolt.org/z/6Mfx3ejKv):

<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](https://pvs-studio.com/en/blog/posts/cpp/0938/)"\.

## Conclusion

In this article, we have discussed how to implement a singly linked list in C\. With [Compiler Explorer](https://godbolt.org/) and [PVS\-Studio](https://pvs-studio.com/en/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](https://pvs-studio.com/en/blog/posts/cpp/0959/)\.

## Additional links

* [List](https://pvs-studio.com/en/blog/terms/6681/)
* [Implementation of a doubly linked list in C](https://pvs-studio.com/en/blog/terms/6682/)
* [Implementation of a doubly linked list in C\+\+](https://pvs-studio.com/en/blog/terms/6683/)
* [Implementation of a singly linked list in C\+\+](https://pvs-studio.com/en/blog/terms/6684/)