What Is Doubly Linked List in Data Structure in C?

//

Angela Bailey

Doubly Linked List in Data Structure in C

A doubly linked list is a data structure that consists of a sequence of nodes. Each node contains three fields: the data field, and two pointers, one pointing to the previous node and one pointing to the next node. This allows traversal in both directions, unlike a singly linked list where traversal is only possible in one direction.

• Bidirectional traversal: As mentioned earlier, a doubly linked list allows traversal in both directions. This makes it easier to navigate through the elements, especially when there is a need to move back and forth.
• Insertion and deletion: Insertion and deletion operations are more efficient compared to arrays or singly linked lists.

In a singly linked list, insertion or deletion requires updating multiple pointers, whereas in a doubly linked list, it can be done by adjusting just two pointers.

• Reverse traversal: With the help of the previous pointers, reverse traversal becomes possible. This can be useful in scenarios where accessing elements from the end of the list is required.

• Increased memory usage: The presence of an extra pointer for each node increases memory consumption compared to singly linked lists.
• Complexity: The presence of additional pointers complicates the implementation and maintenance of doubly linked lists compared to singly linked lists.

Doubly Linked List Implementation in C

To implement a doubly linked list in C, we need to define a structure for each node containing the necessary fields:

``````
struct Node {
int data;
struct Node* prev;
struct Node* next;
};
```
```

To create a new node, we can use the following function:

``````
struct Node* createNode(int data) {
struct Node* newNode = (struct Node*)malloc(sizeof(struct Node));
newNode->data = data;
newNode->prev = NULL;
newNode->next = NULL;
return newNode;
}
```
```

Next, we need to define functions for various operations on the doubly linked list, such as insertion, deletion, and traversal.

Insertion Operation

The insertion operation in a doubly linked list can be performed at the beginning, end, or any specific position in the list. Here’s an example of inserting a node at the beginning:

``````
void insertAtBeginning(struct Node** headRef, int data) {
struct Node* newNode = createNode(data);

return;
}

}
```
```

Deletion Operation

The deletion operation can also be performed at various positions in the doubly linked list. Here’s an example of deleting a node from the beginning:

``````
return;

free(temp);
}
```
```

Traversal Operation

To traverse a doubly linked list, we can start from the head and move to the next nodes until we reach the end. Here’s an example of traversing and printing the elements:

``````

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

These are just basic implementations of operations on a doubly linked list. There are many other operations that can be performed, such as searching for a particular element, reversing the list, and sorting the list.

Conclusion

A doubly linked list is a versatile data structure that provides bidirectional traversal and efficient insertion/deletion operations. However, it comes with increased memory usage and added complexity compared to singly linked lists. Understanding how to implement and work with doubly linked lists in C can be beneficial in solving various problems efficiently.