I am well versed with pros and cons of ArrayList and LinkedList. ArrayList is preferred for random access, when additions and removals are less, and vice versa. What if I need a data structure where I need to do both random access, and need to add & remove items from the list often?
Which one to choose?
These data structures are API-compatible, just benchmark/profile your code with both.
Another hint: with ArrayList assume you perform N lookups and N mutations. This totals to O(N) + O(N * N) <=> O(N^2) complexity. With LinkedList you'll get O(N*N) + O(N) <=> O(N^2) (linear lookup times N + constant time mutation times N). So both data structures are comparable.
If you are willing to go a little bit deeper into the rabbit hole, scala.collection.immutable.Vector has amortized constant cost of both lookup and insertions/removal. And it's immutable, thus thread-safe! It's achieved using some sophisticated data structures underneath.
if you want Random Access go for ArrayList, you can use it as a normal list and add/remove items.
The memory for an ArrayList is allocated in blocks, which can run out of memory until and unless your ArrayList grows huge.
Since you have not mentioned whether you are having any memory constraints(only constraint is random access), I would say that ArrayList should meet all your needs.
I am well versed with pros and cons of ArrayList and LinkedList. ArrayList is preferred for random access, when additions and removals are less, and vice versa. What if I need a data structure where I need to do both random access, and need to add & remove items from the list often?
Which one to choose?
These data structures are API-compatible, just benchmark/profile your code with both.
Another hint: with ArrayList assume you perform N lookups and N mutations. This totals to O(N) + O(N * N) <=> O(N^2) complexity. With LinkedList you'll get O(N*N) + O(N) <=> O(N^2) (linear lookup times N + constant time mutation times N). So both data structures are comparable.
If you are willing to go a little bit deeper into the rabbit hole, scala.collection.immutable.Vector has amortized constant cost of both lookup and insertions/removal. And it's immutable, thus thread-safe! It's achieved using some sophisticated data structures underneath.
if you want Random Access go for ArrayList, you can use it as a normal list and add/remove items.
The memory for an ArrayList is allocated in blocks, which can run out of memory until and unless your ArrayList grows huge.
Since you have not mentioned whether you are having any memory constraints(only constraint is random access), I would say that ArrayList should meet all your needs.
0 commentaires:
Enregistrer un commentaire