Data Structures Midterm

UML Class Modifier: +

Public access modifier; accessed everywhere.

UML Class Modifier: -

Private access modifier; accessed only in the current class.

UML Class Modifier: #

Protected access modifier; accessed in the current class and subclasses.

UML Class Modifier: ~

Default access modifier; used when no access modifier is specified.

Array Variable Declaration Syntax

[] variable_name; or int[] prime; or int prime[]; both equivalent.

Declaring and Defining an Array

Declare and create an array: int[] primes = new int[10] or separate declaration and definition.

Default Initialization for Numeric Arrays

Numeric values initialized to 0 when array is created.

Default Initialization for Boolean Values

Boolean values initialized to false when array is created.

Default Initialization for Char Values

Char values initialized to '\u0000' when array is created.

Accessing Array Elements

Use a[i] to access entry i of array named a; indices start at 0.

Initializing an Array with Existing Values

Example: int[] value = even; where both refer to the same array.

Referencing Array Length

Use array_variable_name.length to get the array length.

Two-Dimensional Array Access

Access using a[i][j] where i is the row and j is the column.

Ragged Array

A non-rectangular two-dimensional array.

Abstract Data Type (ADT)

Composed of a collection of data and a set of operations on that data.

List Interface

Provides the functionality of an indexed data structure and more operations.

ArrayList Class

An implementation of the List interface that allows efficient addition of elements.

Adding Elements to ArrayList

Use myList.add(item) to add at the end of the ArrayList.

ArrayList Method: get()

Returns the item at a specified position in the list.

ArrayList Method: set()

Replaces an item at a specified position in the list.

ArrayList Method: size()

Returns the number of items in the list.

Generic Collections

Lists can specify types to restrict the types of objects stored.

Capacity vs Size

Capacity is total allocated memory; size is the number of elements stored.

Primitives in Java

Basic data types such as int, char, boolean; not objects.

Wrapper Classes in Java

Used to wrap primitive types as objects; e.g., Integer for int.

Big-O Notation

Expresses the performance or complexity of an algorithm in relation to input size.

Linear Growth Rate (O(n))

Processing time increases linearly with the number of inputs.

Quadratic Growth Rate (O(n^2))

Processing time increases proportional to the square of the number of inputs.

Logarithmic Time Complexity (O(log n))

Time complexity where operations cut the problem size in half each time.

Single-Linked List

A data structure allowing insertion and removal at arbitrary locations with O(1) time.

Stack Abstract Data Type

Last-In, First-Out data structure allowing access only to the top element.

Postfix Expression

Mathematical notation where operators follow operands, e.g., 'a b +' instead of 'a + b'.

Postfix to Infix Conversion

Transforming postfix expressions back to standard infix notation.

Pushing to Stack

Adding a new element on top of the stack.

Popping from Stack

Removing and retrieving the top element from the stack.

Peek Operation on Stack

Inspecting the top element of the stack without removing it.

Size of ArrayList

Indicates how many elements are initially stored in the list.

Element Insertion in ArrayList

Inserts at a specified position and shifts elements as necessary.

Generic Classes

Classes that can operate on a variety of data types using type parameters.

Wrapper.valueOf()

Converts a value to its corresponding wrapper object.

Wrapper.parseType()

Parses a string representation of the value back to its primitive type.

Reallocate Method

Creates a new array that is twice the size of the current array.

Complexity of T(n) = O(n^2 + 5n + 25)

Expressed simply as O(n^2) in big-O notation.

Algorithm with Exponential Growth

Algorithms that grow dramatically in complexity with increased inputs.

Removing Element from ArrayList

Removes an element at a specified position and shifts items to fill the gap.

Adding Element to End of ArrayList

Generally a constant time operation, O(1), but can be O(n) if reallocation occurs.

Accessing Elements in Indexed Data Structures

Elements can be accessed in any order using subscript values.

Accessing Array Elements in a Loop

Loop through indices using for(int k=0; k

Array Initialization with Specific Values

Declare and initialize: int[] primes={2,3,5,7,11,13,17};.