Thread by @swapnakpanda

💙 Data Structures in a Nutshell: Doubly Linked List

⇨ What? Why? How?
⇨ List of Operations
⇨ Pseudo Code
⇨ Time & Space Complexities

⇩

Before starting, if you want to learn more about a simple Linked List, check it 👇

https://twitter.com/swapnakpanda/status/1452928917254279180?s=20

We will cover,

0️⃣ Basics (What, Why, How)
1️⃣ Traversal
2️⃣ IsEmpty
3️⃣ Size
4️⃣ Fetch an Element
5️⃣ Insert an Element
6️⃣ Delete an Element
7️⃣ Time & Space Complexities

0️⃣ Basics

✪ What is a Doubly Linked List?

• a LINEAR bi-directional data structure
• its elements may not be in contiguous memory location
• each element has a reference to its next and previous element

✪ Why do we require a Doubly Linked List?

• The shortcoming of a normal Linked List is unidirectional.
• The traversal always begins from the starting which may be slower when an element is very far.

✪ What is an element in a Double Linked List popularly called?
A Node.

✪ How is a node structured?

A node has 3 parts.

• The reference (or, pointer) to the previous node. For the first node this is NULL as there is no previous node.

• The value to be stored
• The reference (or, pointer) to the next node. For the last node this is NULL as there is no next node.

✪ What extra is required?

For convenience and performance, we store 👇 as well

• Head: A reference of the very first node.
• Tail: A reference of the last node.
• Length: Size of the list.

✪ Pseudo Code ✪

Node {
prev: Node,
Value,
next: Node
}
Head:Node = NULL
Tail:Node = NULL
Length:Number = 0

✪ ✪ ✪ ✪ ✪ ✪ ✪ ✪

1️⃣ Traverse through Nodes

✪ Why do we need to traverse?
Elements in a Double Linked List are not stored contiguously. In order to reach at an element, we need to traverse through the list till that element.

✪ How to traverse?
2 ways.

1️⃣.1️⃣ Traverse from Start

✪ Where to start?
• Start from Head
• If Head is NULL, List is empty hence no traversal required

✪ How to traverse from one node to another?
• Using "next" reference of a node

✪ Where to end?
• When "next" reference of a node is NULL.

1️⃣.2️⃣ Traverse from End

✪ Where to start?
• Start from Tail
• If Tail is NULL, List is empty hence no traversal required

✪ How to traverse from one node to another?
• Using "prev" reference of a node

✪ Where to end?
• When "prev" reference of a node is NULL

2️⃣ IsEmpty

If Length is 0 or, Head is NULL or, Tail is NULL. In any case, it means there are no elements in the list. Hence it is empty.

✪ Pseudo Code ✪

Return Length is 0
Or.
Return Head is NULL
Or,
Return Tail is NULL

✪✪✪✪✪✪✪✪✪✪

3️⃣ Size

The Length contains the size of the list.

✪ Pseudo Code ✪

Return Length

✪✪✪✪✪✪✪✪✪✪

4️⃣.1️⃣ Get Front Node

Head has the reference to the very first node aka the "Front Node".

But when Head is NULL, linked list is empty and hence there is no front node present.

✪ Pseudo Code ✪

If Head is NULL
Throw Error
Return Head

4️⃣.2️⃣ Get End Node

Tail has the reference to the very last node aka the "End Node".

But when Tail is NULL, linked list is empty and hence there is no end node present.

✪ Pseudo Code ✪

If Tail is NULL
Throw Error
Return Tail

4️⃣.3️⃣ Get Any Node

Let's say the task is to get a node at kth index

• k = 0 ⇨ the very first node
• k = (Length - 1) ⇨ the very last node
• k <= Length / 2 ⇨ Traverse from Head
• k > Length / 2 ⇨ Traverse from Tail

✪ Pseudo Code ✪

👉 Is k less than or, equal to (Length / 2)? If yes, traverse from Head.

Pseudo code 👇

current = Head
i = 0
while i < k and current is not NULL
current = current->next
i++

If i < 0 or current is NULL
Throw Error

