Create and Initialize Doubly Linked List in DSA Python - Cheat Sheet & Quick Revision

Recall & Review

beginner

What is a doubly linked list?

A doubly linked list is a chain of nodes where each node has three parts: data, a link to the next node, and a link to the previous node. This allows moving forward and backward through the list.

beginner

What are the main parts of a node in a doubly linked list?

Each node has:
1. Data (the value stored)
2. Next pointer (link to the next node)
3. Previous pointer (link to the previous node)

beginner

How do you initialize an empty doubly linked list in Python?

You create a class for the list with a head pointer set to None, meaning the list starts empty with no nodes.

beginner

Why does a doubly linked list have both next and previous pointers?

Having both pointers allows you to move forward and backward through the list easily, unlike a singly linked list which only moves forward.

beginner

What is the first step when creating a doubly linked list?

Define a Node class with data, next, and previous pointers, then create a DoublyLinkedList class with a head pointer set to None.

What does the 'previous' pointer in a doubly linked list node point to?

A The next node in the list

B The tail of the list

C The previous node in the list

D The head of the list

The 'previous' pointer points to the node before the current one, allowing backward traversal.

How do you represent an empty doubly linked list?

A Head points to a node with data 0

B Head points to itself

C Head points to tail

D Head is None

An empty list has no nodes, so the head pointer is set to None.

Which of these is NOT part of a doubly linked list node?

A Random pointer

B Next pointer

C Previous pointer

D Data

A standard doubly linked list node has data, next, and previous pointers. A random pointer is not standard.

What advantage does a doubly linked list have over a singly linked list?

A Can be traversed backward

B Uses less memory

C Faster insertion at head

D Simpler to implement

Doubly linked lists allow traversal in both directions because of the previous pointer.

When initializing a doubly linked list, what is the initial value of the head pointer?

A 0

B None

C A new node

D Tail node

The head pointer is set to None to indicate the list is empty.

Explain how to create and initialize a doubly linked list from scratch.

Think about what each node needs and how the list starts empty.

Describe the structure of a node in a doubly linked list and why it has two pointers.

Focus on the purpose of each pointer.

Practice

1. What is the main difference between a doubly linked list and a singly linked list?

easy

A. A doubly linked list can only be traversed forward.

B. A doubly linked list stores data in arrays instead of nodes.

C. A doubly linked list has nodes with pointers to both next and previous nodes.

D. A doubly linked list does not have a head pointer.

Solution

1. Step 1: Understand node structure in doubly linked list

   Each node in a doubly linked list contains two pointers: one to the next node and one to the previous node.

2. Step 2: Compare with singly linked list

   A singly linked list node has only one pointer to the next node, so it can only be traversed forward.

3. Final Answer:

   A doubly linked list has nodes with pointers to both next and previous nodes. -> Option C

4. Quick Check:

   Doubly linked list nodes have two pointers = C [OK]

Hint: Remember: doubly linked list nodes link both ways [OK]

Common Mistakes:

• Thinking doubly linked list uses arrays
• Assuming it can only go forward
• Confusing head pointer presence

2. Which of the following is the correct way to define a node class for a doubly linked list in Python?

easy

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

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

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

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

Solution

1. Step 1: Identify required attributes for doubly linked list node

   A doubly linked list node must have data, a pointer to the next node, and a pointer to the previous node.

2. Step 2: Check each option for completeness

   class Node: def __init__(self, data): self.data = data self.next = None self.prev = None correctly defines data, next, and prev attributes initialized properly.

3. Final Answer:

   class Node with data, next, and prev attributes initialized -> Option A

4. Quick Check:

   Node needs data, next, prev = A [OK]

Hint: Doubly linked list node needs both next and prev pointers [OK]

Common Mistakes:

• Omitting prev pointer
• Omitting data attribute
• Defining next and prev but missing data

3. What will be the output of the following code that creates a doubly linked list with nodes containing 1, 2, 3?

