2 of 11

Arrays

Java��int[] arr = new int[size];

C++��Int arr[size];

To retrieve / edit an element:

Retrieve: Object o = arr[index];

Edit: arr[index] = o;

3 of 11

ArrayList

Java�ArrayList<Integer> arr = new ArrayList<>(size); // you can initialize ArrayList without a size. Initializing ArrayList without size will default it to size 10.

C++�vector<int> arr;

To retrieve / edit:

Retrieve: Java: arr.get(i); C++: arr[i]

Add: Java: arr.add(object); C++: arr.push_back(item)�Add at an index: Java: arr.add(index, object); C++: arr.insert(index, item);�Remove: Java: arr.remove(index); C++: arr.erase(index); �Remove first occurrence of object (Only in Java): arr.remove(object);

4 of 11

Complexity of ArrayList

Note:

Add/remove for ArrayList at the end of the list is O(1) time, but adding/removing at a specific position and removing first occurrence of object costs O(N) time.

Try to initialize ArrayList with a size if you know what its max size will be. If the number of elements exceed the capacity, the ArrayList will have to resize, which costs time.

5 of 11

Queue

A queue is a First in, First Out data structure.

Example:

Push: cat, unicorn, human

Pop: cat, unicorn, human

6 of 11

Stack

A stack is a Last in, First Out data structure.

Example:

Push: cat, unicorn, human

Pop: human, unicorn, cat

7 of 11

Implementation

Both queue and stack can be implemented using a LinkedList

Functions:

add() / addLast(): Adds to the end of the list

push() / addFirst(): Adds to the front of the list

pop() / removeFirst(): Pops from the front of the list

removeLast(): Pops from the back of the list

8 of 11

Array Implementation

LinkedList is the most convenient implementation for Queue / Stack, but it costs memory / time since it maintains pointers between elements.

If you know the size of the queue/stack, then you can implement it with an array to make the queue/stack more efficient.

9 of 11

Queue Array Implementation

Maintains 2 pointers using ints. One pointer is for the popping, one is for adding

Java implementation:

static int a = 0; // add pointer�static int p = 0; // pop pointer�int[] q = new int[size];�public static int pop() {� a++; return q[a-1];�}�public static void add(int element) {� q[p] = element; p++;�}

10 of 11

Stack Array Implementation

Maintains only 1 pointer: position of the top of the stack

Java implementation:

static int pos = 1; // this is where an element would be added if add is called�int[] q = new int[size];�public static int pop() {� pos--; return q[pos];�}�public static void add(int element) {� q[pos] = element; pos++;�}

11 of 11

Other Useful Data Structures (Java)

HashSet� Uses hashing, O(1) contain, add, remove, but large constant factors�HashMap� Uses hashing, O(1) get, modify�TreeSet� O(log N) contain, add, remove�TreeMap� O(log N) get, modify�PriorityQueue� O(log N) insert, poll

Time complexity cheat sheet: https://tinyurl.com/dscomplexity