# Implementation of a doubly 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 doubly linked list in C\. [Click](https://godbolt.org/z/11ePK7f5b) to see the full version of the code\.

## Structure of a list

A doubly linked list consists of nodes\. Each node contains data, a pointer to the next node, and a pointer to the previous node:

```cpp
typedef struct node_t
{
  struct node_t *next;
  struct node_t *prev;
  int data;
} node_t;
```

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

```cpp
typedef struct double_linked_list_t
{
  node_t *head;
  node_t *tail;
} double_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(double_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 you insert elements into an empty list\. 

```cpp
int add_item_to_begin(double_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->prev = newNode->next = NULL;
  newNode->data = item;

  if (list->head)
  {
    list->head->prev = newNode;
    newNode->next = list->head;
    list->head = newNode;
  }
  else 
  {
    list->head = 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\.

If the list is non\-empty, we insert a new node after the last node \(it is indicated by _last\)\._ The last thing to do is to create a new node and insert it after the last node\.

```cpp
int add_item_to_end(double_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->prev = newNode->next = NULL;
  newNode->data = item;
  
  if (list->tail)
  {
    list->tail->next = newNode;
    newNode->prev = list->tail;
    list->tail = newNode;
  }
  else
  {
    list->head = 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\_before_ function\. This function takes a pointer to the list, a pointer to the node before which an element will be inserted, and the element itself as its arguments\.

```cpp
int add_item_before(double_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->prev = newNode->next = NULL;
  newNode->data = item;
  
  newNode->next = pos;
  newNode->prev = pos->prev;

  if (pos->prev)
  {
    pos->prev->next = newNode;
  }
    
  pos->prev = 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(double_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(double_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_ function\. To delete a node, let's update the _next_ pointer of the previous node and the _prev_ pointer of the next node:

```cpp
int delete_item(double_linked_list_t *list, node_t *node)
{
  if (node == NULL) return -1;
  if (list == NULL) return -2;

  if (node->prev)
  {
    node->prev->next = node->next;
  }
  else
  {
    list->head = node->next;
  }
  
  if (node->next)
  {
    node->next->prev = node->prev;
  }
  else
  {
    list->tail = node->prev;
  }

  free(node);
  return 0;
}
```

There is one peculiar thing — the deletion of the first node\. The _prev _pointer of such a node will be null\. In this case the _then_ branch of the _if \(node\-\>prev\)_ condition will be executed, and the pointer to the first node in the _head_ list will be updated\.

## 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(double_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 element 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/xjfaasfcd):

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

144 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 simple little 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 doubly 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/6683/)
* [Implementation of a singly linked list in C](https://pvs-studio.com/en/blog/terms/6680/)
* [Implementation of a singly linked list in C\+\+](https://pvs-studio.com/en/blog/terms/6684/)