What is a doubly linked list
A doubly linked list is an extension of a singly linked list.
A singly linked list is a sequence of data structures (nodes), which are connected together through links. A node is a data entity that contains data of any type and a reference to another node.
The limitation of a singly linked list is it allows us to traverse forward. A doubly linked list has an additional pointer on a previous node.
A
doubly linked listis a linked data structure that consists of a set of sequentially linked nodes. Each node has three values
- Data
- Pointer to the next node
- pointer to the previous node
Operations
- Insert
- Delete
- Search
The worst-case for Insert, Delete and Search is O(n). Insertion and Deletion at the head can be done in O(1). Insertion and Deletion at the tail can be done in O(1) (when the last element is known) and O(n) (when the last element is unknown)
