Can you explain what a doubly linked list data structure is and how it works?

A doubly linked list is a data structure consisting of nodes, where each node contains data and two references:

• to the next node (next),
• to the previous node (prev).

This allows efficient traversal of the list in both directions.

How it works:

• The first node in the list has no previous node (prev = null).
• The last node in the list has no next node (next = null).
• When adding or removing nodes, links can be easily changed without affecting the entire list.

Example of a node in Dart (Flutter):

class Node<T> {
  T data;
  Node<T>? next;
  Node<T>? prev;

  Node(this.data);
}

A doubly linked list is useful when you need to quickly insert or delete elements in the middle of the list and have the ability to traverse the list in both directions.