Convert Doubly Linked List to Array I solution and explanation
2 more videos on this problem
The problem
You are given the head of a doubly linked list, which contains nodes that have a next pointer and a previous pointer.
Return an integer array which contains the elements of the linked list in order.
Example 1:
Input: head = [1,2,3,4,3,2,1]
Output: [1,2,3,4,3,2,1]
Example 2:
Input: head = [2,2,2,2,2]
Output: [2,2,2,2,2]
Example 3:
Input: head = [3,2,3,2,3,2]
Output: [3,2,3,2,3,2]
Constraints:
- The number of nodes in the given list is in the range
[1, 50]. 1 <= Node.val <= 50
Approach overview
Problem Overview: Given the head of a doubly linked list, the task is to return an array containing the node values in the same order as they appear in the list. You start from the head node and follow the next pointers until the end, copying each value into an array.
Approach 1: Direct Traversal (O(n) time, O(n) space)
The most straightforward solution is to iterate through the doubly linked list starting from the head. At each node, append the node's value to a dynamic array (such as a Python list or Java ArrayList). Continue moving through the list using the next pointer until you reach null. This works because a doubly linked list preserves element order through its sequential node connections. The traversal touches every node exactly once, giving O(n) time complexity where n is the number of nodes. The array stores all values, so the extra space used is O(n). This approach is simple, readable, and the most common implementation in interviews.
Approach 2: Two-Pass Traversal with Preallocated Array (O(n) time, O(n) space)
Another option is to first walk through the list to count the number of nodes. Once you know the size, allocate an array of that exact length. Then perform a second traversal and fill the array sequentially with node values. This avoids dynamic resizing that some array implementations perform during repeated appends. The trade-off is an additional pass through the linked list. Time complexity remains O(n) since each node is visited twice, and space complexity stays O(n) for the resulting array.
Recommended for interviews: Direct traversal is the expected answer. Interviewers want to see that you understand how to iterate through a linked structure using pointers and convert it into a contiguous array representation. Mentioning the two-pass preallocation variant shows deeper awareness of memory behavior in dynamic arrays, but the single-pass append approach is typically preferred for its clarity and minimal code.
Solution
We can directly traverse the linked list, adding the values of the nodes to the answer array ans one by one.
After the traversal is complete, return the answer array ans.
The time complexity is O(n), where n is the length of the linked list. Ignoring the space consumption of the answer array, the space complexity is O(1).
"""
# Definition for a Node.
class Node:
def __init__(self, val, prev=None, next=None):
self.val = val
self.prev = prev
self.next = next
"""
class Solution:
def toArray(self, root: "Optional[Node]") -> List[int]:
ans = []
while root:
ans.append(root.val)
root = root.next
return ans/*
// Definition for a Node.
class Node {
public int val;
public Node prev;
public Node next;
};
*/
class Solution {
public int[] toArray(Node head) {
List<Integer> ans = new ArrayList<>();
for (; head != null; head = head.next) {
ans.add(head.val);
}
return ans.stream().mapToInt(i -> i).toArray();
}
}/**
* Definition for doubly-linked list.
* class Node {
* int val;
* Node* prev;
* Node* next;
* Node() : val(0), next(nullptr), prev(nullptr) {}
* Node(int x) : val(x), next(nullptr), prev(nullptr) {}
* Node(int x, Node *prev, Node *next) : val(x), next(next), prev(prev) {}
* };
*/
class Solution {
public:
vector<int> toArray(Node* head) {
vector<int> ans;
for (; head; head = head->next) {
ans.push_back(head->val);
}
return ans;
}
};/**
* Definition for _Node.
* class _Node {
* val: number
* prev: _Node | null
* next: _Node | null
*
* constructor(val?: number, prev? : _Node, next? : _Node) {
* this.val = (val===undefined ? 0 : val);
* this.prev = (prev===undefined ? null : prev);
* this.next = (next===undefined ? null : next);
* }
* }
*/
function toArray(head: _Node | null): number[] {
const ans: number[] = [];
for (; head; head = head.next) {
ans.push(head.val);
}
return ans;
}/**
* Definition for a Node.
* type Node struct {
* Val int
* Next *Node
* Prev *Node
* }
*/
func toArray(head *Node) (ans []int) {
for ; head != nil; head = head.Next {
ans = append(ans, head.Val)
}
return
}Complexity analysis
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Direct Traversal | O(n) | O(n) | Best general solution. Simple single pass through the list while appending values to an array. |
| Two-Pass Traversal with Preallocation | O(n) | O(n) | Useful when you want to allocate the exact array size before filling it. |
Frequently asked questions
Is Convert Doubly Linked List to Array I easy or hard?
Convert Doubly Linked List to Array I is considered an Easy problem. It mainly tests basic understanding of linked list traversal and how to transfer node values into a sequential array structure.
Convert Doubly Linked List to Array I Python/Java solution
The Python solution typically uses a list and appends values while traversing the nodes. In Java, an ArrayList is commonly used during traversal and then returned as an array if required. Both implementations follow the same O(n) traversal logic.
How to solve Convert Doubly Linked List to Array I in O(n)?
Traverse the list starting from the head and follow the next pointers until you reach the end. For every node visited, push its value into an array or list. Since each node is processed once, the algorithm runs in O(n) time with O(n) additional space.
What is the best approach for Convert Doubly Linked List to Array I?
Direct traversal is the best approach. Start from the head node and iterate through the doubly linked list using the next pointer, appending each node value to an array. This processes every node exactly once, resulting in O(n) time and O(n) space.
Is Convert Doubly Linked List to Array I asked at Google/Amazon/Meta?
Problems involving linked list traversal and conversions appear frequently in interviews at companies like Amazon, Google, and Meta. While this exact problem may vary, the underlying concept of iterating through linked list nodes and building another structure is a common interview pattern.
What data structure is used in Convert Doubly Linked List to Array I?
The problem involves two core data structures: a doubly linked list for the input and an array for the output. The algorithm simply walks through the linked list and copies each node value into the array in order.
What is the time complexity of Convert Doubly Linked List to Array I?
The optimal solution runs in O(n) time because each node in the doubly linked list is visited exactly once during traversal. The resulting array stores all node values, so the space complexity is O(n).