Data Structures and Algorithms Complete Lecture Review

Comprehensive vocabulary flashcards covering fundamentals of data structures, arrays, linked lists, stacks, queues, trees, graphs, sorting, searching, and hashing.

Data

Raw facts and figures, or a value or set of values specifying either a variable or a constant (e.g., marks of students, address of a customer, value of pi).

Information

The processed, structured result of data that provides meaningful context (for example, "Arun is a student, whose age is 12").

Data Structure

A particular way of storing and organizing data in a computer's memory or on disk storage so that it can be used efficiently, expressed as $\text{Data Structure} = \text{Related Data} + \text{Allowed Operations}$.

Elementary Data Item

A data item that does not have subordinate data items and is treated as a single, indivisible entity (such as a student's roll number).

Group Data Item

A data item composed of one or more subordinate data items (for example, a student's name divided into first name, middle name, and last name).

Record

A collection of related data items grouped together, such as Student_ID, Student_name, City, and Age.

File

A collection of related records, such as the records of all 24 students in a class stored together.

Primary Key

A specific data item whose value uniquely identifies a record within a file (for example, Student_ID).

Primitive Data Structures

The fundamental data types directly supported by a programming language, such as integer, real/float, character, double, and pointer.

Non-Primitive Data Structures

Data structures that are created using primitive data structures, including arrays, linked lists, stacks, queues, trees, and graphs.

Linear Data Structure

A data structure in which elements are stored in a linear or sequential order (such as arrays, stacks, queues, and linked lists).

Non-linear Data Structure

A data structure in which elements are not stored in sequential order, permitting hierarchical or interconnected networks (such as trees and graphs).

Linear Array

A collection of similar data elements stored in consecutive, contiguous memory locations, where each item is referenced by an index or subscript.

Array Address Calculation Formula

The mathematical formula to determine the location of element $A[k]$: $\text{Address}(A[k]) = \text{BA}(A) + w(k - \text{lower\_bound})$, where $\text{BA}$ is the base address, $w$ is element size in bytes, and $k$ is the index.

Array Length Formula

The formula used to compute the total number of elements in a linear array: $\text{Length} = \text{upper\_bound} - \text{lower\_bound} + 1$.

Row Major Order

A 2D array memory storage arrangement where elements are stored row by row, calculated using $\text{Address}(A[I][J]) = \text{Base\_Address} + w(N(I - 1) + (J - 1))$, where $N$ is the number of columns.

Column Major Order

A 2D array memory storage arrangement where elements are stored column by column, calculated using $\text{Address}(A[I][J]) = \text{Base\_Address} + w(M(J - 1) + (I - 1))$, where $M$ is the number of rows.

Parallel Arrays

Two or more arrays that hold related attributes of a record across identical indices (e.g., separate arrays for Name, Course, and Age of the same students).

Sparse Matrix

A matrix in which the majority of the elements have a value of zero.

Triplet Representation

A sparse matrix array representation that stores only non-zero values along with their row and column indices, where row 0 specifies the total rows, total columns, and total non-zero elements.

Linked List

A linear data structure consisting of dynamic elements called nodes, each containing a data field and a pointer (link field) storing the address of the next node.

Singly Linked List

The simplest type of linked list in which each node stores data and a single pointer to the next node of the same type, allowing traversal in only one direction.

Circular Linked List

A linked list whose last node's link field points back to the first node (head) rather than containing a $\text{NULL}$ pointer.

Doubly Linked List

A linked list containing three parts per node: a data field, a $\text{NEXT}$ pointer pointing to the succeeding node, and a $\text{PREV}$ pointer pointing to the preceding node, enabling bidirectional traversal.

Circular Doubly Linked List

A doubly linked list where the $\text{NEXT}$ field of the last node stores the address of the head node, and the $\text{PREV}$ field of the first node stores the address of the last node.

Header Linked List

A linked list containing a special header node at the beginning whose data field is kept $\text{NULL}$, classified as either grounded (last node points to $\text{NULL}$) or circular (last node points to header).

Overflow

A condition that occurs when attempting to insert new data into a data structure when no free space is available in memory.

Underflow

A condition that occurs when attempting to delete data from a data structure that is already empty.

Stack

A linear data structure following the Last-In, First-Out (LIFO) or First-In, Last-Out (FILO) order, where insertions and deletions occur strictly at one end called the top.

Push

The primitive stack operation of adding an element to the top of the stack after verifying that $\text{TOP} \neq \text{MAX} - 1$.

Pop

The primitive stack operation of removing and accessing the topmost element of the stack after verifying that $\text{TOP} \neq \text{NULL}$.

Peek

The stack operation that returns or retrieves the value of the topmost element without removing it from the stack.

Polish Notation

Prefix notation in algebraic expressions where operators precede their operands (e.g., $+AB$), as opposed to infix ($A+B$) or reverse Polish / postfix ($AB+$).

Recursion

A programming technique in which a function calls itself to solve smaller versions of a problem, requiring a base case and a recursive case, and utilizing the system stack.

Queue

A linear data structure following the First-In, First-Out (FIFO) principle, where elements are inserted at the rear end and removed from the front end.

Circular Queue

A linear FIFO data structure (also called a ring buffer) where the last position connects back to the first position, resolving linear queue space waste when $\text{rear} = \text{MAX} - 1$.

Deque

A double-ended queue where elements can be inserted or deleted from either the front (head) or back/rear (tail) end, bypassing the strict FIFO rule.

Input Restricted Queue

A variant of a double-ended queue (deque) in which insertions are allowed only at one end, but deletions can occur from both ends.

Output Restricted Queue

A variant of a double-ended queue (deque) in which deletions are allowed only from one end, but insertions can occur at both ends.

Tree

A non-linear hierarchical data structure consisting of nodes connected by edges, having exactly one root node and no cycles, where $n$ nodes have exactly $n - 1$ edges.

Degree of a Node

The number of child nodes descending from a specific node in a tree.

Height of a Tree

The number of edges on the longest path from the root node to a leaf node.

Depth of a Node

The number of edges on the path from the root node to that specific node.

Binary Tree

A hierarchical tree data structure in which each parent node can have at most two children, referred to as the left child and the right child.

Full Binary Tree

A binary tree in which every node has either $0$ or $2$ children, meaning every non-leaf node has exactly two children.

Complete Binary Tree

A binary tree in which every level $l$ except possibly the last is completely filled with $2^l$ nodes, and all nodes at the last level are strictly left-aligned.

Skewed Binary Tree

A binary tree in which every node has only either one child or no child, categorized as left-skewed or right-skewed.

Binary Search Tree

A node-based binary tree in symmetric order where every key in the left subtree is less than the node's key, and every key in the right subtree is greater than the node's key.

Expression Tree

A binary tree representing an arithmetic expression, wherein each internal node represents an operator and each leaf node represents an operand.

Preorder Traversal

A depth-first binary tree traversal that visits the root node first, traverses the left subtree, and then traverses the right subtree ($\text{Root} \rightarrow \text{Left} \rightarrow \text{Right}$).

Inorder Traversal

A depth-first binary tree traversal that traverses the left subtree, visits the root node, and then traverses the right subtree ($\text{Left} \rightarrow \text{Root} \rightarrow \text{Right}$), yielding elements in ascending order in a BST.

Postorder Traversal

A depth-first binary tree traversal that traverses the left subtree, traverses the right subtree, and finally processes the root node ($\text{Left} \rightarrow \text{Right} \rightarrow \text{Root}$).

Graph

A non-linear data structure formally defined as an ordered set $G = (V, E)$, where $V(G)$ is a set of vertices (nodes) and $E(G)$ is a set of edges connecting pairs of vertices.

Regular Graph

A graph where every vertex has the exact same degree ($k$), meaning every node has the identical number of neighbors ($k$-regular graph).

Complete Graph

A graph where every pair of vertices is connected by an edge, containing exactly $\frac{n(n-1)}{2}$ edges for $n$ vertices.

Clique

A subset of the vertex set $C \subseteq V$ in an undirected graph $G = (V, E)$ such that every two distinct vertices in $C$ are connected by an edge.

Adjacency Matrix

A sequential representation of a graph using a 2D array of size $n \times n$, where cell $A[i][j] = 1$ if an edge exists from vertex $i$ to vertex $j$, and $0$ otherwise, taking $O(V^2)$ memory space.

Adjacency List

A linked representation of a graph where each vertex stores a linked list of all destination vertices to which it has connecting edges, saving space for sparse graphs.

Linear Search

A sequential searching algorithm that checks each element of an unordered list one by one until a match is found, with a time complexity of $O(n)$.

Binary Search

A divide-and-conquer search algorithm that repeatedly divides a sorted list in half to find a target element, achieving a time complexity of $O(\log n)$.

Bubble Sort

An internal, stable sorting algorithm that repeatedly compares consecutive adjacent pairs and swaps them if the lower-index element is greater, running in best-case $O(n)$ and worst-case $O(n^2)$.

Selection Sort

An internal, non-stable sorting algorithm that repeatedly identifies the minimum element in the unsorted subarray and swaps it to the front, taking $O(n^2)$ time across all cases.

Insertion Sort

A simple sorting algorithm that splits the array into sorted and unsorted segments, picking values from the unsorted segment and inserting them into their correct position in the sorted segment.

Merge Sort

A stable divide-and-conquer algorithm that recursively splits an array into two halves, sorts each half, and merges them back in order, running in $O(n \log n)$ time with $O(n)$ space.

Quick Sort

A non-stable divide-and-conquer sorting algorithm developed by C. A. R. Hoare that partitions an array around a chosen pivot value, running in average time $O(n \log n)$ and worst-case $O(n^2)$.

Hashing

A technique that converts a key into a table index using a mathematical algorithm (hash function) to enable search, insertion, and deletion in average $O(1)$ time.

Division Method (Hashing)

A hash function technique based on the remainder of division, defined by $h(k) = k \bmod m$, where $m$ is the hash table size.

Open Hashing

A collision resolution technique (separate chaining) where each hash table slot points to an external linked list of keys that hash to that same index, meaning the table never fills up.

Closed Hashing

A collision resolution technique (open addressing) where all keys are stored directly within the hash table itself by following a probe sequence to find an empty slot.

Linear Probing

A closed hashing method that searches for the next free table slot sequentially using the probe formula $h(k, i) = (h(k) + i) \bmod m$, which can cause primary clustering.

Data

Raw, unorganized facts and figures that carry very little meaning until they are processed systematically.

Information

The meaningful, processed, and structured result obtained from data processing.

Data Structure

A particular way of organizing and storing data in computer memory or disk storage so that it can be used efficiently; characterized as related data plus allowed operations.

Data Type

The kind or form of a variable used throughout a program that specifies which values the variable can hold, represented as an abstract language-level implementation.

Elementary Data Item

A data item that does not contain subordinate data items and is treated as a single undivided value (e.g., a student roll number).

Group Data Item

A data item composed of one or more subordinate data items (e.g., a student name divided into first, middle, and last name).

Record

A collection of individual data items grouped together to represent a single entity (e.g., student ID, name, city, and age).

File

A collection of related records stored together (e.g., the records of all 24 students in a class).

Primary Key

A specific data item or field in a record whose value uniquely identifies that record within a file.

Linear Data Structure

A data structure whose elements are stored in a sequential or linear order, such as arrays, stacks, queues, and linked lists.

Non-linear Data Structure

A data structure whose elements are not arranged in a sequential order, such as trees and graphs.

Array

A collection of similar data elements stored in consecutive, contiguous memory locations and referenced by a numeric index or subscript.

Row Major Order

A 2D array memory storage method where elements are stored row by row, such that all elements of the first row occupy contiguous memory locations before those of the second row.

Column Major Order

A 2D array memory storage method where elements are stored column by column, such that all elements of the first column occupy contiguous memory locations before those of the second column.

Parallel Arrays

Two or more arrays of identical capacity that hold related attribute data of an entity at corresponding indices.

Sparse Matrix

A matrix in which the majority of the elements have a value of zero.

Triplet Representation

A sparse matrix array representation where the 0th row records the total number of rows, columns, and non-zero values, followed by triplets storing the row index, column index, and value of each non-zero element.

Linked List

A dynamic linear data structure consisting of nodes, where each node contains an element of data and a pointer (link) storing the address of the next node.

Singly Linked List

The simplest form of linked list where every node contains data and a single pointer referencing the next node, permitting traversal in only one forward direction.

Circular Linked List

A linked list variation where the next pointer of the final node points back to the first node instead of storing a NULL pointer.

Doubly Linked List

A two-way linked list whose nodes comprise three distinct parts: a data field, a forward pointer (NEXT), and a backward pointer (PREV) referencing the preceding node.

Header Linked List

A special linked list containing a dedicated header node at the very beginning whose data field is typically NULL and is pointed to by the START pointer.

Grounded Header Linked List

A header linked list variant where the NEXT field of the final data node points to NULL.

Circular Header Linked List

A header linked list variant where the NEXT field of the final node stores the address of the initial header node.

Overflow

A condition that occurs during insertion when an attempt is made to allocate space or add an item to a data structure that has reached maximum capacity.

Underflow

A condition that occurs during deletion when an attempt is made to remove an element from an empty data structure.

Stack

A linear data structure operating under the Last-In, First-Out ($\text{LIFO}$) principle, where element insertion (push) and deletion (pop) take place exclusively at a single position called the TOP.

Peek

A stack operation that inspects and retrieves the value of the topmost element without removing it from the stack.

Polish Notation

A prefix algebraic notation where every operator is placed before its respective operands (e.g., $+ A B$).

Reverse Polish Notation

A postfix algebraic notation where every operator is placed immediately after its respective operands (e.g., $A B +$).