Skip to content

List In Java - Java Collections

List is an important data structure in Java, in my mind, it's an extending of array, which supports dynamic resize. On the other hand, a list also may waste some memory data, as it will grow half of current capacity when the used size reach the capacity.

The following diagram shows the hierachy of the Lists.

Kroki

The following table lists the comparastion of the Lists.

List Underlying Capacity Thread Safe Access Add/Delete
ArrayList Array Default: 10
Grow: Half of the current size		 No \(O(1)\) \(O(n)\)
Vector Array Default: 10
Grow: Current size or capacityIncrement		 Yes \(O(1)\) \(O(n)\)
Stack Array Default: 10
Grow: Current size or capacityIncrement		 Yes \(O(1)\) \(O(n)\)
LinkedList Linked list No \(O(n)\) \(O(1)\)
CopyOnWriteArrayList Array Default: 0
Grow: 1
Every add operation will create a new array with current size + 1, and copy the data, then assign to the internal array		 Yes \(O(1)\) \(O(n)\)

Array Based List

Array based list use an array to save the data, the difference between a list and an array is that list can automatically grow the underlying array if its element size reach its capacity.

  • add an element

    • if need grow the array, the time is \(O(n)\)

      It requires to create a new array, and copy the origin data to the new array

    • if no need to grow the array, the time is \(O(1)\)

  • insert an element

    As requires to move the elements, the time is \(O(n)\)

  • remove an element

    • if remove at the end, the time is \(O(1)\)
    • if remove requires to move elements, the time is \(O(n)\)

CopyOnWriteArrayList

CopyOnWriteArrayList is thread safe,

  • Write/modification to the list will accquire a lock, but

    it will always create a new array, and copy the data to the new array from the old array, as the write operation doesn't impact the old array, so access is not required the lock.

  • Access the list is no lock

LinkedList

LinkedList uses doubly-linked list as its underlying data structure, it has no limitation on the number of the elements to save, and it doesn't require a continous memory to save all the data.

  • add/insert an element

    • if add to the end of insert to the head, the time is \(O(1)\)

    • if add to other location, it needs to traverse the list, so the time is \(O(n)\)

  • remove an element

    • if remove at the end, the time is \(O(1)\)
    • if remove requires to traverse the list, the time is \(O(n)\)

How to choose which list to use?

  • If your program requires more random access to the list, you should consider using an array based list.
  • If your program requires more add/delete access to the list, you should consider using an linked list based.