Skip to main content

List

Arrays vs ArrayListsโ€‹

FeatureArrayArrayList
primitives types supportedYesNo
indexedYesYes
ordered by indexYesYes
duplicates allowedYesYes
nulls allowedYes, for non-primitive typesYes
resizableNoYes
mutableYesYes
inherits from java.util.ObjectYesYes
implements List interfaceNoYes

Instantiating with Valuesโ€‹

import java.util.ArrayList;
import java.util.List;

// ...
ArrayList<String> arrayList = new ArrayList<>(List.of("first", "second", "third"));
// ...

Element informationโ€‹

Accessing Array Element dataAccessing ArrayList Element data
ExampleString[] array = {"first", "second", "third"}ArrayList<String> arrayList = new ArrayList<>(List.of("first", "second", "third"));
Index value of first element00
Index value of last elementarray.length - 1arrayList.size() - 1
Retrieving number of elements:array.length;arrayList.size();
Setting (assigning an element)array[0] = "one";arrayList.set(0, "one");
Getting an elementarray[0];arrayList.get(0);

Finding an elementโ€‹

ArrayArrayList
int binarySearch(array, element)
Array MUST BE SORTED
Not guaranteed to return index of first element if there are duplicates
boolean contains(element)
boolean containsAll(list of elements)
int indexOf(element)
int lastIndexOf(element)

Sortingโ€‹

Arrayโ€‹

String[] array = {"first", "second", "third"};
Arrays.

sort(array);
note

You can only sort arrays of elements that implement Comparable

ArrayListโ€‹

ArrayList<String> arrayList = new ArrayList<>(List.of("first", "second", "third"));
arrayList.

sort(Comparator.naturalOrder());
arrayList.

sort(Comparator.reverseOrder());
note

You can use the sort method with static factory methods to get Comparators

Creating Lists from Arraysโ€‹

Using Arrays.asList()โ€‹

Returned List is NOT resizeable, but is mutable

String[] days = new String[]{"Sunday", "Monday", "Tuesday"};
List<String> newList = Arrays.asList(days);

Using List.of()โ€‹

Returned List is IMMUTABLE

String[] days = new String[]{"Sunday", "Monday", "Tuesday"};
List<String> newList = List.of(days);

Creating Arrays from ArrayListsโ€‹

ArrayList<String> stringList = new ArrayList<>(List.of("Jan", "Feb", "Mar"));
String[] stringArray = stringList.toArray(new String[0]);
  • If the length of the array you pass, has more elements than the list, extra elements will be filled with the default values for that type
  • If the length of the array you pass, has fewer elements than the list, the method will still return an array, with the same number of elements in it, as the list

Listโ€‹

  • There are two general-purpose List implementations โ€” ArrayList and LinkedList

ArrayList operationsโ€‹

OperationWorst CaseBest Case
add()O(1)*
add(int index, E element)O(n)O(1)*
contains(E element)O(n)O(1)
get(int index)O(1)
indexOf(E Element)O(n)O(1)
remove(int index)O(n)O(1)
remove(E element)O(n)
set(int index, E element)O(1)

LinkedList operationsโ€‹

OperationWorst CaseBest Case
add()O(1)
add(int index, E element)O(n)O(1)
contains(E element)O(n)O(1)
get(int index)O(1)O(1)
indexOf(E Element)O(n)O(1)
remove(int index)O(n)O(1)
remove(E element)O(n)O(1)
set(int index, E element)O(1)O(1)
note

O(1) - constant time - operation's cost (time) should be constant regardless of number of elements

O(n) - linear time - operation's cost (time) will increase linearly with the number of elements n

O(1)* - constant amortized time - somewhere between O(1) and O(n), but closer to O(1) as efficiencies are gained

ArrayListโ€‹

Bottlenecksโ€‹

Either of these operations can be expensive

  • When removing an element, the referenced addresses have to be re-indexed, or shifted, to remove an empty space
  • When adding an element, the array that backs the ArrayList might be too small, and might need to be reallocated (with the copying of the previous array under the hood)

Benefitsโ€‹

  • Our objects aren't stored contiguously in memory, but their addresses are, in the array behind the ArrayList. The addresses can be easily retrieved with a bit of math, if we know the index of the element

LinkedListโ€‹

  • The LinkedList is not indexed at all
  • Each element that's added to a linked list, forms a chain
  • Can also be considered a queue, a double ended queue, because we can traverse both backwards and forwards

Bottlenecksโ€‹

  • Retrieval of an Element costs more than an ArrayList retrieval (because the index isn't stored as part of the list)
  • The element still needs to be found, using the traversal mechanism, which is why deletion and insertion is O(n)

Benefitsโ€‹

  • Inserting and removing an element, is much simpler than with ArrayList (just a matter of breaking two links in the chain, and re-establishing two different links)

  • Reallocation of memory to accommodate all existing elements, is never required

Advice from Timโ€‹

  • The ArrayList is usually the better default choice for a List, especially if the List is used predominantly for storing and reading data
  • If you know the maximum number of possible items, then it's probably better to use an ArrayList, but set its capacity
note

ArrayList's index is an int type, so an ArrayList's capacity is limited to the maximum number of elements an int can hold, Integer.MAX_VALUE = 2,147,483,647

  • Consider using a LinkedList if you're adding and processing or manipulating a large amount of elements, and the maximum elements isn't known, but may be great, or if your number of elements may exceed Integer.MAX_VALUE.
  • A LinkedList can be more efficient, when items are being processed predominantly from either the head or tail of the list

LinkedList's the Queue and Stack methodsโ€‹

note

Queue is a First-In, First-Out (FIFO) -> Offer (Insert) / Poll (Remove)

Stack is a Last-In, First-Out (LIFO) -> Push (Insert) / Pop (Remove)

Iteratorโ€‹

Iterator contains two main methods: hasNext() & next()

note

When an iterator is created, its cursor position is pointed at a position before the first element

The first call to the next method gets the first element, and moves the cursor position, to be between the first and second elements

When hasNext() = false the iterator or cursor position is past the last element

Iterator vs ListIteratorโ€‹

  • An Iterator is forwards only, and only supports the remove method
  • ListIterator can be used to go both forwards and backwards, and in addition to the remove method, it also supports the add and set methods
note

It's really important to understand that the iterator's cursor positions, are between the elements

Why does Java have primitive data types?โ€‹

  • Primitive types generally represent the way data is stored on an operating system
  • Primitives have some advantages over objects, especially as the magnitude, or number of elements increase
  • Objects take up additional memory, and may require a bit more processing power
note

Local primitive variables and references to object (i.e. variable declared in method) are stored in stack. Others are stored in heap

Boxingโ€‹

We need to box primitives into appropriate objects to pass them as generic types

Wrapper Classes
Boolean
Byte
Character
Double
Float
Integer
Long
Short
  • Each wrapper has a static overloaded factory method, valueOf()

Autoboxingโ€‹

We can simply assign a primitive to a wrapper variable

Integer boxedInt = 15;

Automatic unboxingโ€‹

We can assign an instance of a wrapper class, directly to a primitive variable

Integer boxedInt = 15;
int unboxedInt = boxedInt;

Enumerationโ€‹

enum : special data type that contains predefined constants

public enum DayOfWeek {
SUNDAY, MONDAY, TUESDAY, WEDNESDAY, THURSDAY, FRIDAY, SATURDAY
}