Data Structures Midterm

Christopher Schleyer         3/1/2025

Stockton University

Data Structures and Algorithms Exam 1 Review

UML classes;

• + = public

  • Accessed everywhere

• - = private

  • Accessed only in the current class

• # = protected

  • Only the current class and subclasses (and sometimes also same-package classes) of this class will have access to the field or method.

• ~ = default 

Declaring an Array Variable 

• Do not have to create an array while declaring array variable 

– [] variable_name;

– int [] prime;

– int prime[]; 

• Both syntaxes are equivalent

• Multiple elements of the same type 

• No memory allocation at this point

Defining an Array 

• Define an array as follows: 

– variable_name=new [N]; 

– primes=new int[10]; 

• Declaring and defining in the same statement: 

– int[] primes=new int[10]; 

• In JAVA, int is of 4 bytes, total space=4*10=40 bytes

Default Initialization 

• When array is created, array elements are initialized 

– Numeric values (int, double, etc.) to 0 

– Boolean values to false – Char values to ‘\u0000’ (unicode for blank character)

Arrays in Java 

•Java has special language support for arrays. 

– To make an array: declare, create, and initialize it. 

– To access entry i of array named a, use a[i]. – Array indices start at 0.

Initializing Arrays 

• Initialize and specify size of array while declaring an array variable int[] primes={2,3,5,7,11,13,17}; //7 elements 

• You can initialize array with an existing array 

int[] even={2,4,6,8,10}; 

int[] value=even; 

– One array but two array variables! 

– Both array variables refer to the same array 

– Array can be accessed through either variable name

Array Length

• Refer to array length using length

– A data member of array object

– array_variable_name.length

– for(int k=0; k<primes.length;k++)

….

• Sample Code:

long[] primes = new long[20];

System.out.println(primes.length);

• Output: 20

Two-Dimensional Arrays in Java 

•Array access. 

Use a[i][j] to access entry in row i and column j. 

•Zero-based indexing. Row and column indices start at 0.

Ragged Array

• Non-rectangular two-dimensional arrays are sometimes called ragged arrays.

Traversing a Ragged Array 

• In traversing a ragged two-dimensional array (named ragged), we cannot assume that each row contains the same numbers of columns. 

• Write to find the sum of the elements in the ragged array declared above.

Abstract data type (ADT)  

An ADT is composed of 

◼ A collection of data 

◼ A set of operations on that data  

Specifications of an ADT indicate 

◼ What the ADT operations do, not how to implement them  

Implementation of an ADT

◼ Includes choosing a particular data structure 

◼ A data structure is a construct that can be defined in a programming language to store a collection of data

A list is a collection of elements, each with a position or index  Classes ArrayList and LinkedList are subclasses of abstract class AbstractList and implement the List interface

List Interface and ArrayList Class 

• An array is an indexed structure  

• In an indexed structure,  

  • elements may be accessed in any order using subscript values  

  • elements can be accessed in sequence using a loop that increments the subscript  

• With the Java Array object, you cannot 

  • increase or decrease its length (length is fixed)

  • add an element at a specified position without shifting elements to make room  

  • remove an element at a specified position and keep the elements contiguous without shifting elements to fill in the gap

• Java provides a List interface as part of its API java.util

• Classes that implement the List interface provide the functionality of an indexed data structure and offer many more operations

• A sample of the operations:

  • Obtain an element at a specified position

  • Replace an element at a specified position

  • Find a specified target value

  • Add an element at either end

  • Remove an element from either end

  • Insert or remove an element at any position  

  • Traverse the list structure without managing a subscript

• All classes introduced in this chapter support these operations, but they do not support them with the same degree of efficiency

List Interface and ArrayList Class 

• Unlike the Array data structure, classes that implement the List interface cannot store primitive types

• Classes must store values as objects

• This requires you to wrap primitive types, such an int and double in object wrappers, in these cases, Integer and Double
  
  

ArrayList class

• The simplest class that implements the List interface

• An improvement over an array object

• Use when:  

  • you will be adding new elements to the end of a list

  • you need to access elements quickly in any order

  • To declare a List “object” whose elements will reference String objects:

List myList = new ArrayList(); 

• The initial List is empty and has a default initial capacity of 10 elements

• To add strings to the list, myList.add("Bashful"); 

Arraylist methods:

