DEV Community

Cover image for Complete Introduction to the 30 Most Essential Data Structures & Algorithms

Complete Introduction to the 30 Most Essential Data Structures & Algorithms

Iulia Groza on September 03, 2020

Data Structures & Algorithms (DSA) is often considered to be an intimidating topic - a common misbelief. Forming the foundation of the most inn...
Collapse
 
xtofl profile image
xtofl

A gigantic work.

Being a C++ nerd, I have to correct: std::map has logarithmic access complexity (mandated by the standard, e.g. see cppreference). If you're looking for a constant complexity data structure, the 'hashmap' is std::unordered_map.

Collapse
 
iuliagroza profile image
Iulia Groza

Thank you, well pointed out! I haven't noticed I considered the map's access operation to be done in O(1) (in the Maps presentation photo). As you've highlighted the logarithmic complexity, maps are indeed implemented using self-balancing trees (mentioned it in the properties). Going to fix my mistake.

Collapse
 
codinglanguages profile image
Your DevOps Guy

Amazing compilation, congrats!

I think this article is a natural continuation of yours, where I show many problems that can be solved with these data structures and algorithms.

Collapse
 
iuliagroza profile image
Iulia Groza

Definitely! Congrats, well-chosen techniques!

Collapse
 
goodevilgenius profile image
Dan Jones

I'm no expert on this, so I may be mistaken, but I believe there's a mistake in your Binary Search Tree diagram.

Binary Search Tree

Shouldn't the 20 be to the left of the 21, rather than the left of the 38?

Collapse
 
iuliagroza profile image
Iulia Groza

Oh, I'm so sorry! It was a typo. It was 30 instead of 20 in my initial thread. Thank you for noticing! Fixed it! :)

Collapse
 
codinglanguages profile image
Your DevOps Guy

You are right. Everything to the right of 21 should be greater (or equal to, if the tree contains duplicates) than 21.

Good catch!

Collapse
 
itsraghz profile image
Raghavan alias Saravanan Muthu

Wonderful piece of art Lulia :) Thanks for sharing. Really need time to digest this. :)

Collapse
 
anzhari profile image
Anzhari Purnomo

I am brushing up my DSA skills again recently, and this is really useful. Appreciate the huge effort. 🔥💯

Collapse
 
adminha profile image
adminha

Nice post, If you don't mind, I'm going to use some of your content to write an article on devban.com/. Of course, with respect to copyrights and mentioning you as one of the sources.

Collapse
 
phantas0s profile image
Matthieu Cneude

Holy cow. That's an impressive article. I'm curious: did you learn all of that by yourself or did you do some CS studies?

Collapse
 
iuliagroza profile image
Iulia Groza

Thank you! Focusing on DSA was a must because I took part in the National Olympiad in Informatics in high school, and it was definitely worth it :) .

Collapse
 
ohdylan profile image
Dylan Oh

Good stuffs, thanks for the effort.

Collapse
 
rightdroid profile image
Toomas Jaska • Edited

This is incredibly useful. Thanks for this!

Collapse
 
danieluhl profile image
Typing Turtle

This is really great, lots of stuff I've never heard of before. How did you create the diagrams?

Collapse
 
iuliagroza profile image
Iulia Groza

Thanks! I use Adobe Spark.

Collapse
 
badrilee profile image
Badri Lee

Thanks...!

Collapse
 
programmerbyday profile image
Arman @programmerByDay

That was quite thorough.. especially the algorithms section

Collapse
 
memnoch91 profile image
Andrei Tosa

Hei Iulia, amazing work and I've grateful to you for it.

I think you have a small miss-calculation at chapter 5 Maps & Hash Tables, there are only 1440 minutes in a day otherwise you meant something else by the 3600 minutes.

Collapse
 
iuliagroza profile image
Iulia Groza

Huh, someone's missed their Maths classes 😂 . Thanks for reporting such errors! It's pretty hard to review such a big volume of information and readers' support is essential!

Collapse
 
jjant profile image
Julian Antonielli

You don't need pre-image resistance for a Map's hash function, that's a cryptographic hash.

Collapse
 
donmathi profile image
Kjeld Mathias Petersen

I came across a nice special tree algorithm, maybe it could fit into your list
levelup.gitconnected.com/the-white...

Collapse
 
iuliagroza profile image
Iulia Groza

Well-written article! I see a white-grey-black tree is quite similar to an AVL. Thanks for the suggestion! I will definitely consider adding it into a new article.

Collapse
 
jcarlosr profile image
Juan Ramos

Thank you for organizing and presenting the information very well!
May I translate your article to Spanish and add a link to it please?

Collapse
 
iuliagroza profile image
Iulia Groza

Sure, that would be a great idea! I kindly ask you to give me credits and let me know when it is done :)

Collapse
 
nerd profile image
Dhananjay Panage

I really liked reading this, but if I am not mistaken the worst time complexity of BST for insertion, deletion and searching is O(n) and not O(log n).

Collapse
 
geekystar profile image
Geeky-Star

I liked your post, if anyone want to learn data structures, here is a good opportunity you should check out-

geeks-terrace.blogspot.com/2020/11...

Collapse
 
muhamma42867932 profile image
Muhammad Shahab

Use this link leetcode.com/tag/hash-table/ for practices Hash Table.