3345 (Lecture 3) Data Structures: Lists, Stacks, and Queues, Algorithm Complexity & Abstract Data Types

Data Structures

Organized collection of data with specific relationships and operations, essential for efficient data manipulation and storage.

Abstract Data Types (ADTs)

Mathematical abstractions of a set of objects with a set of operations, providing a high-level view of data and operations independent of implementation details.

Stack

Data structure with Last In First Out (LIFO) access, commonly used for function calls, expression evaluation, and backtracking in algorithms.

Queue

Data structure with First In First Out (FIFO) access, widely utilized in operating systems, simulations, and task scheduling algorithms.

ArrayList

Resizable array implementation of the List ADT, offering constant time access and dynamic resizing for efficient data management.

LinkedList

Doubly linked list implementation of the List ADT, suitable for frequent insertions and deletions due to its efficient memory allocation.

List ADT

Set of operations on a list, including printList, makeEmpty, find, insert, remove, and findKth, enabling versatile manipulation of list data structures.

Array Implementation

Implementing instructions using an array, with linear time printList and constant time findKth, crucial for efficient array-based data manipulation.

Linked List

Series of nodes with elements and links to successors, providing efficient memory usage and flexibility for data management.

Iterator

Object that allows traversal through a collection, with next, hasNext, and remove methods, essential for iterating over data structures and collections.

Collection Interface

Resides in package java.util, abstracts the notion of a collection of objects, providing a unified interface for working with different types of collections.

List Interface

Specifies methods for accessing, modifying, and traversing a list of objects, offering a standardized way to interact with list data structures.

ListIterator

Extends the functionality of an Iterator for Lists, with previous, hasPrevious, and add methods, enhancing the capabilities of list iteration and manipulation.

MyArrayList

Custom implementation of the ArrayList data structure, maintaining an underlying array and size, providing a tailored approach to array-based data management.

Capacity

Maximum size of the underlying array in an ArrayList, automatically increased as needed, ensuring efficient utilization of memory resources.

ensureCapacity

Routine to change the capacity of the underlying array in an ArrayList, enabling dynamic adjustment of memory allocation based on data requirements.

Generic Class

Class that can work with different data types, providing flexibility and reusability, essential for creating versatile and adaptable data structures.

Iterator Interface

Provides methods for traversing a collection, including next, hasNext, and remove, facilitating efficient iteration and manipulation of collections.

Maximum Subsequence Sum

The largest sum that can be obtained by adding a contiguous subsequence of a given set of integers

Exhaustive Search Approach

A method that systematically evaluates all possible solutions to find the best one

Upper Bound Rules

Guidelines used to determine the maximum limit of algorithm complexity

Algorithm Complexity

The measure of the resources required to execute an algorithm, often denoted by the Big O notation

Divide and Conquer

A problem-solving approach that breaks a problem into smaller, more manageable sub-problems, solves them, and then combines the solutions

Base Case

The condition in a recursive algorithm where the solution can be directly calculated without further recursion

Optimized Code

Code that has been improved to reduce complexity, increase efficiency, or optimize resource usage

Recursive Call

A function that calls itself to solve smaller instances of the same problem, often used in recursive algorithms

Kadane's Algorithm

An efficient algorithm for finding the maximum sum of a contiguous subarray within a one-dimensional array of numbers

Abstract Data Types (ADTs)

Data types that define a set of values and the operations that can be performed on them, independent of their implementation

Primitive Data Types

Fundamental data types that directly map to machine representations, such as integers, floating-point numbers, and characters

General List

A list of elements with various operations like print, makeEmpty, find, insert, remove, and findKth

Array Implementation

The use of arrays to implement a data structure, providing efficient random access to elements

Linked Lists Implementation

The use of linked lists to implement a data structure, allowing dynamic memory allocation and efficient insertion and deletion of elements