Well, DSA is a kind of new world to me. I just used all library implementations and at times, I have even Ctrl+ Clicked to Java Collections like LinkedList and Array List Implementation.
I can’t say, I understood everything at whole. But still has some understanding on the topic.
I see both has their limitations. LinkedList uses at least one extra memory each node for addressing the next pointer. While Arraylist needs to copy all elements from one array to another for adding or removing elements.
Although, these days with lot of hardware optimizations like caching and SIMD, I get that ArrayList is faster. I have used with million entries in both, proving Arraylist quite faster in performance.
But back in 70s or even prior to that, when we didn’t have these good hardware performance optimizations, copying whole set of elements from one array to another would take some time.
My question is, why there is no popular data structure like, a linkedlist of arrays. Such that, when the structure needs to grow, just add a new pointer to a new node holding array of K elements. So, we would avoid copying all data from one array to another for growing. Also, we would not use too many pointers to new nodes. Kind of getting best of both worlds with some negligible performance cost.
I still get O(n/k) search time, if not O(1) and if I take a reasonably high K like k = 10000, still it would be reasonably fast even for billion data entries. But in that case, for resizing, we would save a whole lot on copying data from one array to another.
I am pretty sure, many geniuses have already thought of this approach and maybe they failed for some reason or some brainstorming could have proven this wrong, which at current knowledge of mine is not understandable by me.
So, is there a story on why this is not so common and we rely on Arraylist heavily these days?
4
What you’re referring to is similar to an “unrolled linked list” (Wikipedia ref). As you mentioned, search and iteration performance can be much better with an unrolled linked list since it’s more cache friendly.
As a hybrid solution between a linked list and an array list, it inherits some of the benefits, and some of the downsides of each implementation. For example, consider insertions in the middle of the list. Let’s say the “bucket” that you need to insert into is full. So, you push the last element of that bucket to the next one. But that bucket is also full. And the next bucket is full. Either you keep moving elements around until you reach a non-full bucket, or you end up with a non-empty bucket in the middle of the list, leading to fragmentation or wasted space. This is no better than an array list.
So in short, it’s situational. If you know you need fast random access and won’t need to resize the list often, then array list is probably better. If you know you’re going to be removing or inserting elements in the middle of then array often, then maybe a plain linked list is better. Considering that linked lists and array lists are sufficient for a lot of use cases, using unrolled linked lists may not be worth it (considering the fragmentation and code complexity introduced).
kirksaunders is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.
3