Doubly Linked Lists

Doubly Linked Lists

A doubly linked list is a type of data structure that consists of nodes. Each node contains three components: a data field, a pointer to the next node, and a pointer to the previous node. This structure allows for traversal in both directions: forward and backward. Doubly linked lists are useful when you need to access elements from both ends or perform operations that require bidirectional traversal.

Structure of a Doubly Linked List

Each node in a doubly linked list has the following structure:

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

In this structure:

• data: This is the value stored in the node.
• next: This is a pointer that points to the next node in the list.
• prev: This is a pointer that points to the previous node in the list.

Creating a Doubly Linked List

To create a doubly linked list, you need to define the head of the list. The head is a pointer to the first node. If the list is empty, the head will be null.

Node* head = NULL;

You can create a new node using the following function:

Node* createNode(int value) {  Node* newNode = new Node();  newNode->data = value;  newNode->next = NULL;  newNode->prev = NULL;  return newNode;}

Inserting Nodes in a Doubly Linked List

You can insert nodes at different positions in a doubly linked list: at the beginning, at the end, or in the middle.

Inserting at the Beginning

To insert a node at the beginning, you need to adjust the pointers of the new node and the existing head:

void insertAtBeginning(Node** head, int value) {  Node* newNode = createNode(value);  newNode->next = *head;  if (*head != NULL) {    (*head)->prev = newNode;  }  *head = newNode;}

Inserting at the End

To insert a node at the end, you need to traverse the list until you reach the last node:

void insertAtEnd(Node** head, int value) {  Node* newNode = createNode(value);  if (*head == NULL) {    *head = newNode;    return;  }  Node* last = *head;  while (last->next != NULL) {    last = last->next;  }  last->next = newNode;  newNode->prev = last;}

Inserting in the Middle

To insert a node in the middle, you need to find the appropriate position:

void insertAfter(Node* prevNode, int value) {  if (prevNode == NULL) {    return;  }  Node* newNode = createNode(value);  newNode->next = prevNode->next;  prevNode->next = newNode;  newNode->prev = prevNode;  if (newNode->next != NULL) {    newNode->next->prev = newNode;  }}

Deleting Nodes in a Doubly Linked List

Deleting nodes requires careful pointer management to avoid memory leaks. You can delete a node from the beginning, the end, or a specific position.

Deleting from the Beginning

To delete from the beginning, you need to adjust the head pointer:

void deleteFromBeginning(Node** head) {  if (*head == NULL) {    return;  }  Node* temp = *head;  *head = (*head)->next;  if (*head != NULL) {    (*head)->prev = NULL;  }  delete temp;}

Deleting from the End

To delete from the end, you need to traverse to the last node:

void deleteFromEnd(Node** head) {  if (*head == NULL) {    return;  }  Node* last = *head;  while (last->next != NULL) {    last = last->next;  }  if (last->prev != NULL) {    last->prev->next = NULL;  } else {    *head = NULL;  }  delete last;}

Deleting a Specific Node

To delete a specific node, you need to adjust the pointers of the adjacent nodes:

void deleteNode(Node** head, Node* delNode) {  if (*head == NULL || delNode == NULL) {    return;  }  if (*head == delNode) {    *head = delNode->next;  }  if (delNode->next != NULL) {    delNode->next->prev = delNode->prev;  }  if (delNode->prev != NULL) {    delNode->prev->next = delNode->next;  }  delete delNode;}

Traversing a Doubly Linked List

To traverse a doubly linked list, you can start from the head and move to the next node or start from the tail and move to the previous node.

void traverseForward(Node* head) {  Node* current = head;  while (current != NULL) {    printf("%d ", current->data);    current = current->next;  }}

void traverseBackward(Node* tail) {  Node* current = tail;  while (current != NULL) {    printf("%d ", current->data);    current = current->prev;  }}

Applications of Doubly Linked Lists

Doubly linked lists have various applications, including:

• Implementing complex data structures like deques (double-ended queues).
• Managing memory in applications that require frequent insertions and deletions.
• Creating navigation systems in applications that require back and forth traversal.

Summary

• A doubly linked list consists of nodes with data, next, and previous pointers.
• Nodes can be inserted at the beginning, end, or middle of the list.
• Nodes can be deleted from the beginning, end, or a specific position.
• Traversal can be done in both forward and backward directions.

Check your understanding

• What are the main components of a doubly linked list node?
• How do you insert a node at the end of a doubly linked list?
• What is the procedure to delete a specific node from a doubly linked list?
• List one application of a doubly linked list.