Final Review: Memory Management and Data Structures

ArrayList

An ArrayList stores a list of elements in contiguous memory locations.

get(i)

Gets the element at index i - fast.

set(i, element)

Replaces the element at index i with the specified element - fast.

add(element)

Appends the specified element to the end of the list - fast.

add(i, element)

Inserts the specified element at index i - slow.

remove(i)

Removes the element at index i in the list - slow.

Linked List

A linked list does not use contiguous memory locations.

Linked List Item

Each item in a linked list contains data and a pointer to the next item's location in memory.

ArrayList vs Linked List

ArrayList stores items in contiguous memory; Linked List stores each item anywhere in memory.

Static Variable

A class level variable; only a single copy is created and shared among all objects of the class.

Stack

The region where a method's local variables are allocated during a method call.

Heap

The region where the 'new' operator allocates memory for objects.

LinkedList Class

The LinkedList class implements the List interface.

List Interface

Defines a collection of ordered elements; elements can be accessed by their integer index.

LinkedList Declaration

LinkedList aList = new LinkedList();

Common LinkedList Method: get(index)

Returns element at specified index.

Common LinkedList Method: set(index, newElement)

Replaces element at specified index with newElement; returns element previously at specified index.

Common LinkedList Method: add(newElement)

Adds newElement to the end of the List; List's size is increased by one.

add()

Adds newElement to the List at the specified index. Indices of the elements previously at that specified index and higher are increased by one. List's size is increased by one.

size()

Returns the number of elements in the List.

remove(index)

Removes element at specified index. Indices for elements from higher positions are decreased by one. List size is decreased by one. Returns reference to element removed from List.

remove(existingElement)

Removes the first occurrence of an element which is equal to existingElement. Indices for elements from higher positions are decreased by one. List size is decreased by one. Returns true if specified element was found and removed.

Enhanced For Loop

A loop that iterates through a List using the syntax: for (element_type variable : array or collection) { //body of loop }.

Map

The Map interface defines a collection that maps keys to values (e.g., mapping student IDs to student names).

HashMap

The HashMap class implements the Map interface.

put()

Associates key with specified value. If key already exists, replaces previous value with specified value.

putIfAbsent()

Associates key with specified value if the key does not already exist or is mapped to null.

get()

Returns the value associated with key. If key does not exist, return null.

containsKey()

Returns true if key exists, otherwise returns false.

containsValue()

Returns true if at least one key is associated with the specified value, otherwise returns false.

ex. List.size()

Returns 0 when List is empty.

ex. List.add(8)

List is now: 8

HashMap

K represents the key type, V represents the value type. K and V must be reference types (e.g., String, Integer, Person).

remove(key)

If the key exists, it deletes that key-value pair and returns the value that was associated with that key. If the key doesn't exist, it returns null.

ex. Map.clear()

Map is now empty

keySet()

Returns a Set containing all keys within the map.

values()

Returns a Collection containing all values within the map.

Queue interface

Defines a Collection of ordered elements that supports element insertion only at the tail and element removal only from the head.

LinkedList class

Implements the Queue interface.

Queue myQueue = new LinkedList()

T represents the element's type and T must be a reference type.

add(newElement)

Adds newElement element to the tail of the queue. The queue's size increases by one.

remove()

Removes and returns the element at the head of the queue. Throws an exception if the queue is empty.

poll()

Removes and returns the element at the head of the queue if the queue is not empty. Otherwise, returns null.

element()

Returns, but does not remove, the element at the head of the queue. Throws an exception if the queue is empty.

peek()

Returns, but does not remove, the element at the head of the queue if the queue is not empty. Otherwise, returns null.

Set

The Set interface defines a Collection of unordered unique elements.

Example of Set

{red, green, blue} is a set and {red, green, blue} = {blue, red, green}.

Non-Set Example

{red, green, green, blue} is NOT a set as it contains duplicate elements.

HashSet

The HashSet class implements the Set interface.

Importing HashSet

To use HashSet, import java.util.HashSet.

Declaring HashSet

A HashSet can be declared and created as follows: HashSet hashSet = new HashSet(); T is a reference type that represents the HashSet's element type.

add() Method

If element does not exist, adds element to the set and returns true. If element already exists, returns false.

remove() Method

If element exists, removes element from the set and returns true. If the element does not exist, returns false.

contains() Method

Returns true if element exists, otherwise returns false.

size() Method

Returns the number of elements in the set.

Recursive Method

A recursive method is a method that calls itself.

Base Case

The base case returns without performing a recursive call and stops the recursion from continuing on forever.

Recursive Case

The recursive case calls the method itself.

Binary Search Algorithm

The binary search algorithm is a very efficient algorithm for guessing your partner's number.

Binary Search

An algorithm that begins at the midpoint of a range and halves the range after each guess.

midVal

Calculated as midVal = (lowVal + highVal) / 2.

Lower Guess

If your partner says 'lower', then guess in the range [lowVal, midVal-1].

Higher Guess

If your partner says 'higher', then guess in the range [midVal+1, highVal].

Recursive Algorithm

An algorithm that is applied again on a smaller range after each guess.

Recursive Binary Search

Used to quickly find an item in a sorted list stored in an array or ArrayList.

findMatch Method

A method that performs recursive binary search of an item in a list within the range lowVal to highVal.

Base Case 1

If item matches the middle element in the range [lowVal, highVal], then return the index of the middle element.

Base Case 2

If the range size is 1 (i.e., lowVal = highVal), then return -1 to indicate that the item is not found.

Recursive Call - Lower Half

Call findMatch(list, item, lowVal, midVal-1) if item < middle element.

Recursive Call - Higher Half

Call findMatch(list, item, midVal+1, highVal) if item > middle element.

Stack Region

A part of a program's memory reserved to support method calls.

Stack Frame

A structure that stores a method's parameters and local variables.

Stack Overflow

Occurs when a stack frame extends beyond the memory region allocated for the stack, often causing a program crash.

Stack Overflow Error

A report generated when a program crashes due to stack overflow.

Non-Recursive Algorithm

An alternative approach developed to avoid stack overflow in large problems.