Do you want to feel Data Structures?: A Kinda Roadmap
Hello Coders, I am Domino and I am here with my computer expert Rubics. I am here to discuss “Data Structure”.
Before we begin, let me tell you guys where it all begins. As you all know that I decided to learn Competitive coding this year. ( You know why)
Now I am stuck and Confused about Data Structure.
Domino: Rubics, Buddy, there are too many data structures and I don’t know if they are language-dependent or just universal. I have so many doubts regarding Data Structure like how we can read them, why we need any perticular data structure like a Link list or something. Please solve my quries buddy…
Rubics: I understand your problem Domino. It happens with every beginner. The path is not clear or even sometimes, they don’t know Why we need any DS. So, Don’t worry, let me go through all DS and explain their need. I also make sure, you learn them in a roadmap model.
So guys, Let’s start today’s Blog with
What is Data Structure?
No seriously, I am not going to discuss what Google says. Let’s understand them in this manner.
Data structure sounds like, any data which has some kind of structure. For example, an array can have the structure of symmetric datatype (int for example). So, basically, a data structure holds more than one value with some kind of rule and helps us to perform various tasks.
Domino: Rubics, Which data structure should I learn, and is data structures are language-dependent?
No, Data Structures are not language-dependent, why do you think that data structures are language-dependent?
Domino: Actually, When I was learning Python, I don’t see Array or Linked List. I learn List, Tuple etc.
Ohh…Yes, Most people think like that, actually, data structures are not language-dependent, they are concepts. There are various reasons you don’t see Arrays or LinkedList in Python:
- Python is an Interpreter based language due to which memory management is different and Most of the things are dynamic.
- In Python, they actually use all basic data structures like an array or Linked list but in the background, the List, Tuple, or Dictionary uses basic data structures like a linked list, Heap in the background.
RoadMap Of Data Structure
Domino: Okay Rubics, Now I get what is Data Structure and your explanation is completely different. I kinda like it. But Now, Please give me a roadmap or Topics or data structure that I must know to start in competitive coding.
Before I explain all basic data structures, If you are a Python/JS developer, you may not need these data structures in your python career but knowing them is best for you, as it enhances your knowledge.
Python/JS has its own data structures like objects, arrays, lists, etc which perform quite advanced operations.
We are going to cover the C language Data structure, after all, C is our mother language.
- Array
- Structure/Union
- Stack
- Queue
- Linked List
- Tree
- Graph
Note: I am not including a string in this list as in some languages, it is treated as a Data type. In some, it is a class or library but most of its behavior is similar to Array.
In this article, I only explain why we need them, what is the problem in the last Data structure, and their use case. For knowing in deep, stick with us. We are planning to write all data structures one by one in the next few weeks.
Array:
- Arrays are defined as the collection of similar types of data items stored at contiguous memory locations.
- Arrays are the derived data type in C programming language which can store the primitive type of data such as int, char, double, float, etc.
- Array is the simplest data structure where each data element can be randomly accessed by using its index number.
Why We Need Them:
The main problem with Datatypes is that they can’t hold multiple data in a single variable that's why we need arrays.
The benefit of using Array:
you can store as much value as you want. You don’t need lots of variables to store similar values.
Structure/Union:
Structure or union are similar to arrays but they also store different types of data type values whereas arrays can only store similar data type values.
Why We Need Them:
The array can only store similar types of values, for example, they can only store either marks(int) or names(string) but they can’t store both in a single variable that’s why we need Structure/Union.
For more read.
Stack:
- Stack is a linear data structure that follows the LIFO (Last In First Out) approach for accessing elements.
- Push, pop, and top (or peek) are the basic operations of a stack.
Why We Need Them:
The problem with the array is that if you have to add an item at last or you have to fetch any item at last (and you don’t know the length of the array), then you have to traverse the whole array.
But in the stack, we always know the index of the last item, it will be easy for us to insert(push) or delete(pop) the last item.
Applications of a stack:
- Check for balanced parentheses in an expression
• Evaluation of a postfix expression
• Problem of Infix to postfix conversion
• Reverse a string
QUEUE:
- A queue can be defined as an ordered list that enables insert operations to be at one end called REAR and delete operations to be performed at another end called FRONT.
• Queue is referred to be as the FIFO(First In First Out) list.
• For example, people waiting in line for a rail ticket form a queue.
Why We Need Them:
The problem with the stack is that we only get the last value, but what if we got a problem where we have to pick an item from the first place and insert any item at last. The stack can only help us insert data at last.
Here we keep track of the first item index and last item index. Insert is called as Enqueue and deletion is called as Dequeue.
Note: There is a memory problem with the simple queue that's why you also learn other versions like a circular queue.
LINKED LIST:
- A linked list is a data structure that has a sequence of nodes where every node is connected to the next node by means of a reference pointer.
- The elements are not stored in adjacent memory locations. They are linked using pointers to form a chain. This forms a chain-like link for data storage.
- Each node element has two parts: a data field and a reference (or pointer) to the next node.
Why We Need Them:
The problem with the array, stack, or queue is that when we have to add or remove any item in the middle of the array then we need to perform a complete swap, which also increases our computation.
The benefit of using a Linked List is that every node is very flexible, you can remove it or connect any new node very easily in the linked list without performing any swapping.
Note: There are various problems with the simple linked list that’s why you also learn other versions like a doubly link list.
TREE:
- A tree is also one of the data structures that represent hierarchical data.
- A tree data structure can be defined recursively as a collection of nodes, where each node is a data structure consisting of a value and a list of references to nodes.
- The start of the tree is the “root node” and the reference nodes are the “children”.
Why We Need Them:
This is a bit interesting, a tree is basically used to increase searching and sorting operations. All the data structures, we have read till now are slow in case of search or sorting. Think about any sorting technique, it always takes O(n²) times. But tree takes approx O(log n) time.
Now I think you get why we need Trees. There are various types of trees. We are planning to post a descriptive article about Trees next Monday. so, keep following us.
GRAPH:
• A graph can be defined as a group of vertices and edges that are used to connect these vertices.
• A graph can be seen as a cyclic tree, where the vertices (Nodes) maintain any complex relationship among them instead of having a parent-child relationship.
Graph G(V. E) with 5 vertices (A, B, C, D, E) and six edges ((A,B), (B,C), (C,E), (E,D), (D,B), (D,A)) is shown in the above figure.
Why We Need Them:
The graph is something you need to learn despite the language. Lots of programming problems are solved using graphs. For example, Uber/Swiggy uses graphs to figure out best and fastest route.
Conclusion:
Domino: It seems alot to me, but now i understand that, I need to start from Array and learn till graph. Rubics can you provide me order to learn DS.
There is no such order for learning DS. I already told you, why you need any DS. What is the problem with the last DS so that we need a new one? But Still read something like that:
Array -> Structure -> Union -> Stack -> Queue -> Linked List -> Tree -> Graph -> Heap
About Us:
About us:
Follow us on medium to get a complete journey topic by topic or follow on Facebook, Quora, LinkedIn or connect with the community on Facebook. Read our other blogs.
Read: Want to get started with Data Structure
Read: Walk like a Snake: A Python Beginners Roadmap
Read: Let’s Draw a Roadmap for Competitive Coding
If you are a beginner, you can start testing your coding skill in our code lab.
Thank you for reading, Please support in comments for queries, suggestions, or appreciation.
See You Soon!!
