What is a doubly-linked list (DLL)? What are its applications

Web Development
,
#1

his is a complex type of a linked list wherein a node has two references:

  • One that connects to the next node in the sequence
  • Another that connects to the previous node.

This structure allows traversal of the data elements in both directions (left to right and vice versa).
Applications of DLL are:

  • A music playlist with next song and previous song navigation options.
  • The browser cache with BACK-FORWARD visited pages
  • The undo and redo functionality on platforms such as word, paint etc, where you can reverse the node to get to the previous page.
#2

A doubly linked list is a data structure in which each node stores a link to its next node(like singly linked list) and to its previous node as well by using an extra pointer called previous pointer.

The popular operation on it is same as that of singly linked list: insertion, deletion, traversal(both directions).

The advantages of doubly over singly linked lists are:

  1. The extra pointer(previous pointer) makes the doubly linked list to be able to be traversed in both the directions.
  2. This allows the insertion of a node at any position(before as well as after a node) in the list.
  3. Given the pointer to a node to be deleted, deletion in doubly linked list is more efficient than the singly linked list.
  4. It can work as a queue and a qtack at the same time.

However, it has some disadvantages too:

  1. every node needs extra space for an additional previous pointer.
  2. this previous pointer needs to be maintained during each operation.