Doubly linked list in Data Structures Theory - Full Explanation

Introduction

Imagine you want to move forwards and backwards easily through a list of items, like flipping pages in a photo album. A doubly linked list solves this by letting you go in both directions smoothly.

Explanation

Structure of Nodes

Each item in a doubly linked list is called a node. Every node holds the actual data and has two links: one pointing to the next node and one pointing to the previous node. This setup allows easy movement forward and backward through the list.

Nodes have two links, enabling navigation in both directions.

Head and Tail

The list has a special node called the head, which is the first item, and another called the tail, which is the last item. The head's previous link and the tail's next link are usually empty or null, marking the ends of the list.

Head and tail mark the start and end, with null links indicating list boundaries.

Traversal

You can move through the list starting from the head going forward by following next links, or from the tail going backward by following previous links. This makes it easy to access items in either direction without starting over.

Traversal can happen forwards or backwards thanks to two-way links.

Insertion and Deletion

Adding or removing nodes is flexible because you can adjust the links of neighboring nodes in both directions. For example, to insert a node, you update the previous node's next link and the next node's previous link to include the new node.

Insertion and deletion involve updating links in both directions for smooth list changes.

Real World Analogy

Think of a train where each carriage is connected to the one before and after it. You can walk from the front carriage to the back or go back the other way easily. If you add or remove a carriage, you just connect the neighboring carriages again.

Structure of Nodes → Each carriage holding passengers and connected to the next and previous carriages

Head and Tail → The first and last carriages of the train marking the ends

Traversal → Walking forwards or backwards through the train carriages

Insertion and Deletion → Adding or removing a carriage by linking the neighboring carriages together

Diagram

Diagram

┌───────┐    ┌───────┐    ┌───────┐
│ Prev  │←──▶│ Prev  │←──▶│ Prev  │
│ Data  │    │ Data  │    │ Data  │
│ Next  │──▶ │ Next  │──▶ │ Next  │
└───────┘    └───────┘    └───────┘
  Head                        Tail

This diagram shows three nodes linked forward and backward, with head at the start and tail at the end.

Key Facts

Node → A container holding data and two links: one to the next node and one to the previous node.

Head → The first node in the doubly linked list with no previous node.

Tail → The last node in the doubly linked list with no next node.

Traversal → Moving through the list forward or backward by following next or previous links.

Insertion → Adding a new node by updating the links of neighboring nodes in both directions.

Deletion → Removing a node by reconnecting its previous and next nodes to each other.

Code Example

Data Structures Theory

class Node:
    def __init__(self, data):
        self.data = data
        self.prev = None
        self.next = None

class DoublyLinkedList:
    def __init__(self):
        self.head = None

    def append(self, data):
        new_node = Node(data)
        if not self.head:
            self.head = new_node
            return
        last = self.head
        while last.next:
            last = last.next
        last.next = new_node
        new_node.prev = last

    def traverse_forward(self):
        current = self.head
        while current:
            print(current.data, end=' ')
            current = current.next
        print()

    def traverse_backward(self):
        current = self.head
        if not current:
            return
        while current.next:
            current = current.next
        while current:
            print(current.data, end=' ')
            current = current.prev
        print()

# Example usage
my_list = DoublyLinkedList()
my_list.append(10)
my_list.append(20)
my_list.append(30)
my_list.traverse_forward()
my_list.traverse_backward()

Common Confusions

Thinking a doubly linked list only moves forward like a simple list.

Thinking a doubly linked list only moves forward like a simple list. A doubly linked list allows movement both forward and backward because each node links to both neighbors.

Believing the head node has a previous node or the tail node has a next node.

Believing the head node has a previous node or the tail node has a next node. The head's previous link and the tail's next link are always null, marking the ends of the list.

Summary

A doubly linked list lets you move forward and backward through items easily.

Each node connects to the next and previous nodes, with special head and tail nodes marking the ends.

You can add or remove items by updating links in both directions without starting over.

Practice

1. What is a key feature of a doubly linked list compared to a singly linked list?

easy

A. It stores data in a fixed-size array

B. Nodes only link to the next node

C. Each node has links to both the previous and next nodes

D. It uses a stack structure internally

Solution

1. Step 1: Understand node links in doubly linked lists

   A doubly linked list node contains two links: one to the previous node and one to the next node.

