Data Structures Vocabulary Flashcards

Flashcards covering core vocabulary, operational properties, algorithm complexities, and structural definitions from the lecture notes.

Linked List

A linear data structure used to store data elements sequentially, where successive elements are connected by pointers and the last element points to NULL.

Sequential Access

The access model supported by linked lists, requiring $O(n)$ search time compared to $O(1)$ direct index access in arrays.

Null Pointer Dereferencing

A runtime error that occurs when a program attempts to access data or memory through a pointer that equals NULL.

Singly Linked List Insertion at Beginning

An operation with time complexity $O(1)$ performed by setting temp->next = head and updating head = temp.

Floyd's Cycle Detection Algorithm

A technique using a slow pointer moving at speed $x$ and a fast pointer moving at speed $2x$ to detect loops in a linked list in $O(n)$ time.

Circular Singly Linked List (CSLL)

A variant of a singly linked list in which the next pointer of the last node points back to the head node instead of NULL.

Circular Doubly Linked List (CDLL)

A doubly linked list where the previous pointer of the head node points to the last node, and the next pointer of the last node points to the head node.

Stack

A linear data structure that stores elements using the Last In First Out (LIFO) or First In Last Out (FILO) access restriction.

Catalan Number (Stack Permutations)

The mathematical formula $C_n = \frac{1}{n+1}\binom{2n}{n}$ used to compute the total number of valid stack permutations for $n$ inputs.

Stack Overflow

An error condition encountered during a push operation when the stack has reached its maximum allocated capacity ($\text{top} == N - 1$).

Stack Underflow

An error condition encountered during a pop operation when attempting to remove an element from an empty stack ($\text{top} == -1$).

Infix Notation

An expression representation where operators are placed between their operands, such as $a + b$.

Postfix Notation

Also known as Reverse Polish notation, an expression representation where operators follow their operands, such as $a b +$.

Prefix Notation

Also known as Polish notation, an expression representation where operators precede their operands, such as $+ a b$.

Queue

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

Circular Queue

A queue implementation using array modulo arithmetic ($(R + 1) \pmod N$) to connect the last index back to the first index, preventing memory wasted by standard linear queues.

$n$-ary Tree Leaf Node Relation

A formula stating that in a full $n$-ary tree with $i$ internal nodes, the total number of leaf nodes $L$ equals $L = i(n - 1) + 1$.

Binary Tree Leaf-to-Degree-2 Property

A property of binary trees where the number of leaf nodes ($n_0$) is always equal to the number of internal nodes with two children ($n_2$) plus one ($n_0 = n_2 + 1$).

Full Binary Tree

A binary tree structure where every internal node has strictly zero or two children.

Complete Binary Tree (CBT)

A binary tree in which every level is fully filled except possibly the last level, which is filled sequentially from left to right.

Perfect Binary Tree

A binary tree where all internal nodes have two children and all leaf nodes are located at the exact same level or depth.

Preorder Traversal

A binary tree traversal algorithm that visits nodes in the sequence: Root, Left Subtree, Right Subtree.

Inorder Traversal

A binary tree traversal algorithm that visits nodes in the sequence: Left Subtree, Root, Right Subtree.

Postorder Traversal

A binary tree traversal algorithm that visits nodes in the sequence: Left Subtree, Right Subtree, Root.

Binary Search Tree (BST)

A binary tree data structure where for every node, all keys in its left subtree are smaller and all keys in its right subtree are larger.

Inorder Successor

The node with the smallest key in a node's right subtree (leftmost node of the right subtree), used to replace a node with two children during deletion.

AVL Tree

A self-balancing binary search tree where the balance factor $BF = H(\text{LST}) - H(\text{RST})$ of every node is restricted to $-1$, $0$, or $1$.

LL Rotation

A single right rotation applied in an AVL tree to restore balance when an imbalance occurs in the left child's left subtree.

LR Rotation

A double rotation consisting of a left rotation followed by a right rotation, used to rebalance an AVL tree when an imbalance occurs in the left child's right subtree.

Max Heap

A complete binary tree where every parent node's key is greater than or equal to the keys of its children, placing the maximum key at the root.

Heapify Procedure

A recursive process used to restore the max-heap or min-heap property at a given node in $O(\log n)$ time.

Build Heap Procedure

An algorithm that converts an unordered array into a valid binary heap running with a tight time complexity bound of $O(n)$.

Chaining (Open Hashing)

A collision resolution technique where colliding keys are maintained in linked lists allocated outside the primary hash table array.

Load Factor ($\alpha$)

The ratio of total elements $n$ stored in a hash table to the total number of available slots $m$ ($\alpha = \frac{n}{m}$).

Primary Clustering

A performance issue in Linear Probing where consecutive occupied slots form large contiguous blocks, increasing search probe counts.

Secondary Clustering

A phenomenon in Quadratic Probing where keys that map to the identical initial slot follow the exact same secondary probing sequence.

Double Hashing

An open addressing collision resolution technique that uses a secondary hash function $h_2(k)$ to compute variable probe step intervals.