Data Structures and Algorithms
91 flashcards by MentisLibrary
Arrays, trees, graphs, hashing, sorting, and searching, each with the time and space complexity you are expected to know cold. Built for interview prep and for finally understanding why one structure beats another.
- Array
- A fixed-size block of contiguous memory holding elements of the same type, addressed by integer index.
- Dynamic array
- A resizable array that allocates a larger backing buffer and copies elements over when it fills up.
- Amortized analysis
- Averaging the cost of an operation over a long sequence of operations, so an occasional expensive step is spread across many cheap ones.
- Singly linked list
- A chain of nodes where each node stores a value and a pointer to the next node.
- Doubly linked list
- A linked list whose nodes point to both the next and the previous node.
- Why is array insertion at the front O(n)?
- Every following element must shift one slot to the right to keep the elements contiguous.
- Stack
- A last in, first out (LIFO) collection with push, pop, and peek.
- Queue
- A first in, first out (FIFO) collection with enqueue at the back and dequeue at the front.
- Deque
- A double ended queue supporting insert and remove at both ends in constant time.
- Circular buffer
- A fixed-size array used as a ring, with head and tail indices that wrap around using modulo.
- Hash table
- A structure that maps a key to a bucket index by applying a hash function, giving near constant time lookup.
- Hash collision
- Two distinct keys hashing to the same bucket index.
- Separate chaining
- A collision strategy where each bucket holds a secondary structure, usually a linked list, of all entries that hashed there.
- Open addressing
- A collision strategy that stores every entry in the table itself and probes for the next free slot.
- Load factor
- The ratio of stored entries to buckets in a hash table.
- Set
- A collection of unique elements with fast membership testing and no defined order in the hash-based form.
- Binary tree
- A tree in which every node has at most two children, called left and right.
- Binary search tree (BST)
- A binary tree where every key in the left subtree is smaller than the node, and every key in the right subtree is larger.
- In-order traversal
- Visit the left subtree, then the node, then the right subtree.
- Pre-order traversal
- Visit the node first, then the left subtree, then the right subtree.
- Post-order traversal
- Visit the left subtree, then the right subtree, then the node.
- Level-order traversal
- Visit nodes level by level from the root down, using a queue.
- Self-balancing tree
- A BST that restructures itself on insert and delete so its height stays O(log n).
- AVL tree
- A self-balancing BST that keeps the height difference between any node's two subtrees at most 1.
- Red-black tree
- A self-balancing BST that colors nodes red or black and enforces rules keeping the longest path at most twice the shortest.
- B-tree
- A balanced tree where each node holds many keys and has many children, designed so one node fits one disk page.
- Trie (prefix tree)
- A tree where each edge is a character, so a path from the root spells a prefix shared by everything below it.
- Heap
- A complete binary tree satisfying the heap property: every parent compares favorably to its children.
- Priority queue
- A queue that dequeues the highest-priority element rather than the oldest, typically implemented with a heap.
- Heapify
- Building a heap from an unordered array by sifting down every non-leaf node from the bottom up.