Data Structures and Algorithms: Big O Notation and Linked Lists

Vocabulary practice flashcards covering algorithms, computational complexity, Big O classifications, array constraints, and linked list structures and operations.

Algorithm

A well-defined sequence of steps that takes one or more values as inputs and produces one or more values as outputs.

Data Structure

A collection of data values, the relationships between them, and the operations that can be applied to them.

Computational Complexity

A measurement of the amount of resources, such as time and space (memory), that an algorithm requires to run.

Big O Notation

A mathematical notation representing an inclusive upper bound, indicating that an algorithm's execution metrics grow no faster than a specified rate.

Little o Notation

A mathematical notation representing a strict upper bound, indicating that an algorithm grows strictly slower than a specified rate.

Constant Time ($O(1)$)

An algorithmic time complexity where an algorithm takes the exact same amount of effort to execute regardless of input size, typical of simple variable assignments, arithmetic operations, and direct index references.

Linear Time ($O(n)$)

An algorithmic time complexity indicating that the effort to execute an algorithm grows proportionally to the number of items being processed, typical of simple loops iterating over an input.

Quadratic Time ($O(n^2)$)

An algorithmic time complexity where an algorithm performs $n^2$ operations relative to the input size, typically caused by nested loops iterating over the data.

Logarithmic Time ($O(\log(n))$)

An algorithmic time complexity reflecting the inverse of exponentiation, typically occurring when an algorithm disregards large portions of the input with each successive loop.

Auxiliary Space Complexity

The additional memory an algorithm requires to execute, excluding the memory necessary to store the original input data.

Static Array

A fixed-size contiguous collection of elements whose capacity must be known and allocated at the time of definition.

Dynamic Array

A resizable array structure that requires memory reallocation when growing and suffers costly $O(n)$ overhead when inserting or removing elements at the beginning or interior.

Node

An individual element in a linked list that stores a data payload along with pointer references linking it to adjacent nodes.

Head

A pointer reference designating the first node in a linked list.

Tail

A pointer reference designating the final node in a linked list, whose forward reference pointer leads to None.

Singly Linked List

A linear data structure consisting of nodes where each node contains data and a single pointer reference (next) targeting the succeeding node in the sequence.

Doubly Linked List

A linear linked data structure where each node stores two pointer references: one forward reference (next) to the following node and one backward reference (prev) to the preceding node.

Append

A linked list operation that inserts a new node at the end of the list, operating with $O(1)$ time complexity in both singly and doubly linked lists.

Prepend

A linked list operation that inserts a new node at the start of the list, operating with $O(1)$ time complexity in both singly and doubly linked lists.

Pop Left

An operation that removes and returns the first node from a linked list, running in $O(1)$ time complexity.

Pop Right (Singly Linked List)

The operation of removing the final node in a singly linked list, which runs in $O(n)$ time complexity because it requires traversing the list to locate the node preceding the tail.

Pop Right (Doubly Linked List)

The operation of removing the final node in a doubly linked list, which runs in $O(1)$ time complexity because the preceding node is directly accessible via the tail's prev pointer.

Traversal

The process of moving sequentially through the nodes of a list, which can only move forward in a singly linked list, but can proceed both forward and backward in a doubly linked list.