Convert Doubly Linked List to Array I - Solution & Explanation

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.