Sean Hill Sean Hill - 1 year ago 43
Android Question

What data structure is used in apps for modifiable lists?

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?

Answer Source

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.

Both LinkedList and ArrayList allow duplicates.

Neither LinkedList nor ArrayList are thread-safe. So if accessing either from more than one thread, you have a whole other category of concerns to address.

To understand the nuances, study linked lists and arrays in general.