This is just a short answer about the use of ArrayList. It is almost always a poor option, as it is pretty much an array with helper functions. If you have an ArrayList of 10000 integers, and then add another integer, ArrayList will (if its current array it's storing the values in is of size 10000) create a new array, move all the values of the old array in the new array, then add the integer to the end. Sounds inefficient? Certainly does.

My opinion is to use LinkedList. LinkedList is faster, because it works like this:

• Each value in the list is stored in a Node.
• Each Node points to the next Node.
• Adding something to the end is as simple as creating a new Node and linking it to the Node chain.
• Removing and inserting is as simple as changing some links around.

Worst-case time complexity comparison:

        LinkedList        ArrayList
Get:       O(n)              O(1)
Add:       O(n)              O(n)
Insert:    O(n)              O(n)

Yes, LinkedList is losing, but in this case, you don't use get often. On the other hand, memory is an issue for ArrayList:

        LinkedList        ArrayList
Get:       O(1)              O(1)
Add:       O(1)              O(n)
Insert:    O(1)              O(n)

This is just a short answer about the use of ArrayList. It is almost always a poor option, as it is pretty much an array with helper functions. If you have an ArrayList of 10000 integers, and then add another integer, ArrayList will (if its current array it's storing the values in is of size 10000) create a new array, move all the values of the old array in the new array, then add the integer to the end. Sounds inefficient? Certainly does.

My opinion is to use LinkedList. LinkedList is faster, because it works like this:

• Each value in the list is stored in a Node.
• Each Node points to the next Node.
• Adding something to the end is as simple as creating a new Node and linking it to the Node chain.
• Removing and inserting is as simple as changing some links around.

Worst-case time complexity comparison:

        LinkedList        ArrayList
Get:       O(n)              O(1)
Add:       O(n)              O(n)
Insert:    O(n)              O(n)

Best-case time complexity comparison:

        LinkedList        ArrayList
Get:       O(1)              O(1)
Add:       O(1)              O(1)
Insert:    O(1)              O(n) <- assuming not inserting at end of list

Yes, LinkedList is losing, but in this case, you don't use get often. On the other hand, memory is an issue for ArrayList:

        LinkedList        ArrayList
Get:       O(1)              O(1)
Add:       O(1)              O(n)
Insert:    O(1)              O(n)