Linear Data Structures with Built-in Libraries
A DS is linear DS if its elements form a linear sequence, i.e. elements are arranged from left to right(or top to bottom).
Mastery of these is very very critical:
Static Array
Most commonly used DS. The maximum input size is usually mentioned in the problem statement. The array size is declared to be the maximum input size with a small extra buffer for safety.
Typical array operations include accessing elements by their indices, sorting elements, performing a linear scan, or a binary search on a sorted array. Here is the link to problems to practice Static Arrays
Dynamically-Resizeable Array: C++ STL vectors (or Java ArrayList)
Here is the link to revise vectors.
Similar to a static array, except that can handle runtime resizing.
Usually, we initialize the size(reserve() or resize()) with estimated size of the collection for better performance.
The most common operation applied to vectors and arrays are sorting and searching. It is good to know about basic sorting and searching algorithms. Here is the link to learn about them: sorting and searching among elements.
Array of Booleans: C++ STL bitsets(or Java BitSet)
If you need an array but want to store only Boolean values in it (true/false or 0/1), one can use a C++ STL bitset. Here is the link to learn bitset.
Bitmasks
A small sets of Booleans. As an integer is stored as a sequence of bits. We can use integers to represent(lightweight) a small set of Booleans.
Using bitmasks is much more efficient than $vector<bool>$ or $bitset$ or $set<int>$ options if all that you want to do is set operations like AND, OR, XOR, etc. Her is a link if you want to learn bitmasking.
Note that it is not a new DS. We are just using integers as a string of bits.
Here are the links you can use to learn the Linked Lists and C++ STL list:
Linked Lists:
Note that it is not a new DS. We are just using integers as a string of bits.
Linked Lists: C++ STL list(Java LinkedList)
Here are the links you can use to learn the Linked Lists and C++ STL list:
Linked Lists:
- https://rishabhjainiitbhu.blogspot.com/2019/07/singly-linked-linked-list-in-c-using.html
- https://rishabhjainiitbhu.blogspot.com/2019/07/singly-linked-lists-contd.html
And C++ STL: Lists:
Stacks: C++ STL stack(Java Stack):
Here are the links you can use to learn the Stacks and C++ STL stack:
Stacks:
C++ STL stacks:
Queue: C++ STL queue(Java Queue)
Here are the links you can use to learn about Queues and C++ STL queue:
Queue:
C++ STL queue:
No comments:
Post a Comment