Doubly Linked List is a linear data structure consisting of a collection of nodes which are stored in separated physical memory locations

Each node comprises three parts, the data and two pointers in which one is linked to previous node and the other is linked to next node. The previous pointer of the head node is linked to null while the next pointer of the tail node is linked to null

Operations and Time complexity

  • Traversal O(N)
  • Add First O(1), Add Last O(1)
  • Remove First O(1), Remove Last O(1)

Implementation example