In some apps you have lists of items where you can move items around, delete items, add or insert items, etc.
Normally I'd say an ArrayList would work but apparently a lot of operations are linear time.
Is there a better data structure most people use for this?
If your priority is inserting and/or removing elements from a collection that maintains an arbitrary order, the the
LinkedList class bundled with Java meets that need. You can very quickly insert or remove any element at any specific index number.
Each link in the chain that is a doubly-linked-list knows its predecessor and its successor. Each element holds a reference/pointer to the element in front and another reference/pointer to the one following. So insertion means telling a linked pair to consider the new element as their successor or predecessor. The rest of the chain remains untouched.
The downside to
LinkedList is that access by index number is expensive as finding the nth element means traversing n links going from one element to the next in the chain. A linked-list inherently means sequential access. So, getting to an element is expensive but once there the mechanics of the insertion/deletion is cheap.
Another downside to
LinkedList is searching, for similar reason (sequential access). Since the ordering is arbitrary and not sorted, there is no way to approximately predict/expect where the element might be found. So searching means traversing the chain from one element to the next and performing a comparison on each one.
On the other hand, if indexed access is your priority, then
ArrayList is the way to go. Directly accessing the nth element is the speciality for
ArrayList. Inserting and removing elements are very expensive operations requiring the backing array to be rebuilt unless dealing with the last element. For large arrays this has implications for memory management as the array must be in contiguous memory.
ArrayList allow duplicates.
ArrayList are thread-safe. So if accessing either from more than one thread, you have a whole other category of concerns to address.