Doubly Linked List | Representation and Basic Operations

05 min read

Unlike a Singly Linked List, in a Doubly Linked List, there is an extra pointer, the previous pointer along with the next pointer as shown below. The previous pointer points to the previous node in the list and the next pointer points to the next node in the list. So, in a doubly linked list, a node contains a reference both to its previous node and to its next node.

representation of a doubly linked list

 

Representation

 

doubly-linked-lists


/* Structure for node in doubly LL */
struct node { 
    int data; 
    struct node* next; // Pointer to next node 
    struct node* prev; // Pointer to previous node
};

 

Basic operations

The following are the basic operations supported by this Linked List.

  • Insertion − Inserts an element at a specified position in the list.
  • Deletion − Deletes an element at a specified position in the list.
  • Search − Searches an element using the given value.
  • Update − Updates/modifies an element in the list with the given value.
  • Reverse − Reverses the entire Linked list. 
  • Traverse  −  Displays all the elements in the linked list.

 

Advantages and Disadvantages of Doubly Linked List over Singly Linked List

  • Traversal can be done in both directions (from the start node to the end node as well as from the end node to the start node) in a Doubly Linked list. But this is not possible in a Singly Linked List and it can only be traversed only in one direction.
  • Deletion and insertion operations are easy to implement in a Doubly LL than a Singly LL. For example, in a singly linked list, to delete a node, the pointer to the previous node is needed for which the list is to be traversed. In a Doubly LL, we just need to know the pointer of the node to be deleted.
  • Memory has to be allocated for both the next and previous pointers in a node. Hence, the occupation of memory is higher in Doubly LL.
  • Both the pointers will have to be modified if any kind of operation is performed like insertion, deletion, etc in case of Doubly LL.

 

Applications

  • The browser cache which allows you to hit the BACK buttons or navigate through previous pages.
  • Applications that have a Most Recently Used (MRU) lists.
  • A stack, hash table, and binary tree can be implemented using a doubly linked list. 
  • Undo features in publishing or editing applications like Photoshop and Word.
  • A great way to represent a deck of cards in a game where removing items from anywhere in the deck is essential.

 

POST A NEW COMMENT
     
  • Input (stdin)

    Output (stdout)


    Input (stdin)

    Your Output (stdout)

    Expected Output

    Compiler Message

    Input (stdin)

    2    3

    Your Output (stdout)

    5

    Expected Output

    5

    Compiler Message

    5

    Error