About the #data-structures series
Get the code on Github
The data structures in the series
- [x] Array
- [x] Hash Table
- [x] Set
- [x] Singly Linked List
- [x] Doubly Linked List
- [x] Stack
- [x] Queue
- [x] Tree
- [x] Binary Search Tree
- [x] Trie
- [x] Graph
What is a data structure?
Instead of trying to re-explain what a data structure is, I prefer to leave you with the perfect description wikipedia makes of it.
In computer science, a data structure is a particular way of organizing data in a computer so that it can be used efficiently. From Wikipedia
“used efficiently” here means that according to your needs. You may need for example an organizing structure that allows very fast lookup or it could be very fast insertion or any thing related to your application.
The key thing to remember is that each data structure has it own advantages and disadvantages. There isn’t any one of them that would beat all of the others, that’s the reason why it is important to know them all.
If you hear about data structures, you will for sure hear about their complexity. As said before every data structure has its own advantages and disadvantages, their complexity can be seen as a way of expressing their own advantages and disadvantages easily according to a specific problem.
The complexity is expressed on 2 axes, the space and the time.
The space complexity represents the memory consumption of a data structure. As for most of the things in life, you can’t have it all, so it is with the data structures. You will generally need to trade some time for space or the other way around.
The time complexity for a data structure is in general more diverse than its space complexity.
In contrary to algorithms, when you look at the time complexity for data structures you need to express it for several operations that you can do with data structures. It can be adding elements, deleting elements, accessing an element or even searching for an element.
Dependent on data
Something that data structure and algorithms have in common when talking about time complexity is that they are both dealing with data. When you deal with data you become dependent on them and as a result the time complexity is also dependent of the data that you received. To solve this problem we talk about 3 different time complexity.
- The best-case complexity: when the data looks the best
- The worst-case complexity: when the data looks the worst
- The average-case complexity: when the data looks average
The big O notation
The complexity is usually expressed with the Big O notation. The wikipedia page about this subject is pretty complex but you can find here a good summary of the different complexity for the most famous data structures and sorting algorithms.