Data Structures, Abstract Data Types, and Algorithm Analysis

Vocabulary flashcards covering core concepts of Lists, Fundamental Data Structures, Algorithm Analysis, Queues, and Stacks.

Ordered List

A linear collection where elements are ordered by an inherent characteristic of the elements, such as names in alphabetical order or scores in ascending order.

Unordered List

A linear collection where the order of elements is not based on element characteristics, but is determined directly by the user of the list.

Indexed List

A linear collection where elements are referenced by their numeric position (index), and indexes are automatically updated whenever the list changes.

Array

A sequenced collection of variables all of the same type, where each cell is uniquely referenced by an index starting from $0$.

Capacity

The maximum number of elements that can be stored in an array or fixed-size data structure.

Singly Linked List

A unidirectional linked list composed of nodes containing data and a pointer to the next node, which can be traversed only from the head to the tail.

Circular Linked List

A linked list variation in which the last node references the first node, ensuring that every node in the list has a successor.

Dummy Head Node

A permanent initial node in a linked list (present even when empty) that simplifies insertion and deletion algorithms by eliminating special cases for null pointers.

Doubly Linked List

A linked list where each node contains explicit references to both its predecessor and its successor.

Tail Reference

An external reference pointing directly to the last node of a linked list, allowing direct $O(1)$ access to append elements at the end.

Primitive Operations

Basic computations performed by an algorithm (such as variable assignments, evaluations, comparisons, and array indexing) assumed to take a constant time $O(1)$ in the RAM model.

Asymptotic Complexity

The characterization of an algorithm's growth function and efficiency based on its dominant term as the problem size $n$ increases toward infinity.

Big-O Notation

A mathematical notation representing the formal upper bound of an algorithm's running time, defined as $f(n) \le c \times g(n)$ for all $n \ge n_0$ given positive constants $c$ and $n_0$.

Big-Omega Notation

A mathematical notation representing the lower bound of an algorithm's running time ($f(n) \ge c \times g(n)$ for all $n \ge n_0$), providing its best-case complexity.

Big-Theta Notation

A mathematical notation that encloses a function from above and below ($c_1 \times g(n) \le f(n) \le c_2 \times g(n)$ for $n \ge n_0$), used to describe average-case complexity.

Queue ADT

An Abstract Data Type storing arbitrary objects using a First-In, First-Out (FIFO) strategy, inserting at the rear (enqueue) and removing from the front (dequeue).

Circular Array Queue

An array-based queue implementation that reuses array slots circularly using modular arithmetic $r = (f + sz) \bmod N$ to avoid rightward drift.

Stack ADT

An Abstract Data Type storing arbitrary objects using a Last-In, First-Out (LIFO) strategy, where insertions (push) and deletions (pop) occur at the top.

Infix Expression

An arithmetic expression format where operators are placed between operands, requiring parentheses and operator precedence to determine evaluation order.

Postfix Expression

An arithmetic expression format where operators follow their operands, allowing stack-based evaluation without needing parentheses.