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.

## Advantages of Doubly Linked List

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

## Disadvantages of Doubly Linked List

**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);
if (*headRef == NULL) {
*headRef = newNode;
return;
}
(*headRef)->prev = newNode;
newNode->next = *headRef;
*headRef = newNode;
}
```

### 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:

```
void deleteFromBeginning(struct Node** headRef) {
if (*headRef == NULL)
return;
struct Node* temp = *headRef;
if ((*headRef)->next != NULL)
(*headRef)->next->prev = NULL;
*headRef = (*headRef)->next;
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:

```
void traverse(struct Node* head) {
struct Node* current = head;
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.