Doubly Linked List Structure and Node Design in DSA C++ - Build from Scratch

Doubly Linked List Structure and Node Design

📖 Scenario: Imagine you are building a simple music playlist app. Each song can be played forward or backward, so you need a structure that allows moving in both directions easily.

🎯 Goal: You will create a basic doubly linked list structure with nodes that hold song names. This will help you understand how nodes connect forward and backward.

📋 What You'll Learn

Create a Node class with string data, Node* next, and Node* prev members

Create a DoublyLinkedList class with a Node* head pointer

Initialize the list with one node containing the song name "Song1"

Set the next and prev pointers of the node to nullptr

💡 Why This Matters

🌍 Real World

Doubly linked lists are used in music players, browsers (back and forward buttons), and many applications where you need to move in both directions through data.

💼 Career

Understanding doubly linked lists is fundamental for software developers working with data structures, improving problem-solving skills and preparing for technical interviews.

1

Create the Node class

Create a Node class with a public string data member, and two public pointers: Node* next and Node* prev. Add a constructor that takes a string parameter called songName and sets data to it, and initializes next and prev to nullptr.

DSA C++

// Define the Node class with data, next, and prev
// Your code here

Hint

Remember to include string and pointer members for next and prev. Initialize pointers to nullptr in the constructor.

2

Create the DoublyLinkedList class with head pointer

Create a DoublyLinkedList class with a public pointer Node* head. Add a constructor that initializes head to nullptr.

DSA C++

// Define the DoublyLinkedList class with a head pointer
// Your code here

Hint

Make sure the head pointer is public and set to nullptr in the constructor.

3

Initialize the list with one node

Inside the DoublyLinkedList class, add a public method void initialize() that creates a new Node with data "Song1" and sets head to point to this new node.

DSA C++

#include 
#include 
using namespace std;

class Node {
public:
    string data;
    Node* next;
    Node* prev;

    Node(string songName) {
        data = songName;
        next = nullptr;
        prev = nullptr;
    }
};

class DoublyLinkedList {
public:
    Node* head;

    DoublyLinkedList() {
        head = nullptr;
    }

    // Add initialize method here
    // Your code here
};

Hint

Create a method called initialize that sets head to a new Node with "Song1".

4

Print the list starting from head

In the main() function, create a DoublyLinkedList object called playlist. Call playlist.initialize(). Then print the data of the head node using cout.

DSA C++

#include 
#include 
using namespace std;

class Node {
public:
    string data;
    Node* next;
    Node* prev;

    Node(string songName) {
        data = songName;
        next = nullptr;
        prev = nullptr;
    }
};

class DoublyLinkedList {
public:
    Node* head;

    DoublyLinkedList() {
        head = nullptr;
    }

    void initialize() {
        head = new Node("Song1");
    }
};

int main() {
    // Create playlist and initialize
    // Print the data of head node
    // Your code here
}

Hint

Create the playlist object, call initialize(), then print playlist.head->data.

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