Question

describe five data structures . What are the fundamental operations for eachdata structure?E.g., the fundamental operations of a stack are push and pop. Do not selection the stack, queue, double ended queue, singly linked list, or doubly linked list.There are hundreds of different data structures.

Answer 1

Arrays:- It is one of the most rudimentary data structure of all. It is the one that is taught for beginners who start to learn about any programming language or any data structures course. Maybe, it's this level of simplicity of arrays that a lot of peoples many times ignore how powerful it can become. Just for the sake of completeness let's start from the beginning.

An array is a linear data structure that contains data items of a similar type.

The greatest advantage it has over a lot of other data structures is that it has constant access time for the element at any index in the array, we just need to know where it is kept. Insertion is a bit complicated actually, if we are not keeping any order to our data elements then we can simply add a new element to the end of the array but if we are then first we have to shift all the elements of the array - starting from where the insertion is going to happen to the end of the array - one step forward, to make a place for new insertion.

Arrays are used in the implementation of many other data structures like heaps, binary trees, binary search trees, Hashing tables, & so on.

Using binary Search trees we can make the complexity of search O(log n). BST (binary search trees) which can be implemented using an array also eliminate the O(n) complexity problem of insertion we were having with arrays. Using Hashing we can make the average complexity of search to O(1) which is constant complexity. But just think of being able to find a record in constant time from a data set of which contains data in order of millions of records.

So array when used with the right technique can be very useful.

Trees:- A tree is another great data structure. It is just as simple as the name suggests. Here we have a root, which can have a lot of children, which can further have children until we reach a point where a node does not have any more children. Such a node is called a leaf node. In general, each node in a tree can have n children.

In more formal words, a tree data structure can be defined recursively as a collection of nodes, where each node is a data structure consisting of a value, together with a list of references to nodes, with the constraints that no reference is duplicated, and none points to root.

This is a generic definition of a tree, but we generally use that can have only 2 children, like a binary tree, BST, AVL trees, etc. These are used specifically because they eliminate some problems that other versions of a tree might have had in past.

For eg., Binary trees are not good for searching, to search we have to search the entire tree, then came BST which provided an ordering to the elements of the tree, and in the best case the searching of an element could be performed in O(log n) time. But in the worst case the complexity of searching was still O(n) (case of skewed trees), so remove that there came AVL trees, which even in the worst cast have the complexity of O(log n) for searching, & so on.

Similar to this there are a lot of versions of trees that are used for various applications. Some of them are XOR trees, red-black trees, splay trees, B trees, B+ trees, & so on.

What can a data structure like a tree be used for? Well, actually there a lot of application of tree data structure which can be used to show child-parent relationships. For eg.:- if a university offers a lot of courses, then we can find prerequisites for a course easily using a tree. B+ trees are widely used in the file storage systems used in our computers because they can search millions of records within a short period of time, and so on.

The insertion & deletion of elements in a tree is implementation-specific.

Graphs:- A Graph is also a good one. You see in trees we could only have had parent child relationships, i.e. a parent node could only be connected to it's child. It cannot then be connected to the children of it's child. But a graph lets us do that. Now, why would we wanna do that? This is because so that we could establish a direct relationship between the two nodes, as simple as that. The graph is a data structure that is used a lot today.

We see maps on our phones that are nothing just graph containing nodes that are separated from each other by the weight(distance between the nodes) of their edges (the lines connecting two nodes).

The graphs can also be used in representing relationships and determine possible relationships in social networking applications. For eg.:- On Facebook, you might have seen peoples you may know section, where it suggests a list of people that you might know. It does so with the help of a graph data structure. What it does (at least I like to think it works this way for a reason of explanation) is it sees the list of your contacts on FB that you communicate more fluently with, and then it sees who they talk to more fluently, & then it suggests you those people thinking that you might know those people (This is just a simple explanation, in reality, it will be using very complex and a lot of such conditions to find the peoples you might know).

The insertion and deletion operations in Graph also are representation specific. There are many methods to represent graphs, three of them are adjacency list, adjacency matrix & adjacency set.

Bloom Filter:- It is a probabilistic data structure that was designed to check whether an element is present in a set. That is it can tell about absence for sure but it cannot tell about its presence. I know sounds strange (at least that was my first reaction). Let's see a bit more closely.

How it works is quite simple actually, it starts off with an array that contains a lot of bits initialized to 0. To store a data value, we simply apply k different hash functions & treat the resulting k values as indices in the array, & we set each of the k array elements to 1. We repeat this for every element we encounter.

(Still don't understand just bear a little more with me, we're almost there).

Now suppose that we have a number and we want to check whether it is present in the set or not. What to do?

Simply apply the k hash functions & look up the indicated array elements.

• If anyone of them is 0 we can be 100% sure that we have never encountered the element before - if we had, the bit would have been stored to 1.
• However even if all of them are 1, we still can't conclude that we have seen the element before because all of the bits could have been set by the k hash functions applied to multiple other elements that we have inserted before. All we can say is that it is likely that we may have encountered the element.

It is crucial to understand that an element once added to the bloom filter cannot be removed. Since if we try to set a bit to 0 then it would be wrong since another no. might also have set it to 1.

I know after hearing this you would say what the heck? Why would anyone use such a dumb data structure like ever in their life, but it has its applications. The applications of bloom filters are:- Weak password detection, cybersecurity like virus scanning, wallet synchronization in Bitcoin, safe browsing in Google Chrome. Not so dumb after all huh.

Symbol Table:- Now I know you probably have guessed a lot just by listening to the name but still let me try to explain. So the Symbol table is a table of symbols with their values (you might have heard it as key-value pairs). It is as simple as that. Since childhood, we all have used a dictionary. It is just like that. It is a data structure that is used widely by language translators, such as compilers or interpreters, where each unique word (identifier - the key we were talking about) in a program's source code (nothing fancy just the code we write) is associated with information relating to its declaration or appearance in the source (the value for our key). It is just a table.

We can implement symbol tables in many ways such as using Hashing, unordered or ordered array implementation, ordered or unordered linked list implementation, BST implementation, and so on. Now for each, we know how to perform insertion and deletion so the complexity of these operations will depend on the complexity of insertion & deletion of data structure which is used for its implementation.

Hope this helps. If you like the answer please upvote. If you have any queries or suggestions regarding the answers please leave them in the comments section so I can update and improve the answer. Thank you