Our website uses cookies to enhance your browsing experience.
Accept
to the top
close form

Fill out the form in 2 simple steps below:

Your contact information:

Step 1
Congratulations! This is your promo code!

Desired license type:

Step 2
Team license
Enterprise license
** By clicking this button you agree to our Privacy Policy statement
close form
Request our prices
New License
License Renewal
--Select currency--
USD
EUR
* By clicking this button you agree to our Privacy Policy statement

close form
Free PVS‑Studio license for Microsoft MVP specialists
* By clicking this button you agree to our Privacy Policy statement

close form
To get the licence for your open-source project, please fill out this form
* By clicking this button you agree to our Privacy Policy statement

close form
I am interested to try it on the platforms:
* By clicking this button you agree to our Privacy Policy statement

close form
check circle
Message submitted.

Your message has been sent. We will email you at


If you do not see the email in your inbox, please check if it is filtered to one of the following folders:

  • Promotion
  • Updates
  • Spam

Webinar: Parsing C++ - 10.10

>
>
>
Implementation of a doubly linked list …

Implementation of a doubly linked list in C

Jun 21 2023

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 doubly linked list in C. Click 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:

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:

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:

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.

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.

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.

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:

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:

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:

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:

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:

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:

<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".

Conclusion

In this article, we have discussed how to implement a doubly 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.

Additional links

Popular related articles


Comments (0)

Next comments next comments
close comment form