a concise shot of dev knowledge
Become a Contributor
Concise shots of dev knowledge

RELATED TAGS

linked list
data structures
interviews

What is a doubly linked list?

Edpresso 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).

RELATED TAGS

linked list
data structures
interviews
RELATED COURSES

View all Courses

Keep Exploring

Learn in-demand tech skills in half the time

Copyright ©2022 Educative, Inc. All rights reserved.

soc2