Not so long ago, I thought. that there is no excuse for using java.util.LinkedList as a java.util.List implementation. But something made me look for him. Let's see. Any competent Java specialist knows that java.util.ArrayList should be used when we need fast access by index, and java.util.LinkedList if we need to insert or delete items in the middle of the list. Not many of them guess that if we insert or delete elements in the middle of the list with the remove(int index) and add(int index, E element) methods, then searching for the desired element will take an average time proportional to the size of the O(N) list. . So when does the java.util.LinkedList benefit come about?

When using iterators. More precisely, when you delete or insert elements through java.util.ListIterator . In the end, in search of justification, I found a very real example of code in which java.util.LinkedList gives a significant advantage over java.util.ArrayList . This is the simplest filtering algorithm that removes all elements from the list that do not satisfy the specified condition.

 for (Iterator<E> i = list.iterator(); i.hasNext(); ) { E val = i.next(); if (!condition(val)) { i.remove(); } } 

The same code can be easily rewritten using an additional list, and then the algorithm with java.util.ArrayList , at least, will not have a quadratic dependence on the original size.
')

 List<E> list1 = new ArrayList<E>(); for (Iterator<E> i = list.iterator(); i.hasNext(); ) { E val = i.next(); if (condition(val)) { list1.add(val); } } list.clear(); list.addAll(list1); 

But it is not correct that the data structures dictate the algorithm to us. But it was this algorithm that suggested me how to create a list that most operations will perform in O(1) .

To do this, we need an assumption: “The insert and delete operations occur side by side.” Of course, we can imagine a situation in which the insert and delete operations will occur randomly, but in this case neither java.util.ArrayList nor java.util.ArrayList will save us java.util.LinkedList that we fight. After all, to add or remove an arbitrary java.util.ArrayList element should generally shift the number of elements in the array proportional to the size of O (N), and java.util.LinkedList should find it O(N) .

The idea is as follows. The list is not stored in one array, but in 2x. Moreover, each array can accommodate it entirely.



When you insert an item in the middle of the list, we insert it into the gap. But after all, we may want to insert the element in the wrong place where separation occurs. To do this, we move part of the elements so that the gap moves to the right place.



You will say: “Yes, we moved fewer elements than in the case of java.util.ArrayList , but it is still proportional to the size of the list.” You are right, but if we recall our assumption, then each time, except for the first, we will move insignificant number of elements.

The same thing happens when you delete. The gap is shifted to the place where the item was removed.

I quickly wrote the implementation of this list. And he ran the tests: filling, sequential scanning, scanning by index, filtering, deleting the entire list from the head by one element. Since the results vary greatly for different lists, it is quite difficult to visualize them. So just show the table. Charts will be, but later. The tables show the time to perform various tasks on different volumes in milliseconds.

ArrayList

size	fill	sequence	index	filtration	remove first
20,000	0	0	0	94	47
40,000	0	0	0	406	187
60,000	sixteen	0	0	891	437
80,000	0	0	0	1578	782
100,000	0	15	0	2453	1219
120,000	sixteen	0	15	3516	1750
140,000	sixteen	0	0	4796	2391
160,000	sixteen	0	15	6219	3125
180000	sixteen	0	15	7969	3984
200,000	63	0	0	9859	4844

As you can see from the table, java.util.ArrayList does an excellent job with filling and any scan, and filtering and even deleting the list from the head suffers a crushing defeat.

Linkedlist

size	fill	sequence	index	filtration	remove first
20,000	0	0	406	0	0
40,000	31	0	1985	0	0
60,000	15	0	3828	sixteen	0
80,000	0	0	8359	0	0
100,000	sixteen	0	24891	0	15
120,000	sixteen	0	43562	sixteen	0
140,000	sixteen	15	52985	0	15
160,000	sixteen	0	57047	15	0
180000	79	0	121531	0	15
200,000	32	15	152250	sixteen	sixteen

The weak point of java.util.LinkedList is access by index, but the filtering operation is performed much faster.

DoubleArrayList

size	fill	sequence	index	filtration	remove first
20,000	0	0	0	0	0
40,000	sixteen	0	0	0	0
60,000	0	0	0	15	0
80,000	0	0	sixteen	0	0
100,000	sixteen	0	0	15	0
120,000	sixteen	0	0	15	0
140,000	sixteen	sixteen	0	15	0
160,000	sixteen	sixteen	0	15	0
180000	47	sixteen	0	15	0
200,000	32	0	15	0	sixteen

And finally, my implementation of org.kefirsf.list.DoubleArrayList does not sink on any of the tests.

Let's compare with LinkedList on large volumes.

Filling

Filtration

Head removal

From all these graphs, it can be seen that in various operations, DoubleArrayList works for a time comparable to java.util.LinkedList . Even if not always better. The main thing is that there is no quadratic dependence on the size of the array, and all operations are performed in O(N) , which means that single operations on average are performed in O(1) . Thus, the goal is achieved.

The org.kefirsf.list.DoubleArrayList code is available on GitHub: github.com/kefirfromperm/multi-array-list
Caution: do not try to use it in industrial development. org.kefirsf.list.DoubleArrayList still not well covered with tests, its use can lead to memory leaks.