CS61B Guide
  • This site is now deprecated
  • Object Oriented Programming
    • Inheritance
    • Access Control
    • Dynamic Method Selection
    • Java Objects
    • Generic Types
  • Asymptotics
    • Asymptotic Analysis Basics
    • Amortization
    • Asymptotics Practice
  • Abstract Data Types
    • Collections
      • Arrays
      • Linked Lists
      • Sets
      • Stacks and Queues
    • Binary Trees
      • Heaps
      • Balanced BSTs
      • Tries
    • Graphs
    • Hashing and Hash Tables
    • Union Find (Disjoint Sets)
    • Comparables and Comparators
  • Sorting
    • Sorting
  • Algorithms
    • Minimax Algorithm
    • Searching
      • Binary Search
      • Depth First Search (DFS)
      • Breadth First Search (BFS)
    • Shortest Paths
      • Dijkstra's Algorithm
      • A* Search
    • Minimum Spanning Trees
      • Prim's Algorithm
      • Kruskal's Algorithm
  • Misc Topics
    • Modular Arithmetic and Bit Manipulation
    • Exceptions
    • More Resources
Powered by GitBook
On this page
  • Properties
  • Using Arrays in Java
  • Array Lists

Was this helpful?

  1. Abstract Data Types
  2. Collections

Arrays

PreviousCollectionsNextLinked Lists

Last updated 5 years ago

Was this helpful?

This page assumes prior knowledge of Python lists from CS61A or equivalent.

Arrays are a very popular data structure that stores an indexed list of data.

Properties

  • Fixed length: after instantiation, the length of an array cannot be changed.

  • Every value in array is the same type and holds the same amount of bits in memory.

  • Zero-indexed. That means arr[0] returns the first value, and arr[arr.length] is out of bounds.

  • No methods. Helper methods from other libraries (like System.arraycopy) need to be used to manipulate arrays.

  • Retrieval is independent of size and takes constant time regardless of how big arrays are.

Using Arrays in Java

Instantiation:

  • int[] a = {1, 2, 3, 4, 5}; assigns values.

  • int b = new int[3]; creates array of provided length populated with default values.

Copying

  • Use System.arraycopy(source, start, target, startTarget, amountToCopy) to shallow copy the values (or pointers) in the array. That is, if an array is holding reference types, only the pointers will be copied and not the actual values of the reference objects being held.

  • System.arraycopy(b, 0, x, 3, 2) is equivalent to x[3:5] = b[0:2] in Python.

Multidimensional Arrays

  • int[][] 2d = new int[4][4];or int[][] 2d = new int[][] {{1}, {2, 3}, {4, 5, 6}};will create arrays inside of an array. This is useful for storing matrices, coordinate maps, or any other multidimensional data!

Generic Arrays

  • Arrays of generic objects are NOT allowed! Use ArrayLists instead.

  • Or, this workaround can be used:Type[] items = (Type[]) new Object[length]

Array Lists

Java has another built-in type that uses an array under the hood, which is the ArrayList. Here's how ArrayLists are different from normal arrays:

Simply assigning int[] c = b will copy the pointer to array b! Not the values! See for a discussion on why this is significant.

ArrayLists can resize arbitrarily. (They use something similar to the array case study in the page.

ArrayLists use and therefore do not support primitive types like int.

ArrayLists have all behaviors expected from the interface.

Java Objects
Generic Types
Collections
Amortization
An artistic interpretation of a new int[5] {6, 1, 2, 3, 99};