Return current

👉 Is k greater than (Length / 2)? If yes, traverse from Tail.

Pseudo Code 👇

current = Tail
i = Length - 1
while i > k and current is not NULL
current = current->prev
i--

If i < 0 or current is NULL
Throw Error

Return current

✪✪✪✪✪✪

5️⃣.1️⃣ Insert at the Front

Given: "node", which will be inserted at the front

• "next" of "node" should point to current Head node
• "prev" of "Head" should point to "node"
• "node" should be the Head node
• In case of empty list, "node" should be the Tail node as well

✪ Pseudo Code ✪

If node is NULL
Throw Error

node->next = Head

if Head is not NULL
Head->prev = node

Head = node

if Tail is NULL
Tail = node

Length++

✪✪✪✪✪✪

5️⃣.2️⃣ Insert at the End

Given: "node", which will be inserted at the end

• "prev" of "node" should point to current Tail node
• "next" of "Tail" should point to "node"
• "node" should be the Tail node
• In case of empty list, "node" should be the Head node as well

✪ Pseudo Code ✪

If node is NULL
Throw Error

node->prev = Tail

if Tail is not NULL
Tail->next = node

Tail = node

if Head is NULL
Head = node

Length++

✪✪✪✪✪✪

5️⃣.3️⃣ Insert at any position

Given:
• "node", which will be inserted at kth position
• "current", which is the node at (k-1)th position [Use 4️⃣.3️⃣ to get it)

We should do as 👇

✪ Pseudo Code ✪

If node is NULL or current is NULL
Throw Error

If current->next is not NULL
current->next->prev = node

node->next = current->next
node-> prev = current

current->next = node

Length++

✪✪✪✪✪✪✪✪✪

6️⃣.1️⃣ Delete from Front

After deletion,
• the Head should refer to the current 2nd node
• the "next" of 1st node should be NULL
• the "prev" of Head node should be NULL
• In case of empty list, Tail should be NULL

✪ Pseudo Code ✪

If Head is NULL
Throw Error

temp = Head
Head = temp->next
temp->next = NULL

If Head is not NULL
Head->prev = NULL
Else
Tail = NULL

Length--

✪✪✪✪✪✪

6️⃣.2️⃣ Delete from End

After deletion,
• the Tail should refer to the current last but one node
• the "prev" of last node should be NULL
• the "next" of Tail node should be NULL
• In case of empty list, Head should be NULL

✪ Pseudo Code ✪

If Tail is NULL
Throw Error

temp = Tail
Tail = temp->prev
temp->prev = NULL

If Tail is not NULL
Tail->prev = NULL
Else
Head = NULL

Length--

✪✪✪✪✪✪

6️⃣.3️⃣ Delete from any position

Given:
• "current", which is the node at kth position

Do 👇
• "next" of "prev" of "current" should be "next" of "current"
• "prev" of "next" of "current" should be "prev" of "current"
• "next" and "prev" of "current" should be NULL

✪ Pseudo Code ✪

If current or current->next or current->prev is NULL
Throw Error

current->prev->next = current->next
current->next->prev = current-prev

current->prev = NULL
current->next = NULL

Length--

✪✪✪✪✪✪

7️⃣ Space & Time Complexity

IsEmpty: O(1),N/A
Size: O(1), O(1)
GetFrontNode: O(1), N/A
GetEndNode: O(1), N/A
GetAnyNode: O(n), N/A
InsertAtFront: O(1), N/A
InsertAtEnd: O(1), N/A
InsertAtAny: O(1), N/A
DeleteFromFront: O(1), O(1)
DeleteFromEnd: O(1), O(1)
DeleteFromAny: O(1), N/A

To help spreading this,
♥️ Like this 🧵
🔁 RETWEET the first tweet

To suggest or give feedback,
💬 Reply to this 🧵

To never miss any content from me,
✅ Follow @swapnakpanda
🔔 Turn on Notifications

Have you missed any DSA related contents that I have written so far? Find everything organised at a single place, 👇

twitter.com/i/events/14502…