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.

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