Create and Initialize Doubly Linked List in DSA Javascript - Build from Scratch

Create and Initialize Doubly Linked List

📖 Scenario: You are building a simple program to manage a playlist of songs. Each song should be connected to the previous and next song so you can easily move forward or backward in the list.

🎯 Goal: Create a doubly linked list with three songs. Each song node should have a title, a prev pointer to the previous song, and a next pointer to the next song.

📋 What You'll Learn

Create a class called Node with properties title, prev, and next.

Create three nodes with titles exactly 'Song A', 'Song B', and 'Song C'.

Link the nodes so that Song A points forward to Song B, Song B points back to Song A and forward to Song C, and Song C points back to Song B.

Create a variable called head that points to the first node (Song A).

Print the titles of the songs starting from head by following the next pointers.

💡 Why This Matters

🌍 Real World

Doubly linked lists are used in music players, browsers, and other apps where you need to move forward and backward through items easily.

💼 Career

Understanding doubly linked lists helps in software development roles that involve data structure manipulation, improving your problem-solving skills.

1

Create the Node class

Create a class called Node with a constructor that takes a title parameter and sets this.title. Also initialize this.prev and this.next to null.

DSA Javascript

// Your code here

Hint

Think of each song as a box that knows its name and has two empty slots for neighbors.

2

Create three song nodes

Create three variables called songA, songB, and songC that are new Node objects with titles 'Song A', 'Song B', and 'Song C' respectively.

DSA Javascript

class Node {
    constructor(title) {
        this.title = title;
        this.prev = null;
        this.next = null;
    }
}

// Your code here

Hint

Use the new keyword to create each song node with the exact titles.

3

Link the nodes to form the doubly linked list

Set songA.next to songB, songB.prev to songA, songB.next to songC, and songC.prev to songB.

DSA Javascript

class Node {
    constructor(title) {
        this.title = title;
        this.prev = null;
        this.next = null;
    }
}

const songA = new Node('Song A');
const songB = new Node('Song B');
const songC = new Node('Song C');

// Your code here

Hint

Connect each node's next and prev properties to link the songs forward and backward.

4

Set head and print the list titles

Create a variable called head that points to songA. Then use a while loop to print the title of each node starting from head and moving forward using the next pointer.

DSA Javascript

class Node {
    constructor(title) {
        this.title = title;
        this.prev = null;
        this.next = null;
    }
}

const songA = new Node('Song A');
const songB = new Node('Song B');
const songC = new Node('Song C');

songA.next = songB;
songB.prev = songA;
songB.next = songC;
songC.prev = songB;

// Your code here

Hint

Start from head and move forward using next until you reach the end (null).

Practice

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

easy

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

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

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

D. A doubly linked list does not use pointers at all.

Solution

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

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

2. Step 2: Compare with singly linked list

   Singly linked list nodes have only one pointer to the next node, so they cannot go backward.

3. Final Answer:

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

4. Quick Check:

   Doubly linked list = two pointers per node [OK]

Hint: Remember: doubly linked means two directions [OK]

Common Mistakes:

• Thinking doubly linked lists use arrays
• Believing doubly linked lists only go forward
• Confusing pointers with data storage

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

easy

A. class Node { constructor(data) { this.data = data; this.next = null; } }

B. class Node { constructor(data) { this.data = data; this.prev = null; this.next = null; } }

C. class Node { constructor(data) { this.data = data; this.left = null; this.right = null; } }

D. class Node { constructor(data) { this.value = data; this.next = null; } }

Solution

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

   A doubly linked list node needs both 'prev' and 'next' pointers initialized to null.

2. Step 2: Check constructor parameters and properties

   class Node { constructor(data) { this.data = data; this.prev = null; this.next = null; } } correctly defines 'data', 'prev', and 'next' properties in the constructor.

3. Final Answer:

   class Node { constructor(data) { this.data = data; this.prev = null; this.next = null; } } -> Option B

4. Quick Check:

   Node needs prev and next pointers [OK]

Hint: Doubly linked nodes have both prev and next [OK]

Common Mistakes:

• Omitting the prev pointer
• Using wrong pointer names like left/right
• Using different property names for data

3. What will be the output of the following code snippet?

class Node {
  constructor(data) {
    this.data = data;
    this.prev = null;
    this.next = null;
  }
}

