# Return Linked List elements as an array

Out of pure curiosity, if I have a Doubly Linked List, what would be the fastest way to return the elemenmts of the List in the correct order as an array? For example, would it be more efficient to create an empty list an append the elements or create a list with the length of the Linked List and insert each element?

• (Linked List elements as an array & create an empty list [and] append: thinking in Python? What is, what is not an array? (If Linked_List was iterable, just use it as a parameter in instantiation: list(Linked_List))) Jun 14 at 10:32

In terms of computational complexity, both approaches will be $$O(n)$$. Also, its impossible to do better than $$O(n)$$, since you must always go through all elements in the linked-list anyways.

So in those terms, the running times are equivalent. What about the space (memory) complexity? Well, in both cases we ultimately create an array of length $$n$$ and nothing more than it. So, both approaches will have also $$O(n)$$ memory complexity.

What is the difference then? The key difference is not in any complexity measure, but it has to do with how memory is allocated. In the second approach, you have to create an array with some constant size, and you wont change that size. Hence, you will allocate memory only once. In the first approach, you create a (dynamic) list, which uses a less-efficient data structure (when compared to an array with a constant size) that can increase in size. Additionally, since this array increases in size it means that it will allocate memory more than once.

So ultimately, what do you want to use? the second implementation would be a better option - even though it doesn't improve in asymptotic complexity measures.

Since you haven't mentioned if the elements have to be sorted into an array, I am assuming you just want to copy the elements of the list into an array.

Well, this can be done by pointing to the head and copying the data of the head (head->data) into the array one by one and deallocating the node and moving on to the next node, and repeat.

Pseudo-code:

 i = 0