How do I convert a Doubly Linked List to an Array in JavaScript?

Converting a doubly linked list to an array is a common task in various programming scenarios, especially when you need easier access to elements or want to perform array-specific operations. Understanding how to perform this conversion helps in optimizing your code and working efficiently with different data structures. Here, you'll find a clear explanation along with an example implementation in JavaScript.

What is a Doubly Linked List?

A doubly linked list is a data structure where each node contains three parts:

• The data or value stored at the node.
• A reference to the next node.
• A reference to the previous node.

This setup allows traversal in both forward and backward directions, unlike singly linked lists.

The Goal: Convert Doubly Linked List to Array

The main idea behind converting a doubly linked list to an array is to traverse the list from the head to the end and push each node's value into an array.

Step-by-Step Approach

1. Initialize an empty array
2. Start at the head of the doubly linked list
3. Loop through each node until reaching the end (null)
4. Push the node's value into the array
5. Move to the next node
6. Return the populated array

Example Implementation

Let's consider a simple implementation with a doubly linked list class and a function to convert it to an array:

1// Define the Node class
2class Node {
3  constructor(value) {
4    this.value = value;
5    this.next = null;
6    this.prev = null;
7  }
8}
9
10// Define the DoublyLinkedList class
11class DoublyLinkedList {
12  constructor() {
13    this.head = null;
14    this.tail = null;
15  }
16
17  // Method to add a node at the end
18  append(value) {
19    const newNode = new Node(value);
20    if (!this.head) {
21      this.head = newNode;
22      this.tail = newNode;
23    } else {
24      this.tail.next = newNode;
25      newNode.prev = this.tail;
26      this.tail = newNode;
27    }
28  }
29
30  // Method to convert list to array
31  toArray() {
32    const result = [];
33    let current = this.head;
34    while (current) {
35      result.push(current.value);
36      current = current.next;
37    }
38    return result;
39  }
40}

Usage Example

1const list = new DoublyLinkedList();
2list.append(10);
3list.append(20);
4list.append(30);
5
6const array = list.toArray();
7console.log(array); // Output: [10, 20, 30]

Explanation

• The append method adds new nodes to the end of the list, updating the next and prev pointers accordingly.
• The toArray method starts from the head and follows next pointers until it reaches null.
• During traversal, each node's value gets pushed into an array.
• Upon completion, the array contains all the values from the doubly linked list in order.

This approach ensures that the list is traversed exactly once, resulting in an efficient conversion process with a time complexity of O(n), where n is the number of elements in the list.

By following this pattern, you can convert a doubly linked list into an array in your own projects or during technical interviews, demonstrating your understanding of both data structures and algorithmic thinking.