2. Step 2: Compare with singly linked list

   A singly linked list node only has a link to the next node, not the previous one.

3. Final Answer:

   Each node has links to both the previous and next nodes -> Option C

4. Quick Check:

   Doubly linked list = two links per node [OK]

Hint: Remember: doubly means two links per node [OK]

Common Mistakes:

• Thinking nodes only link forward
• Confusing with arrays or stacks
• Assuming fixed size storage

2. Which of the following is the correct way to update links when inserting a new node newNode after a node current in a doubly linked list?

easy

A. newNode.next = current.next; newNode.prev = current; current.next.prev = newNode; current.next = newNode;

B. newNode.prev = current.next; newNode.next = current; current.prev = newNode; current.next = newNode;

C. current.next = newNode; newNode.next = current.prev; current.prev = newNode;

D. newNode.next = current.prev; newNode.prev = current.next; current.next = newNode;

Solution

1. Step 1: Set newNode's next and prev pointers

   newNode.next should point to current.next, and newNode.prev should point to current.

2. Step 2: Update surrounding nodes to link to newNode

   current.next.prev must point back to newNode, and current.next must point to newNode.

3. Final Answer:

   newNode.next = current.next; newNode.prev = current; current.next.prev = newNode; current.next = newNode; -> Option A

4. Quick Check:

   Update newNode links, then fix neighbors [OK]

Hint: Update new node links before neighbors [OK]

Common Mistakes:

• Mixing prev and next pointers
• Not updating current.next.prev
• Assigning pointers in wrong order

3. Consider the following doubly linked list nodes and code snippet:

Node1: data=10, prev=None, next=Node2
Node2: data=20, prev=Node1, next=Node3
Node3: data=30, prev=Node2, next=None

current = Node2
print(current.prev.data, current.data, current.next.data)

What will be the output?

medium

A. None 20 30

B. 30 20 10

C. 20 20 20

D. 10 20 30

Solution

1. Step 1: Identify current node and its neighbors

   current is Node2 with data 20; prev is Node1 with data 10; next is Node3 with data 30.

2. Step 2: Print data values of prev, current, and next nodes

   Output will be 10 (prev), 20 (current), 30 (next).

3. Final Answer:

   10 20 30 -> Option D

4. Quick Check:

   Prev, current, next data = 10, 20, 30 [OK]

Hint: Prev and next data surround current data [OK]

Common Mistakes:

• Confusing prev and next nodes
• Assuming None has data
• Printing node references instead of data

4. The following code attempts to delete a node current from a doubly linked list. What is the error?

current.prev.next = current.next
current.next.prev = current.prev
current = None

medium

A. It should only update current.prev.next, not current.next.prev

B. It does not handle the case when current is the head node

C. It should update current.next.next instead of current.prev.next

D. It incorrectly sets current to None instead of deleting

Solution

1. Step 1: Analyze pointer updates for deletion

   The code updates the previous node's next pointer and the next node's prev pointer to bypass current.

2. Step 2: Check edge cases for head or tail nodes

   If current is the head (no prev), current.prev is None, so current.prev.next causes an error.

3. Final Answer:

   It does not handle the case when current is the head node -> Option B

4. Quick Check:

   Deleting head needs special handling [OK]

Hint: Check for None before updating neighbors [OK]

Common Mistakes:

• Ignoring head or tail node cases
• Assuming current is always in middle
• Confusing which pointers to update

5. You want to reverse a doubly linked list by swapping the next and prev pointers of each node. Which of the following steps is correct to achieve this?

hard

A. For each node, swap its next and prev pointers, then move to the new prev node

B. For each node, swap its next and prev pointers, then move to the new next node

C. For each node, only swap next pointers and ignore prev pointers

D. For each node, set next to None and prev to head

Solution

1. Step 1: Swap next and prev pointers for each node

   Swapping next and prev reverses the direction of links.

2. Step 2: Move to the new prev node after swapping

   After swapping, the original next is now prev, so move to node.prev to continue.

3. Final Answer:

   For each node, swap its next and prev pointers, then move to the new prev node -> Option A

4. Quick Check:

   Swap links, then follow new prev to reverse [OK]

Hint: After swapping, move to node.prev to continue [OK]

Common Mistakes:

• Moving to node.next after swapping
• Swapping only one pointer
• Setting pointers to None incorrectly