- Forum
- General C++ Programming
- What is faster dynamic arrays or linked
What is faster dynamic arrays or linked lists
Let's say I want to retrieve some data structure inside a linked list I would have to do something along these lines:
short num = 500;
while(node != NULL){
if(node->num == num) break;
node = node->n;
}
If i was using a dynamic array to hold the data structures instead of wasting processing power to loop through all the structures I could just go:
node = node_list[500];
Which would be faster? I'm pretty sure the dynamic array would be faster but is there any way to test this?
short num = 500;
while(node != NULL){
if(node->num == num) break;
node = node->n;
}
If i was using a dynamic array to hold the data structures instead of wasting processing power to loop through all the structures I could just go:
node = node_list[500];
Which would be faster? I'm pretty sure the dynamic array would be faster but is there any way to test this?
You are correct. Accessing an index in the dynamic array takes O(1) time complexity. Which basically means it takes constant time, dependent on how fast the computer can access the data. On there other hand, to access a specific node in a linked list you must loop through the entire list, which take O(N) time. N represents how many inputs you have.
Obviously dynamic arrays are better for this application. But Linked lists are better for others, such as inserting or removing at any point in the list.
This is why it is important to understand what sort of operations will be run on a set of data and choose the best data structure to represent that in a program.
Obviously dynamic arrays are better for this application. But Linked lists are better for others, such as inserting or removing at any point in the list.
This is why it is important to understand what sort of operations will be run on a set of data and choose the best data structure to represent that in a program.
Hi,
> What is faster dynamic arrays or linked lists?
Dynamic arrays.
Dynamic arrays are definitely faster.
> What is faster dynamic arrays or linked lists?
Dynamic arrays.
Dynamic arrays are definitely faster.
> Is there any way to test this?
Using <chrono> or clock_t.
Test this with a very large number of objects (say, one hundred million objects) and see the results.
Using <chrono> or clock_t.
Test this with a very large number of objects (say, one hundred million objects) and see the results.
Thank you so much for your insightful replies
"Obviously dynamic arrays are better for this application. But Linked lists are better for others, such as inserting or removing at any point in the list."
I want to share that even though common manipulation of data mainly includes addition, subtraction, movement and retrieval. I have been coding in C for about a year now and from my experience retrieval of data dominates the main while loop so to speak. And if you think about it, dynamic arrays actually overtake linked lists in performance when it comes to addition and subtraction as the size of of the list increases.
With regards to rearranging the node positions for linked lists first you need "n" cycles to find the hooks which hold old and new data and then hook up at least 8 pointers assuming this is a doubly linked list and both the nodes are somewhere in the middle. Where as with a dynamic array you just need
0(2) time complexity and 3 pointer hook ups.
There is also the benefit of having to use 8 bytes less per data structure since you don't need the left and right pointers. I know these things seem really small but I think they add up, or maybe I'm just a hobbyist and I care too much about my code.
Call me biased but I think dynamic arrays outweigh linked lists regardless of the routines being performed.
"Obviously dynamic arrays are better for this application. But Linked lists are better for others, such as inserting or removing at any point in the list."
I want to share that even though common manipulation of data mainly includes addition, subtraction, movement and retrieval. I have been coding in C for about a year now and from my experience retrieval of data dominates the main while loop so to speak. And if you think about it, dynamic arrays actually overtake linked lists in performance when it comes to addition and subtraction as the size of of the list increases.
With regards to rearranging the node positions for linked lists first you need "n" cycles to find the hooks which hold old and new data and then hook up at least 8 pointers assuming this is a doubly linked list and both the nodes are somewhere in the middle. Where as with a dynamic array you just need
0(2) time complexity and 3 pointer hook ups.
There is also the benefit of having to use 8 bytes less per data structure since you don't need the left and right pointers. I know these things seem really small but I think they add up, or maybe I'm just a hobbyist and I care too much about my code.
Call me biased but I think dynamic arrays outweigh linked lists regardless of the routines being performed.
Is it possible to "memcpy" an array of pointers on to a second array or move without having to loop through them one by one.
To take this further is it possible to "shift" multiple pointers on an array eg:
[a][b][c][0]
[0][a][b][c]
To take this further is it possible to "shift" multiple pointers on an array eg:
[a][b][c][0]
[0][a][b][c]
Topic archived. No new replies allowed.