Posts by Dat Hoang

04
Aug
featured image

Performance of array vs linked-list on modern computers

posted on Friday August 4th, 2017 / 0 Comments

Few notes The array mentioned here is automatically-reallocated array (vector in C++, ArrayList in Java or List in C#). The benchmark graph between vector & list I showed in this post belongs to "Baptiste Wicht" in http://baptiste-wicht.com/posts/2012/12/cpp-benchmark-vector-list-deque.html (Thanks for saving my time for the benchmarking stuff). From theory People say Linked-list has much better performance than array when it comes to random-insertion & random-deletion. That's what we've learn in theory, too. And I've seen many people around the internet suggest to use linked-list when we need to do a lots of random-insertion & random-deletion. To practice "How could it be?" "Impossible!" Note: The "list" above is implemented as doubly linked-list in C++. And the …

more