Data structures are essential in creating efficient and powerful Algorithms, As a self-taught-dev, I've always struggled with Data structures.
So Here's a mini-tutorial & some basic concepts of Data Structures.
What is a data structure?
A Data Structure is a way of Organising data so it can be used efficiently.
Why do we need to know Data structures?
- They help us manage and organize our data in a very natural way
- They are essential in creating efficient and powerful Algorithms
- They make your code cleaner😁
Before we dive into basic concepts of Data Structures we need to talk about the concept of ABSTRACT DATA TYPE which is an important concept of Data Structures
What is an Abstract Data Type?
An Abstract Data Type is an abstraction of a data structure that provides only the interface to which the data structure must ADHERE.
Some examples of the abstract data types are:
List: Lists can be implemented in two ways, You can have a dynamic Array or a Linked List because they both provide a way of adding, removing, and indexing elements on the list.
Another example is a map Abstraction which can also be implemented in two ways:
- Treemap
Hash map / Hash Table
We Use Treemap and Hash Map in Map abstraction because they both have a method of displaying hierarchical data.
Another way to think of an Abstract data type is as a mode of transportation, Some modes of transportation might be walking, taking a train, or even flying a jet😆... These specific modes of transportation would be analogous to the data structures themselves.
We wanted to get from one place to another through a mode of transportation that was our Abstract data type. The mode of transportation we used exactly is what our data structure is right there.
As Programmers, we often find ourselves asking the same two questions over and over again... Which is how much time does this algorithm takes to finish? And How much space does this Algorithm needs for its computation, That's where Complexity Analysis comes in?
What is complexity Analysis?
Complexity analysis is a technique to characterize the time taken by an algorithm concerning the input size (independent from the machine, language, and compiler).
If your program takes a too long time to finish then it’s no good and similarly if your program runs in constant time but requires too much space your algorithm is no good as well.
To Standardise a way of talking about how much space and time is required for an algorithm to run, Theoretical computer scientists have invented what we call The BIG-O notation.
Big-O Notation
Big-O Notation gives an upper bound of the complexity in the worst case, Helping to quantify performance as the input size becomes arbitrarily large.
Big-O is also known as Order of Magnitude of Complexity
So let’s say your Algorithms sorts numbers, Imagine the input as the worst possible arrangement of numbers for your particular sorting Algorithms, Suppose you have an unordered list of number and you’re searching for the number 8 then the worst case isn’t when the number eight is at the beginning of the list or in the middle of the list but It’s when eight is the very last number of the list.
For that particular example, the time complexity would be linear with the respect to the number of elements in the list, Because you’ll have to go through every single element until you find eight.
The same concept also applies to SPACE you could just consider the worst possible amount of space your algorithm is going to need for that particular input.
There’s also the fact that Big-O only cares about what happens when your input becomes arbitrarily large, We’re not really interested in what happens when the input is small
We're done! 🥳 🎉
So that's it!!, Thank you for making it through this long post!!!😂❤️