Java and collections:When to use a linked list of arrays?

Question

What would be the advantage of using a linked list of arrays?

I have read that if the data is large and insertions are allowed (for example, a text buffer), then a common halfway measure is to use a linked list of arrays .
But there was no explanation on what is the benefit of using such a structure.

Or at least I did not get it.

So what would be the gain in using a linked list of arrays and when?

• bezmax: Your question is weird. You use linked list of arrays when you need linked list of arrays. Sorry for sarcasm but you could also try asking about benefit of using HashSet of arrays or maybe Stream of arrays.
• Cratylus: I understand what you are saying.My problem is that this was mentioned in a material I am reading relating to performance and it mentioned this datastructure (at least this is how I understood it) as a "trick" between using a linkedlist which has slow access but fast insertions and deletions and an array which is exactly the opposite.I thought that may be this is a common "trick" I am not aware
• bezmax: For fast insertions, deletions and access we use ArrayList in Java. No need for any custom data structures unless you need it for some specific data which require that custom structure.
• TC1: @Max That's not entirely true, you should really check the javadoc again. ArrayList is the same as std::vector in C++, it's a pretty thin wrapper for an array, and if the insertion index exceeds the initially allocated size, the whole array gets realloced and copied. This is unnoticable for small amounts of data, but once you start reallocating and copying a few GBs, you get the gist... Hence the name Array List.
• Unai Vivi: @OP You mean a LinkedList of ArrayList, right? You don't want to mix up java collections with standard arrays, or do you?

Answer 1

With Linked list of arrays you can easily combine both the advantages of linked lists and static arrays.

Check this question.

Answer 2

I think it gives an ability to insert a new portion of data (quite big, might be) simply as a new array into a list, without touching existing arrays in the list which go after an inserting position.

Generally, inserting into a linked list is faster than inserting into an array, because it doesn't require shifting elements after new one. In case you described, the benefit should even more significant because you don't need to shift all subsequent data which is large (in average) by definition.

At the same time, we should take into account that access to such data structure is more complex and slower.

P.S. Also, if speed is really critical for you, firstly I would do a small investigation with comparison of existing real implementation of data structures (ArrayList, LinkedList, arrays, etc.).

Answer 3

When you'll need fast object obtaining from collection and you'll not be sure, that you have enough memory to allocate "whole" array (ArrayList implementation), you might write your own implementation which uses list of arrays to rapidly fast find the object you're looking for.

But there are definitely better data structures for this approach.

Answer 4

I can think of opposite situation: array of linked lists (actually hashmap) where every array element is a bucket that points to the list that can dynamically grow.Think of Dictionary that is being built and new words are added but the number of letters is constant.

Some example of what you describe can be a skip list based solution I can also think of some efficient hashing or implementing a dynamic queue of constant sets of batch jobs.

• Cratylus: I think this is the inverse of what I describe
• aviad: @user384706, the first paragraph is definitely the inverse of what you describe (it is clearly stated there). the 2-nd one is based on what you asked - list of arrays.

Answer 5

Think about this problem:

Imagine a (literal) stack of plates If the stack gets too high, it might topple There- fore, in real life, we would likely start a new stack when the previous stack exceeds some threshold Implement a data structure SetOfStacks that mimics this SetOf- Stacks should be composed of several stacks, and should create a new stack once the previous one exceeds capacity (Cracking Tech Code Interview)

Answer 6

No need to create custom data structure if unnecessarily. Beacause,as Linked List of Array, there's no difference between HashMap.

• Scratte: I thought the HashMap was an array of linked lists.. not a linked list of arrays.