• get(int index)=Return the item at a specific position in the list

• set(int index, T item) = Replace an item at a specified position in the list 

• size() = Return the number of items in the list

• public boolean add(T item) = Adds a reference to the item at end of the ArrayList. Always returns true

• public void add(int index, T item) = Adds a reference to the item, inserts it before the item at position index

• public int indexOf(Object item)= Return the position of the first occurrence of an item in the list, or -1 if not in the list

• public T remove(int index) = Returns and removes the item at position index and shifts the items that follow it to fill the vacated space.
  
  

Generic Collections  

• The statement 

List myList = new ArrayList(); 

uses a language feature called generic collections or generics 

• The statement creates a List of String; only references of type String can be stored in the list

• String in this statement is called a type parameter

• The type parameter sets the data type of all objects stored in a collection

• The general declaration for generic collection is 

CollectionClassName<E> variable = new CollectionClassName<E>(); 

• The <E> indicates a type parameter

• Adding a non-compatible type to a generic collection will generate an error during compile time

However, primitive types will be autoboxed

Size vs Capacity

• Capacity – This refers to the total amount of memory allocated for the array. 

• Size – This refers to the actual number of elements currently stored in the array. It tells you how many positions in the array are actively being used.

reallocate Method = Creates a new array that is twice the size of the current array and then copy the contents of the new array

Primitives & Wrappers

Java has a wrapper class for each of the eight primitive data types

• Primitive Type = the most basic data type available in Java. These types are not objects and are used to store simple values directly in memory. They are efficient in terms of memory usage and performance.

  • They include int, byte, short, char, boolean, double, and float. 

• Wrapper Classes = used in situations where objects are required, such as for elements of a Collection. Each primitive type has a corresponding wrapper class. Wrapper classes provide additional functionality and allow primitive types to be used as objects. For example:

  • Integer obj = Integer.valueOf(n);

  • Integer for int

  • Character for char

  • Boolean for boolean

• Wrapper classes are essential when working with collections, as collections can only store objects. They also support null values, which primitive types do not.

Wrapper methods

• Wrapper.valueOf() takes a value (or string) and returns an object of that class

• Wrapper.parseType() parses a string representation & returns the literal value.

Generic Methods

• Generic methods, classes, and interfaces allow you to define a single method or class that can operate on a group of related methods or types, respectively.

• If the operations performed by several overloaded methods are identical for each argument type, the overloaded methods can be more compactly and conveniently coded using a genericmethod.

• You can write a single generic method declaration that can be called with arguments of different types. 

• Based on the types of the arguments passed to the generic method, the compiler handles each method call appropriately. 

Generic Method Implementation

• All generic method declarations have a type-parameter section delimited by angle brackets (< and >) that precedes the method’s return type (< T > in this example). 

• Each type-parameter section contains one or more type parameters (also called formal type parameters), separated by commas. 

• A type parameter, also known as a type variable, is an identifier that specifies a generic type name. 

• Can be used to declare the return type, parameter types and local variable types in a generic method, and act as placeholders for the types of the arguments passed to the generic method (actual type arguments). 

• A generic method’s body is declared like that of any other method. Type parameters can represent only reference types—not primitive types. 

Generic Classes 

• The concept of a data structure, such as a stack, can be understood independently of the element type it manipulates. 

• Generic classes provide a means for describing the concept of a stack (or any other class) in a type-independent manner. 

• These classes are known as parameterized classes or parameterized types because they accept one or more type parameters.

Algorithm Efficiency and Big-O

• Getting a precise measure of the performance of an algorithm is difficult

• Big-O notation expresses the performance of an algorithm as a function of the number of items to be processed

• This permits algorithms to be compared for efficiency

• For more than a certain number of data items, some problems cannot be solved by any computer

Linear Growth Rate (O(n))

• If processing time increases in proportion to the number of inputs n, the algorithm grows at a linear rate

• If processing time increases in proportion to the number of inputs n, the algorithm grows at a linear rate

Quadratic Growth Rate

• If processing time is proportional to the square of the number of inputs n, the algorithm grows at a quadratic rate

• If processing time is proportional to the square of the number of inputs n, the algorithm grows at a quadratic rate

Big-O Notation

• The O() in the previous examples can be thought of as an abbreviation of "order of magnitude"

