Data Structures Flashcards
Grade 11 · Technology · Flashcards
Key terms, definitions, and complexity facts for arrays, linked lists, stacks, queues, trees, and hash tables.
Flashcards
- Data Structure
- A way of organizing and storing data to enable efficient access and modification.
- Array
- Contiguous memory block; O(1) access by index, O(n) insertion/deletion in the middle.
- Singly Linked List
- Each node holds a value and a pointer to the next node; O(1) head insert, O(n) search.
- Doubly Linked List
- Each node holds a value, a next pointer, and a previous pointer; O(1) deletion given a node reference.
- Stack
- LIFO structure; supports push (add) and pop (remove) at the top in O(1).
- Queue
- FIFO structure; supports enqueue at the back and dequeue from the front in O(1).
- Deque
- Double-ended queue; O(1) insert and delete at both front and back.
- Binary Search Tree
- Tree where left subtree < node < right subtree; average O(log n) search, insert, delete.
- Balanced BST
- A BST that maintains O(log n) height through rotations (e.g., AVL, Red-Black trees).
- Hash Table
- Maps keys to values via a hash function; average O(1) lookup, insert, delete.
- Heap
- Complete binary tree satisfying heap property; O(log n) insert and extract-min/max.
- Graph
- A set of vertices connected by edges; used to model networks, relationships, and paths.
- Big O Notation
- Describes the upper-bound growth rate of an algorithm's time or space relative to input size n.
- Amortized O(1)
- An operation that occasionally takes longer but averages to O(1) over many calls (e.g., dynamic array append).
- Collision (hash table)
- Two keys hash to the same index; resolved by chaining (linked list per bucket) or open addressing.
Get a personalized course on Data Structures built around your child.