Create and Initialize Doubly Linked List in DSA Python - Time & Space Complexity

Time Complexity: Create and Initialize Doubly Linked List

O(n)

Understanding Time Complexity

When we create and initialize a doubly linked list, we want to know how the time it takes grows as we add more items.

We ask: How does the work increase when the list gets longer?

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

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

class DoublyLinkedList:
    def __init__(self, values):
        self.head = None
        self.tail = None
        for value in values:
            new_node = Node(value)
            if not self.head:
                self.head = new_node
                self.tail = new_node
            else:
                self.tail.next = new_node
                new_node.prev = self.tail
                self.tail = new_node

This code creates a doubly linked list from a list of values by adding nodes one by one at the end.

Identify Repeating Operations

• Primary operation: Looping through each value in the input list to create and link nodes.
• How many times: Exactly once for each value in the input list.

How Execution Grows With Input

Each new value causes one node to be created and linked, so the work grows directly with the number of values.

Input Size (n)	Approx. Operations
10	About 10 node creations and links
100	About 100 node creations and links
1000	About 1000 node creations and links

Pattern observation: The work increases evenly as the list gets longer, doubling the input doubles the work.

Final Time Complexity

Time Complexity: O(n)

This means the time to create the list grows in a straight line with the number of items you add.

Common Mistake

[X] Wrong: "Creating the list takes the same time no matter how many items there are."

[OK] Correct: Each item requires a new node and linking, so more items mean more work.

Interview Connect

Understanding how creating a linked list scales helps you explain your code clearly and shows you know how data structures behave as they grow.

Self-Check

"What if we added nodes at the front instead of the end? How would the time complexity change?"

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