class Node:
    def __init__(self, data):
        self.data = data
        self.next = None
        self.prev = 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 display_forward(self):
        current = self.head
        result = []
        while current:
            result.append(current.data)
            current = current.next
        return result

dll = DoublyLinkedList()
dll.append(1)
dll.append(2)
dll.append(3)
print(dll.display_forward())

medium

A. [3, 2, 1]

B. []

C. [1, 3, 2]

D. [1, 2, 3]

Solution

1. Step 1: Append nodes 1, 2, 3 to the doubly linked list

   Nodes are added at the end. First node 1 becomes head, then 2 is linked after 1, then 3 after 2.

2. Step 2: Display nodes forward

   Starting from head, nodes are visited in order 1 -> 2 -> 3, collected in list [1, 2, 3].

3. Final Answer:

   [1, 2, 3] -> Option D

4. Quick Check:

   Appending nodes in order shows [1, 2, 3] [OK]

Hint: Appending adds nodes at end; display forward shows insertion order [OK]

Common Mistakes:

• Confusing order of nodes
• Printing empty list if head is null
• Mixing up forward and backward traversal

4. Identify the error in the following code that tries to append nodes to a doubly linked list:

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

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

    def append(self, data):
        new_node = Node(data)
        if self.head is None:
            self.head = new_node
        else:
            last = self.head
            while last.next:
                last = last.next
            last.next = new_node
            new_node.next = last

medium

A. new_node.next should be new_node.prev to link backward

B. Missing return statement after setting head

C. The while loop condition should be last.prev instead of last.next

D. Node class is missing data attribute

Solution

1. Step 1: Analyze append method's linking logic

   After finding last node, code sets last.next = new_node correctly, but sets new_node.next = last, which is wrong.

2. Step 2: Correct backward link pointer

   Backward link should be new_node.prev = last, not new_node.next = last.

3. Final Answer:

   new_node.next should be new_node.prev to link backward -> Option A

4. Quick Check:

   Backward link uses prev pointer = D [OK]

Hint: Backward link uses prev, not next pointer [OK]

Common Mistakes:

• Setting new_node.next instead of new_node.prev
• Forgetting to link backward pointer
• Confusing next and prev pointers

5. You want to create a doubly linked list from a Python list of values [10, 20, 30] and then print the list backward starting from the last node. Which code snippet correctly initializes the doubly linked list and prints the values backward?

hard

A. dll = DoublyLinkedList()
for val in [10, 20, 30]:
dll.append(val)
current = dll.head
while current.prev:
current = current.prev
while current:
print(current.data, end=' ')
current = current.next

B. dll = DoublyLinkedList()
for val in [10, 20, 30]:
dll.append(val)
current = dll.head
while current.next:
current = current.next
while current:
print(current.data, end=' ')
current = current.prev

C. dll = DoublyLinkedList()
for val in [10, 20, 30]:
dll.append(val)
current = dll.head
while current.next:
current = current.next
while current:
print(current.data, end=' ')
current = current.next

D. dll = DoublyLinkedList()
for val in [10, 20, 30]:
dll.append(val)
current = dll.head
while current.prev:
current = current.prev
while current:
print(current.data, end=' ')
current = current.prev

Solution

1. Step 1: Append values 10, 20, 30 to doubly linked list

   Values are appended in order, head points to 10, last node is 30.

2. Step 2: Move to last node by traversing next pointers

   Start at head, move forward while current.next exists to reach last node (30).

3. Step 3: Print backward by moving prev pointers

   From last node, print data and move backward using current.prev until null.

4. Final Answer:

   Traverse forward to the last node using next pointers, then print backward using prev pointers, producing 30 20 10 -> Option B

5. Quick Check:

   Traverse next to last, then prev backward = A [OK]

Hint: Go forward to last node, then traverse backward with prev [OK]

Common Mistakes:

• Trying to move backward from head
• Using next pointer to go backward
• Not moving to last node before backward print