Explore tens of thousands of sets crafted by our community.
Data Structures Basics
10
Flashcards
0/10
Stack
Definition: A collection of elements with two principal operations: push and pop, which follow last in, first out (LIFO) principle. Operations possible: Push, Pop, Peek. Complexity of operations: Push - O(1), Pop - O(1), Peek - O(1).
Queue
Definition: A collection of elements that supports first in, first out (FIFO) principle. Operations possible: Enqueue, Dequeue, Peek. Complexity of operations: Enqueue - O(1), Dequeue - O(1), Peek - O(1).
Trie
Definition: A tree-like data structure that stores a dynamic set of strings in which each node represents a common part of one or more strings. Operations possible: Insertion, Search, Deletion. Complexity of operations: Insertion - O(m), Search - O(m), Deletion - O(m), where m is the length of the string.
Array
Definition: A collection of items stored at contiguous memory locations. Operations possible: Access, Insertion, Deletion. Complexity of operations: Access - O(1), Insertion - O(n), Deletion - O(n).
Hash Table
Definition: A data structure that implements an associative array, a structure that can map keys to values. Operations possible: Insert, Search, Delete. Complexity of operations: Insert - O(1), Search - O(1), Delete - O(1) on average.
Linked List
Definition: A sequence of nodes where each node is linked to the next node. Operations possible: Access, Insertion, Deletion. Complexity of operations: Access - O(n), Insertion - O(1), Deletion - O(1).
Graph
Definition: A collection of nodes (vertices) and the connections between them (edges). Operations possible: Add Vertex, Add Edge, Remove Vertex, Remove Edge. Complexity of operations: Depends on the representation (Adjacency matrix or adjacency list).
Binary Search Tree
Definition: A binary tree in which each node has two children at most and the left child's key is less than the parent's key, and the right child's key is greater. Operations possible: Search, Insertion, Deletion. Complexity of operations: Search - O(log n), Insertion - O(log n), Deletion - O(log n).
Heap
Definition: A specialized tree-based data structure that satisfies the heap property; either the parent is greater than or equal to the children (max heap) or lesser (min heap). Operations possible: Insertion, Deletion, Peek. Complexity of operations: Insertion - O(log n), Deletion - O(log n), Peek - O(1).
Red-Black Tree
Definition: A balanced binary search tree with each node colored red or black, following specific balance rules to ensure the tree remains approximately balanced. Operations possible: Search, Insertion, Deletion. Complexity of operations: Search - O(log n), Insertion - O(log n), Deletion - O(log n).
© Hypatia.Tech. 2024 All rights reserved.
