Performance differences between GlueList vs ArrayList vs LinkedList

Question

I know that there are lots of topics about list performance comparison.i can assure you this is NOT duplicate one.

I found new data structure called GlueList and it made me think.

I'm confused about list data-structures (GlueList , ArrayList and LinkedList).

How to choose one of them for given tasks.

For me personally, it's rarely worth the effort to try to force a new third-party product through the Technology Architecture Board approval process, so I would stick with the core Java classes in virtually every case. — azurefrog, Dec 11 '15 at 15:56

score 1 · Answer 1 · answered Dec 11 '15 at 16:01

GlueList

* "a" number of created nodes. "b" size of node array. *

get(int index) is O(1) ~ O(a)

add(E element) is O(1) ~ O(a*b)

add(int index, E element) is O(1) ~ O(a*b)

remove(int index) is O(1) ~ O(a*b)

Iterator.remove() is O(1) ~ O(a*b)

ListIterator.add(E element) is O(1) ~ O(a*b)

LinkedList

get(int index) is O(n)

add(E element) is O(1)

add(int index, E element) is O(n)

remove(int index) is O(n)

Iterator.remove() is O(1)

ListIterator.add(E element) is O(1)

ArrayList

get(int index) is O(1)

add(E element) is O(1) amortized, but O(n) worst-case since the array must be resized and copied

add(int index, E element) is O(n - index) amortized, but O(n) worst-case (as above)

remove(int index) is O(n - index) (i.e. removing last is O(1))

1 Answers1