Our website uses cookies to enhance your browsing experience.
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:
Webinar: Evaluation - 05.12
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.
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;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;
}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;
}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;
}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;
}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);
}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;
}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.
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.
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.
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".
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.
0
0
0
0