Tech cheat sheets - Lists & arrays

In Java, arrays and lists are an ordered collection of non-unique elements. They are probably one of the most common data structures you might have come across in your day-to-day programming.

Array vs List

In most cases, in Java you are more likely to use Lists over arrays - Lists provide more functionality as part of the API than the array does, so given the option, most people will use a list.

The two most common use cases for an array in java are:

1. An array of primitive types - Java generics only supports object references. Although Java autoboxing reduces the need for this, as you can still insert int type values into List<Integer> for example.
2. Micro optimization in performance critical systems

Most other cases, people generally use Lists, as the List interface offers more/convenient functionality, and also offers further control over type of List:

ArrayList

Array list is a simple array based implementation of the List interface.

Performance

add( T item ) - Adding a single element to an ArrayList using this add method will just add the element at the end of the list, which is very cheap - O(1)

add( T item, int index) - Adding a single element to an ArrayList at a specified position is less performant, as it needs to copy all elements to the right of the specified position, so this is more expensive and runs in linear time - O(n)

remove( T item ) - Similar to adding at a specified position, this is less performant  as it involves an array copy (plus, if we remove a specific Object rather than an item at a given position, it still potentially needs to access all items in the list). Again, linear time - O(n)

set/get( int index ) - This is very cheap in an arraylist, as it is just backed by an array, so can be looked up in constant O(1)

LinkedList

LinkedList in Java is a double linked list implementation of the List interface (e.g. every element in the list stores a pointer to the previous & next elements in the list - and these pointers are used to access/traverse the list).

Performance

add( T item ) - Adding a single element to a LinkedList using this add method will also just add the element at the end of the list same as the ArrayList, which is very cheap - O(1)

add( T item, int index) -Again, adding at a given position (** using this method!) is more expensive - Insertion in a linked list is cheap, as the pointers just need to be adjusted, however, you have to traverse the list to find the position, which puts you back into running in linear time - O(n)

remove( T item ) - Again, this method has the same performance/issues as the above add at position method, having to traverse the list to find the element to remove. So again, runs in linear time - O(n)

set/get( int index ) - As we need to traverse the list to find the position, it also needs to potentially traverse every element in the list, so runs at linear time O(n)


** As you will note from the above summary, ArrayList is better for get & set methods and equal performance for add remove methods. However, LinkedList does have the benefit of being able to use an Iterator to add/delete elements in constant O(1) time - e.g. if you are iterating a list and already at the position you wish to insert/delete then it is very cheap - see JavaDocs

Conclusion

By and large, for most simple List cases (not considering wanting to use Sets, Queues, Stacks etc) the most common choice is ArrayList as it offers, generally, the best performance.

If you know you need to have a very large list, and know that you will always be inserting new elements towards the head of the list, then LinkedList may be a better alternative - if you only ever insert at the start of a list, LinkedList will perform in constant O(1) time, where as ArrayList will perform O(n) time.

There are futher implementations of the List interface in Java, such as Stack, Vector.  I will look at some of those in different posts.