1
$\begingroup$

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?

$\endgroup$
1
  • $\begingroup$ (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))) $\endgroup$
    – greybeard
    Jun 14 at 10:32
1
$\begingroup$

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.

$\endgroup$
0
$\begingroup$

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
 ptr = &head
 arr[i] = head->data
 head = head->next
 free(ptr)
 i++ until i = length of list
 
$\endgroup$
2
  • $\begingroup$ yes, you are correct. The order does not matter. My question was actually if I should create an empty list and append each item or create a list with the length of the Linked List and insert each item when moving through the Linked List $\endgroup$
    – Kinyx
    Jun 13 at 15:47
  • $\begingroup$ yes, that's what comes to my mind. But to make it more memory-friendly, make sure you keep freeing up the nodes as you are done copying the data. :) $\endgroup$ Jun 13 at 15:49

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.