Doubly Linked Lists (DLL)

After singly-linked lists, we've 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)
Tail pointer

Introduction #

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

Furthermore, since a linked list can only be traversed in one direction, this limits us to a great extent. Thus we 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, we simply need to add a new member to the already constructed Node class:

Create a free account to view this lesson.

Continue your learning journey with a 14-day free trial.

By signing up, you agree to Educative's Terms of Service and Privacy Policy

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) #