Doubly Linked List Structure and Node Design in DSA C++ - Time & Space Complexity

Time Complexity: Doubly Linked List Structure and Node Design

O(n)

Understanding Time Complexity

We want to understand how the time to create and link nodes in a doubly linked list grows as we add more nodes.

How does the work increase when the list gets longer?

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

struct Node {
    int data;
    Node* prev;
    Node* next;
    Node(int val) : data(val), prev(nullptr), next(nullptr) {}
};

void append(Node*& head, int val) {
    Node* newNode = new Node(val);
    if (!head) {
        head = newNode;
        return;
    }
    Node* temp = head;
    while (temp->next) {
        temp = temp->next;
    }
    temp->next = newNode;
    newNode->prev = temp;
}
    

This code creates a doubly linked list node and appends a new node at the end of the list.

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

• Primary operation: The while loop that moves through the list to find the last node.
• How many times: It runs once for each node already in the list, so if there are n nodes, it runs about n times.

How Execution Grows With Input

As the list grows, the time to add a new node grows roughly in a straight line with the number of nodes.

Input Size (n)	Approx. Operations
10	About 10 steps to find the end
100	About 100 steps to find the end
1000	About 1000 steps to find the end

Pattern observation: The work increases directly with the number of nodes, so doubling nodes doubles the work.

Final Time Complexity

Time Complexity: O(n)

This means adding a node takes longer as the list gets longer, growing in a straight line with the list size.

Common Mistake

[X] Wrong: "Appending a node always takes the same time no matter how long the list is."

[OK] Correct: Because the code must walk through all existing nodes to find the end, the time grows with the list length.

Interview Connect

Understanding how node traversal affects time helps you explain and improve linked list operations clearly in interviews.

Self-Check

"What if we kept a pointer to the tail node? How would the time complexity of appending change?"

Practice

1. What is the main advantage of a doubly linked list over a singly linked list?

easy

A. It can only be traversed forward.

B. It uses less memory than a singly linked list.

C. It requires only one pointer per node.

D. It allows traversal in both forward and backward directions.

Solution

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

   Each node has two pointers: one to the next node and one to the previous node.

2. Step 2: Compare traversal capabilities

   This allows moving forward and backward through the list, unlike singly linked lists which only allow forward traversal.

3. Final Answer:

   It allows traversal in both forward and backward directions. -> Option D

4. Quick Check:

   Doubly linked list = two-way traversal [OK]

Hint: Remember: two pointers mean two directions [OK]

Common Mistakes:

• Thinking it uses less memory than singly linked list
• Assuming it has only one pointer per node
• Believing it can only traverse forward

2. Which of the following is the correct way to declare a node structure for a doubly linked list in C++?

easy

A. struct Node { int data; Node* next; Node* prev; };

B. struct Node { int data; Node next; Node prev; };

C. struct Node { int data; Node* next; int prev; };

D. struct Node { int data; int next; int prev; };

Solution

1. Step 1: Check pointer usage for next and prev

   In a doubly linked list, next and prev must be pointers to Node, so Node* next and Node* prev are correct.

2. Step 2: Identify incorrect declarations

   struct Node { int data; Node next; Node prev; }; uses Node next and Node prev (not pointers), C uses int prev, and D uses int for both next and prev, which is incorrect.

3. Final Answer:

   struct Node { int data; Node* next; Node* prev; }; -> Option A

4. Quick Check:

   Pointers for next and prev = struct Node { int data; Node* next; Node* prev; }; [OK]

Hint: Pointers to Node must use * symbol [OK]

Common Mistakes:

• Using Node instead of Node* for next and prev
• Using int type for pointers
• Missing pointer symbols

3. Consider the following code snippet for a doubly linked list node insertion at the front:

struct Node {
  int data;
  Node* next;
  Node* prev;
};

Node* head = nullptr;

Node* newNode = new Node{10, nullptr, nullptr};
newNode->next = head;
if (head != nullptr) {
  head->prev = newNode;
}
head = newNode;

// What is the data in head->next after insertion?

medium

A. nullptr

B. 10

C. Undefined

D. Garbage value

Solution

1. Step 1: Analyze initial head value

   Initially, head is nullptr, meaning the list is empty.

2. Step 2: After insertion, newNode->next points to old head (nullptr)

   Since head was nullptr, newNode->next is set to nullptr, so head->next is nullptr after insertion.

3. Final Answer:

   nullptr -> Option A

4. Quick Check:

   Empty list insertion sets next to nullptr [OK]

Hint: New node next points to old head, which is nullptr here [OK]

Common Mistakes:

• Assuming head->next has data 10
• Thinking head->next is undefined or garbage
• Ignoring initial nullptr head

4. Identify the error in the following code snippet for inserting a node at the end of a doubly linked list:

struct Node {
  int data;
  Node* next;
  Node* prev;
};

void insertEnd(Node*& head, int val) {
  Node* newNode = new Node{val, nullptr, nullptr};
  if (head == nullptr) {
    head = newNode;
    return;
  }
  Node* temp = head;
  while (temp->next != nullptr) {
    temp = temp->next;
  }
  temp->next = newNode;
  newNode->prev = nullptr;
}

medium

A. temp should be initialized to nullptr.

B. head should be passed by value, not reference.

C. newNode->prev should point to temp, not nullptr.

D. newNode->next should point to head.

Solution

1. Step 1: Check newNode's prev pointer assignment

   After finding the last node (temp), newNode is added after temp, so newNode->prev must point to temp.

2. Step 2: Identify incorrect assignment

   Code sets newNode->prev = nullptr, which breaks backward link; it should be newNode->prev = temp.

3. Final Answer:

   newNode->prev should point to temp, not nullptr. -> Option C

4. Quick Check:

   Prev pointer links new node to last node [OK]

Hint: Prev of new node = last node before insertion [OK]

Common Mistakes:

• Setting newNode->prev to nullptr instead of last node
• Passing head by value losing list updates
• Incorrect initialization of temp pointer

5. You want to design a function to delete a node from a doubly linked list given a pointer to that node (not the head). Which pointer updates are necessary to maintain list integrity?

hard

A. No pointer updates needed; just delete the node.

B. Set node's prev->next to node's next and node's next->prev to node's prev.

C. Set node's prev to nullptr and node's next to nullptr only.

D. Set node's next->next to node's prev and node's prev->prev to node's next.

Solution

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

   To remove a node, the previous node's next pointer must skip the node and point to node's next.

2. Step 2: Update next node's prev pointer

   Similarly, the next node's prev pointer must skip the node and point to node's prev.

3. Final Answer:

   Set node's prev->next to node's next and node's next->prev to node's prev. -> Option B

4. Quick Check:

   Prev and next pointers bypass deleted node [OK]

Hint: Link prev and next nodes directly to remove node [OK]

Common Mistakes:

• Not updating both prev and next pointers
• Setting wrong pointers to nullptr
• Deleting node without fixing links