• A simple way to determine the big-O notation of an algorithm is to look at the loops and to see whether the loops are nested

• Assuming a loop body consists only of simple statements,

  • a single loop is O(n)

  • a pair of nested loops is O(n2)

  • a nested pair of loops inside another is O(n3)

  • and so on . . .

• You must also examine the number of times a loop is executed

  • for(i=1; i < x.length; i *= 2) {

// Do something with x[i] 

}  

• The loop body will execute k-1 times, with i having the following values: 1, 2, 4, 8, 16, . . ., 2k until 2k is greater than x.length

• Since 2k-1 = x.length < 2k and log22k is k, we know that k-1 = log2(x.length) < k

• Thus we say the loop is O(log n) (in analyzing algorithms, we use logarithms to the base 2)

• Logarithmic functions grow slowly as the number of data items n increases

Ex:
Consider the following program structure: 

for (int i = 0; i < n; i++) { 

for (int j = 0; j < n; j++) { 

Simple Statement 

} 

}

for (int i = 0; i < n; i++) {

Simple Statement 1

Simple Statement 2

Simple Statement 3

Simple Statement 4

Simple Statement 5

}

Simple Statement 6

Simple Statement 7 ... 

Simple Statement 30 

This concludes to a complexity of 

T(n) = n2+5n+25

• In terms of T(n), T(n) = O(f(n))

• There exist 

  • two constants, n0 and c, greater than zero, and

  • a function, f(n),

• such that for all n > n0, cf(n) = T(n)

• In other words, as n gets sufficiently large (larger than n0), there is some constant c for which the processing time will always be less than or equal to cf(n)

• cf(n) is an upper bound on performance

• The growth rate of f(n) will be determined by the fastest growing term, which is the one with the largest exponent

• In the example, an algorithm of O(n2 + 5n + 25) is more simply expressed as O(n2)

• In general, it is safe to ignore all constants and to drop the lower-order terms when determining the order of magnitude

• Order of complexity from shortest to longest time:
  O(1), O(log n), O(n), O(n log n), O(n^2 ), O(n^3), O(2^n), O(n!)

Algorithms with Exponential and Factorial Growth Rates

• Algorithms with exponential and factorial growth rates have an effective practical limit on the size of the problem they can be used to solve

• The set and get methods execute in constant time: O(1)  Inserting or removing general elements is linear time: O(n)  Adding at the end is (usually) constant time: O(1)  With our reallocation technique the average is O(1)  The worst case is O(n) because of reallocation

Binary Search

• Locates a target value in a sorted array/list by successively eliminating half of the array from consideration. 

• How many elements will it need to examine? O(log N) 

• Can be implemented with a loop or recursively

Single-Linked Lists

• A linked list is useful for inserting and removing at arbitrary locations

• The ArrayList is limited because its add and remove methods operate in linear (O(n)) time— requiring a loop to shift elements

• A linked list can add and remove elements at a known location in O(1) time

• In a linked list, instead of an index, each element is linked to the following element

A List Node

• A node can contain:

  • a data item

  • one or more links

• A link is a reference to a list node

• In our structure, the node contains a data field named data of type E

• and a reference to the next node, named next

A Single-Linked List Class

• Generally, we do not have individual references to each node.

• A SingleLinkedList object has a data field head, the list head, which references the first list node

Stacks

• one of the most commonly used data structures in computer science

• A stack can be compared to a Pez dispenser

• Only the top item can be accessed

• You can extract only one item at a time

• The top element in the stack is the last added to the stack (most recently)

• The stack’s storage policy is Last-In, FirstOut, or LIFO

Specification of the Stack Abstract Data Type

• Only the top element of a stack is visible; therefore the number of operations performed by a stack are few

• We need the ability to

  • test for an empty stack (empty)

  • inspect the top element (peek)

  • retrieve the top element (pop)

  • put a new element on the stack (push)
    
    

PostFix Expressions

A Postfix expression is a mathematical notation where operators come after the operands. For example, instead of writing a + b, you write a b +.

Key Point:
In Postfix, you evaluate expressions by processing the operands first and then applying the operators.

Example:

Input: arr = [“2”, “3”, “1”, “*”, “+”, “9”, “-“]
Output: -4
Explanation: If the expression is converted into an infix expression, it will be 2 + (3 * 1) – 9 = 5 – 9 = -4.