class DoublyLinkedList {
  constructor() {
    this.head = null;
    this.tail = null;
  }
  append(data) {
    const newNode = new Node(data);
    if (!this.head) {
      this.head = newNode;
      this.tail = newNode;
    } else {
      this.tail.next = newNode;
      newNode.prev = this.tail;
      this.tail = newNode;
    }
  }
}

const list = new DoublyLinkedList();
list.append(1);
list.append(2);
list.append(3);

let current = list.head;
const result = [];
while (current) {
  result.push(current.data);
  current = current.next;
}
console.log(result);

medium

A. []

B. [3, 2, 1]

C. [null, null, null]

D. [1, 2, 3]

Solution

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

   Each append adds a new node at the tail, linking prev and next pointers correctly.

2. Step 2: Traverse from head to tail collecting data

   Starting at head (1), moving next collects 1, then 2, then 3, then stops at null.

3. Final Answer:

   [1, 2, 3] -> Option D

4. Quick Check:

   Traversal from head collects [1, 2, 3] [OK]

Hint: Traverse from head using next to get list order [OK]

Common Mistakes:

• Confusing traversal direction
• Not updating tail pointer on append
• Pushing null values instead of data

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

class Node {
  constructor(data) {
    this.data = data;
    this.prev = null;
    this.next = null;
  }
}

class DoublyLinkedList {
  constructor() {
    this.head = null;
    this.tail = null;
  }
  append(data) {
    const newNode = new Node(data);
    if (!this.head) {
      this.head = newNode;
      this.tail = newNode;
    } else {
      this.tail.next = newNode;
      this.tail.prev = newNode;
      this.tail = newNode;
    }
  }
}

medium

A. The constructor is missing initialization of head and tail.

B. The newNode should not have prev or next pointers.

C. The line 'this.tail.prev = newNode;' should be 'newNode.prev = this.tail;'.

D. The append method should not update the tail pointer.

Solution

1. Step 1: Analyze pointer updates in append method

   When adding newNode, the previous tail's next should point to newNode, and newNode's prev should point to old tail.

2. Step 2: Identify incorrect pointer assignment

   The code incorrectly sets 'this.tail.prev = newNode;' which wrongly changes the old tail's prev pointer instead of newNode's prev pointer.

3. Final Answer:

   The line 'this.tail.prev = newNode;' should be 'newNode.prev = this.tail;'. -> Option C

4. Quick Check:

   Correct prev pointer must link newNode to old tail [OK]

Hint: Prev pointer goes from new node back to old tail [OK]

Common Mistakes:

• Swapping prev and next pointers
• Not updating newNode.prev correctly
• Forgetting to update tail pointer

5. You want to create a doubly linked list from an array of values [10, 20, 30] and then traverse it backward from tail to head. Which code snippet correctly initializes the list and prints the values backward?

hard

A. const list = new DoublyLinkedList();
for (const val of [10, 20, 30]) list.append(val);
let current = list.tail;
while (current) { console.log(current.data); current = current.prev; }

B. const list = new DoublyLinkedList();
for (let i = 2; i >= 0; i--) list.append([10, 20, 30][i]);
let current = list.head;
while (current) { console.log(current.data); current = current.next; }

C. const list = new DoublyLinkedList();
for (const val of [10, 20, 30]) list.append(val);
let current = list.head;
while (current) { console.log(current.data); current = current.prev; }

D. const list = new DoublyLinkedList();
for (const val of [10, 20, 30]) list.append(val);
let current = list.tail;
while (current) { console.log(current.data); current = current.next; }

Solution

1. Step 1: Append values in order to the list

   Using a for-of loop appends 10, then 20, then 30, building the list head to tail.

2. Step 2: Traverse backward from tail using prev pointer

   Starting at tail (30), moving prev prints 30, 20, 10 in reverse order.

3. Final Answer:

   const list = new DoublyLinkedList(); for (const val of [10, 20, 30]) list.append(val); let current = list.tail; while (current) { console.log(current.data); current = current.prev; } -> Option A

4. Quick Check:

   Backward traversal uses tail and prev pointer [OK]

Hint: Traverse backward from tail using prev pointer [OK]

Common Mistakes:

• Traversing backward from head
• Using next pointer to go backward
• Appending values in reverse order but traversing forward