Trusted answers to developer questions
Trusted Answers to Developer Questions

Related Tags

linked list
data structures

What is a doubly linked list?

Educative Answers Team

The limitations of singly linked lists

The singly linked list (SLL) is a linear data structure comprising of nodes chained together in a single direction. Each node contains a data member holding useful information, and a pointer to the next node.

svg viewer

The problem with this structure is that it only allows us to traverse forward, i.e., we cannot iterate back to a previous node if required.

This is where the doubly linked list (DLL) shines. DLLs are an extension of basic linked lists with only one difference:

A doubly linked list contains a pointer to the next node as well as the previous node. This ensures that the list can be traversed in both directions.

The doubly linked list class

From the definition above, we can see that a DLL node has three fundamental members:

  • the data
  • a pointer to the next node
  • a pointer to the previous node
svg viewer
There is a pointer to next and the previous node.

A DLL costs more in terms of memory due to the inclusion of a p (previous) pointer. However, the reward for this is that iteration becomes much more efficient.

Time Complexity

The worst case complexity for search, insertion, and deletion is O(n). Insertion and deletion at the head can be done in O(1).


linked list
data structures
Copyright ©2022 Educative, Inc. All rights reserved

View all Courses

Keep Exploring