Doubly Linked Lists (DLL)

After singly linked lists, you have come to the more evolved version of the linked list data structure: doubly linked lists.

We'll cover the following

- Introduction
- Structure of the Doubly Linked List (DLL)
- - Impact on deletion
- Time complexity

Introduction

By now, you must have noticed a constraint that arises when dealing with singly linked lists. For any function that does not operate at the head node, you must traverse the whole list in a loop.

While the search operation in a normal list works in the same way, access is much faster as lists allow indexing.

Furthermore, since a linked list can only be traversed in one direction, you needlessly have to keep track of previous elements.

This is where the doubly linked list comes to the rescue!

Structure of the Doubly Linked List (DLL)

The only difference between doubly and singly linked lists is that in DLLs, each node contains pointers for both the previous and the next node. This makes the DLLs bi-directional.

To implement this in code, you simply need to add a new member to the already constructed Node Class:

Level up your interview prep. Join Educative to access 80+ hands-on prep courses.

Introduction to Complexity Measures

Introduction to Arrays

Introduction to Linked Lists

Introduction to Stack/Queues

Introduction to Graphs

Introduction to Trees

Trie

Introduction to Heap

Introduction to Hashing

Summary of Data Structures

Doubly Linked Lists (DLL)

Introduction

Structure of the Doubly Linked List (DLL)