Data Structure Guide

The ultimate Data Structure quick reference for developers and solutions architects.

• Arrays:
  • Contiguous memory storage for elements.
  • Time complexity: O(1) for access, O(n) for search and insertion (in worst case).
  • Create an array by specifying the size and data type.
• Linked Lists:
  • Nodes connected by pointers.
  • Time complexity: O(n) for access, O(1) for insertion and deletion (at head/tail).
  • Create a linked list by Define a Node structure with a data field and a next pointer.
• Stacks:
  • LIFO (Last-In, First-Out) structure.
  • Time complexity: O(1) for all operations.
  • Using an array or linked list, implement push and pop operations accordingly.
• Queues:
  • FIFO (First-In, First-Out) structure.
  • Time complexity: O(1) for all operations.
  • Using an array or linked list, implement enqueue and dequeue operations accordingly.
• Hash Tables:
  • Key-value pairs with efficient lookup.
  • Time complexity: O(1) for average case, O(n) in worst case.
  • Define an array or linked list to store key-value pairs, implement hash functions to map keys to indices.
• Trees:
  • Hierarchical structure with parent-child relationships.
  • Time complexity: O(log n) for search, insertion, and deletion (in balanced trees).
  • Define a Node structure with a data field and child pointers, and link nodes together.
• Binary Trees:
  • Trees with at most two children per node.
  • Time complexity: O(log n) for search, insertion, and deletion (in balanced trees).
  • Define a Node structure with a data field and left/right child pointers, and link nodes together.
• Binary Search Trees:
  • Sorted binary trees for efficient search.
  • Time complexity: O(log n) for search, insertion, and deletion (in balanced trees).
  • Node structure with a data field and left/right child pointers, and implement insertion and search operations to maintain the sorted order.
• AVL Trees:
  • Self-balancing binary search trees.
  • Time complexity: O(log n) for search, insertion, and deletion.
  • Node structure with a data field, left/right child pointers, and balance factor, and implement self-balancing operations during insertion and deletion.
• Red-Black Trees:
  • Self-balancing binary search trees with color properties.
  • Time complexity: O(log n) for search, insertion, and deletion.
  • Node structure with a data field, left/right child pointers, color property, implement operations to maintain the red-black properties during insertion and deletion.
• B-Trees:
  • Balanced trees for efficient disk-based storage.
  • Time complexity: O(log n) for search, insertion, and deletion.
  • Node structure with data fields, child pointers, and key ranges, and implement split and merge operations to maintain the B-tree properties.
• Heaps:
  • Trees with highest (or lowest) priority element at the root.
  • Time complexity: O(log n) for insertion, deletion, and finding the maximum/minimum.
  • Using an array and implement heapify operations to maintain the heap property.
• Graphs:
  • Vertices connected by edges.
  • Time complexity: Varies depending on the algorithm used.
  • Define a set of vertices and their connections (edges), and use adjacency lists or matrices to represent the relationships between vertices.
• Tries:
  • Tree-like structures for efficient string lookup.
  • Time complexity: O(m) for search, insertion, and deletion (m is the length of the string).
  • Node structure with child pointers for each character, and implement operations to insert and search strings efficiently.
• Bloom Filters:
  • Probabilistic data structures for membership queries.
  • Time complexity: O(k) for insertion and lookup (k is the number of hash functions).
  • Bit array and a set of hash functions, and implement operations to insert and query elements for membership.
• Skip Lists:
  • Linked lists with multiple layers for efficient search.
  • Time complexity: O(log n) for search, insertion, and deletion.
  • Node structure with data fields and multiple levels, and implement operations to insert, search, and delete nodes at various levels.
• Hash Chaining:
  • Collision resolution technique using linked lists.
  • Time complexity: O(1) for average case, O(n) in worst case.
  • Hash table with chaining by Define an array or linked list of buckets, and implement hash functions and collision resolution through linked lists.
• Priority Queues:
  • Data structures with priority-based ordering.
  • Time complexity: O(log n) for insertion, deletion, and finding the maximum/minimum.
  • Binary heap or other suitable data structure, and implement operations to insert and extract the highest (or lowest) priority element.
• Disjoint Sets (Union-Find):
  • Efficiently manage disjoint sets.
  • Time complexity: Nearly O(1) for all operations (with union by rank and path compression).
  • Define a set of elements and implementing operations like union and find to manage sets and their relationships.
• Hash Maps:
  • Key-value pairs with hash-based lookup.
  • Time complexity: O(1) for average case, O(n) in worst case.
  • Define an array or linked list of buckets, and implement hash functions and collision resolution mechanisms to store and retrieve key-value pairs.
• Doubly Linked Lists:
  • Linked lists with previous and next pointers.
  • Time complexity: O(n) for access, insertion, and deletion.
  • Node structure with data, previous, and next pointers, and link nodes together accordingly.
• Circular Linked Lists:
  • Linked lists where the tail points to the head.
  • Time complexity: O(n) for access, insertion, and deletion.
  • Node structure with data and next pointers, and ensure the last node points back to the first node.
• Self-balancing Trees:
  • Trees that maintain balance during operations.
  • Time complexity: O(log n) for search, insertion, and deletion.
  • Node structures and implement balancing operations during insertions and deletions.
• Splay Trees:
  • Self-adjusting binary search trees.
  • Time complexity: O(log n) amortized for search, insertion, and deletion.
  • Node structure with data, left/right child pointers, and parent pointers, and implement operations to maintain the splay property during insertions, deletions, and searches.
• Fenwick Trees:
  • Efficient range query data structures.
  • Time complexity: O(log n) for query and update operations.
  • An array to store cumulative sums and implementing update and query operations to efficiently calculate prefix sums.
• Segment Trees:
  • Data structures for range-based queries.
  • Time complexity: O(log n) for query and update operations.
  • Node structure with data fields and child pointers, and implement build, update, and query operations to efficiently handle range-based queries.
• Trie Trees:
  • Specialized trees for efficient string operations.
  • Time complexity: O(m) for search, insertion, and deletion (m is the length of the string).
  • Node structure with child pointers for each character, and implement operations to insert, search, and delete strings efficiently.
• Radix Trees:
  • Space-optimized trie-like structures.
  • Time complexity: O(m) for search, insertion, and deletion (m is the length of the string).
  • Node structure with child pointers for each character or digit, and implement operations to insert, search, and delete strings efficiently using radix-based traversal.
• Suffix Trees:
  • Data structures for efficient substring search.
  • Time complexity: O(m) for search, insertion, and deletion (m is the length of the string).
  • Node structure with child pointers, and implement operations to construct the tree from a given string and efficiently search for substrings.
• Queue With Two Stacks:
  • Implementing queues using stacks.
  • Time complexity: O(1) for all operations.
  • Queue using two stacks by implementing push and pop operations on the stacks and managing the elements in a way that emulates a queue.
• Deque (Double-Ended Queue):
  • Supports insertion and deletion at both ends.
  • Time complexity: O(1) for all operations.
  • An array or linked list, and implement operations to add or remove elements from both ends efficiently.
• Sparse Matrix:
  • Efficient representation of matrices with mostly empty cells.
  • Time complexity: Varies depending on the operation and representation used.
  • Data structure that only stores non-zero elements and their positions, and implement operations to efficiently access and manipulate matrix elements.