Doubly Linked List

Introduction

A Doubly Linked List is a linear data structure consisting of nodes where each node contains three components: a data field, a pointer to the next node, and a pointer to the previous node in the sequence. The first node's previous pointer is null, and the last node's next pointer is null, marking the boundaries of the list. It allows bidirectional traversal and supports efficient insertion and deletion operations at both ends or any position without the need to shift elements.

Structure of Doubly Linked List

Data: The value stored in the node.

Next Pointer: A reference to the next node in the list.

Previous Pointer: A reference to the previous node in the list

Representation of Doubly Linked List

//dllrepresetation.c
struct Node {
  int data;
  Node* prev;
  Node* next;
};
struct Node *createNode(int new_data) {
  struct Node *new_node = (struct Node *)
  malloc(sizeof(struct Node));
  new_node->data = new_data;
  new_node->next = NULL;
  new_node->prev = NULL;
  return new_node;
}

Operation on Doubly Linked List

Insertion

• Insertion At Beginning

• Insertion At Position

• Insertion At Tail

Deletion

• Deletion At Beginning

• Deletion At Position

• Deletion At Tail

Traversal

Forward Traversal

1. Star Initialize a pointer (current) to the head of the list.

2. While (current!=null)

• Process the data of the current node.

• Move the pointer to the next node (current = current->next).

// forwardtraversalondll.c
void forwardTraversal(struct Node* head) {
  struct Node* curr = head;
  while (curr != NULL) {
      printf("%d ", curr->data);
      curr = curr->next;
  }
}

Backward Traversal

1. Star Initialize a pointer (current) to the tail of the list.

2. While (current!=null)

• Process the data of the current node.

• Move the pointer to the previous node (current = current->prev).

// backwardtraversalondll.c
void backwardTraversal(struct Node* tail) {
  struct Node* curr = tail;
  while (curr != NULL) {
      printf("%d ", curr->data);
      curr = curr->prev;
  }
}

Searching

1. Start from the head of the linked list.
2. Check if the current node's data matches the target value:

• If a match is found, return true.

3. Move to the next node.
4. Repeat steps 2 and 3 until:

• The target value is found (return true).
• The end of the list is reached (return false).

//searchingondll.c
bool searchLinkedList(struct Node* head, int target)
{
  while (head != NULL) {
      if (head->data == target) {
          return true; // Value found
      }
      head = head->next;
  }
  return false;
}