Updated: Jan 22, 2025 Author: Navdeep Singh
The most fundamental data structure. Arrays are stored contiguously in memory.
These also store an ordered list of elements, but the values are not contiguous in RAM. Linked list nodes have pointers connecting them.
Probably the most useful data structure as well. They use a hash function to map keys to indexes within an array. This allows us to have an amortized time of O(1) for most operations.
Typically used to process elements in the same order as they are added. These follow a FIFO (first-in first-out approach). Queues can be double-ended, which allow you to add and remove elements from both the front and the back.
A Binary Tree is an ordered tree data structure where each node is connected to at most two more nodes (called the left and the right child). Being ordered means we can perform DFS and BFS in O(log n) time.
Here, each node represents a character in the alphabet and can have at most 26 children. This allows us to save space when inserting words. Tries are useful for auto-complete features and allow us to search for words using their prefix.
Heaps are a nearly complete binary tree, with potentially the last level being not full. They are implemented with arrays under the hood. Heaps serve as priority queues, and always have the smallest (min-heap) or the largest (max-heap) item stored at the root node.
A graph is a bunch of nodes (vertices) connected by edges. Linked Lists and Trees are also special type of graphs, but a more general graph can have an arbitrary number of vertices connected to it. A good way to represent graphs in interviews is through an adjacency list.
