ArrayList

From CS315

Jump to: navigation, search

Contents

ArrayList

ArrayList is an array implementation of the List interface. ArrayList's main feature is that it is resizable and does not suffer from the limitations given by an array.

Methods

ArrayList implements all optional list operations and allows all elements (including null).

Basic Methods 

 get - Input: index  Output: returns element at given index in the internal array.
 set - Input: index and element Output: sets element to that position and returns what was formally at that position. 
 add - Input: element Output: adds to the end of the array, if full the array is resized.
 remove - Input: index Output: copies the rest of the array over location and returns the removed item
 size - Output: returns amount of items in the current list.

Runtime of Methods

  • O(1) : size, isEmpty, get, set, iterator, listIterator
  • O(N) : addAll, clone, clear, contains, indexOf, remove, ensureCapacity
  • Amortized O(1): add

ArrayList's add method is amortized constant time because, as the internal array is filled, it is expanded by a fixed proportion. Although this expansion takes O(N) time, it is amortized constant because over N insertions it takes O(N) time; so O(N) / N = O(1).

Benefits

  • Easy expansion.
  • Allows access to any element within it in constant time.
  • Usually has faster iteration compared to LinkedList because of the locality of the references.
  • Constant time deletion at the end of the list.

Drawbacks

  • Linear time for insertion or deletion into arbitrary location in list.
  • Amortized constant insertion instead of simply constant.

Java Implementation

  • Inherits mod count from AbstractList to prevent iterators from making changes

when the ArrayList is no longer in sync with the iterator's expected mod count.

  • ArrayList extends AbstractList and implements List, RandomAccess, Cloneable,

and Serializable.

  • When the internal array is filled, a new array is created with the size increased

by 3/2's. The elements of the former array are copied to this array and it is set as the interal storage container for the ArrayList.

  • The clear method goes through the list setting each element to null [ O(N) ]

instead of using AbstractCollection's clear which uses an iterator's remove method that results in O(N^2) time.

References


Written by Gilberto Cardenas

Retrieved from "http://z.cs.utexas.edu/users/downing/cs315/index.php/ArrayList"
Personal tools