10 Common Data Structures Explained with Videos + Exercises

As a developer, having a solid grasp of data structures is crucial. Data structures provide a way to organize and store data efficiently so that it can be accessed and worked with easily. Choosing the right data structure for the problem at hand can have a huge impact on the performance and maintainability of your code.

In this article, we‘ll take a look at 10 commonly used data structures every developer should know. For each data structure, I‘ll give a high-level overview and then link to resources like videos and practice problems for digging deeper.

We‘ll also do a deep dive into one versatile data structure that doesn‘t always get the attention it deserves – sets. By the end, you‘ll have a solid understanding of the strengths and use cases of various data structures and be well prepared to efficiently tackle coding challenges and real-world problems.

The Top 10 Data Structures

Here are the data structures we‘ll cover:

  1. Linked Lists
  2. Stacks
  3. Queues
  4. Sets
  5. Maps
  6. Hash Tables
  7. Binary Search Tree
  8. Trie
  9. Heap
  10. Graph

Don‘t worry if these sound intimidating – I‘ll explain each one in simple terms with examples. Let‘s start with a quick rundown of each and then we‘ll explore sets in more detail.

Linked Lists

A linked list consists of a series of "nodes" where each node contains data and a pointer to the next node. This allows for efficient insertion and deletion but searching is slow. Linked lists are useful for things like stacks and queues.

Stacks

A stack follows a "last in, first out" (LIFO) approach. Think of a stack of plates – you can only take a plate from the top, which is the last one you put there. Adding an item is called "pushing" and removing is called "popping". Stacks are used for things like undo/redo and function call history.

Queues

Queues are similar to stacks but use a "first in, first out" (FIFO) approach, like waiting in line. Items are added to the back of the queue and removed from the front. Queues are used for things like task scheduling and breadth-first search.

Maps

Maps store key-value pairs, where each key must be unique. You can quickly retrieve a value if you know its key. Maps are useful for things like caches and lookups.

Hash Tables

Hash tables are a way to implement maps. The keys are run through a hash function to determine where to store the value, allowing for very fast lookups. Handling hash collisions is the main challenge.

Binary Search Tree

In a BST, each node has at most two "child" nodes. Starting at the root node, each left child is smaller and each right child is larger. This structure allows for fast searching, insertion, and deletion. BSTs are commonly used for things like sorted data and lookups.

Trie

A trie, or prefix tree, stores data as a series of nodes that each represent a letter. Walking down the trie spells out words or keys. Tries are often used for quick prefix lookups, like autocomplete.

Heap

A heap is another tree structure where each node is greater than (max heap) or less than (min heap) its children. This allows for fast retrieval of the maximum or minimum value. Heaps are used in priority queues and heap sort.

Graph

Graphs store nodes and the edges/connections between them. Graphs can be directed (one-way relationships) or undirected (two-way). They‘re used for modeling networks, geography, and relationships.

Now that you have a high-level view, let‘s take a closer look at sets.

Sets: The Unsung Hero

A set is a data structure that stores unique values, with no regard for order. If you try to add a value that already exists in the set, the duplicate will be ignored. This makes sets perfect for tracking things like collections, memberships, and de-duplication.

Here are the key operations and concepts for sets:

  • Add: Insert a new item into the set
  • Remove: Delete an item from the set
  • Contains: Check if the set contains a given item
  • Union: Create a new set with all the items from two sets
  • Intersection: Create a new set containing only the items found in both sets
  • Difference: Create a new set with items that are in one set but not the other
  • Subset: Check if every item in one set is also in another set

Let‘s look at an example to make this concrete. Say you have two sets, A and B:

A = {1, 2, 3, 4, 5}
B = {2, 4, 6} 

Here‘s how the various operations would work:

  • Union of A and B: {1, 2, 3, 4, 5, 6}
  • Intersection of A and B: {2, 4}
  • Difference of A and B: {1, 3, 5}
  • B is a subset of A: False

You can efficiently implement these operations using a hash table where each item is a key and the value is a dummy variable (often 1 or True). This allows for fast lookups to check if an item exists.

Here‘s what the implementation of a set might look like in Python:

class Set:
  def __init__(self):
    self.items = {}

  def add(self, item):
    self.items[item] = True

  def remove(self, item):
    if item in self.items:
      del self.items[item]

  def contains(self, item):
    return item in self.items

  # Other methods like union, intersect, difference...

So when would you use a set? Here are some common scenarios:

  • Eliminating duplicates: Sets only allow unique values, so converting a list to a set is an easy way to remove any duplicates
  • Membership testing: Sets allow for fast lookups to check if an item is present
  • Finding shared or distinct items: Need to see which items two groups have in common or what makes them different? The union and intersect operations have you covered

For a visual explanation of sets, check out this video: Sets Data Structure

And here are some practice problems to help you get comfortable working with sets:

Wrapping Up

We‘ve covered a lot of ground! To recap, here are the key things to take away:

  • Data structures allow you to efficiently organize and work with data
  • Knowing the strengths and use cases of different data structures will help you choose the best one for the task at hand
  • Sets are a powerful but often overlooked data structure that every developer should be familiar with
  • The best way to solidify your understanding is to practice implementing and using the data structures yourself

I encourage you to review the linked resources and try the practice problems. And don‘t forget to bookmark this page as a handy reference.

Feel free to reach out if you have any questions! Happy coding!

Similar Posts