When you dive into almost any advanced data structure, you'll find that it all comes back to arrays.

Arrays are the building blocks that make so much possible in computing, even though they don't always get the spotlight. They're simple, efficient, and form the foundation of many complex structures we rely on every day.

Let's take a closer look:

Hash Tables

At first glance, hash tables might seem intricate, but at their core, they're just arrays. The magic lies in the hash function, which determines where to store or find each item within the array. This allows for average-case constant-time lookups—an incredibly powerful feature for efficient data retrieval.

Dynamic Arrays (like Python Lists or Java ArrayLists)

Dynamic arrays give the impression of flexibility, but underneath, they're regular arrays that resize as needed. When the array reaches capacity, a new, larger array is allocated, and existing elements are copied over. The "magic" here is the resizing and copying process that happens behind the scenes, providing the illusion of infinite scalability.

Btw, let me introduce myself: I'm an ex-FAANG Senior Software Engineer who has conducted hundreds of coding interviews, currently on sabbatical. You can get free daily coding interview tips from me straight to your inbox by subscribing to my newsletter called Faangshui here: blog.faangshui.com. Let's also connect on Linkedin! Now let's get back to arrays...

Heaps

Often used to implement priority queues, heaps are essentially binary trees stored in—you guessed it—arrays. Parent-child relationships are managed through simple index calculations:

• Parent of index i: (i - 1) // 2
• Left child of i: 2 * i + 1
• Right child of i: 2 * i + 2

This structure allows for efficient insertion and deletion operations while maintaining the heap property.

Tries

Tries are excellent for storing strings, especially when dealing with prefix queries like autocomplete features. Each node in a trie typically contains an array (or map) of pointers to its child nodes, each representing a character. This setup enables fast and efficient searches by traversing the array of pointers corresponding to each character in the input string.

Graphs (Adjacency Matrices)

When representing a graph using an adjacency matrix, you're essentially using a two-dimensional array to keep track of connections between nodes. Each cell in the matrix indicates whether a pair of nodes is connected (and possibly the weight of that connection). This method is straightforward and works particularly well for dense graphs.

If you like this kind of articles, consider subscribing to my daily newsletter: blog.faangshui.com