# Application of Data Structure One interesting application is in sparse matrices, which makes an unimaginable difference in what is possible to compute on a very modest machine. Certainly the algorithm that Google uses for search would be impossible without them.

Basically, the idea is that instead of taking an N x N matrix and filling in zeros, you ignore the values that are zeros and only store non-zero elements. But for general matrices, it’s not always clear where the non-zero elements will be, so you can create an array representing the indices over columns, say, and then in each array element store a [sorted] linked-list. It’s pretty easy to see how this could speed up a matrix-vector multiplication algorithm because you aren’t calculating anything you don’t need to, i.e. if a matrix element is zero then it won’t contribute to the answer. And, again, it has taken exactly as much space as is required, so it is memory efficient too.

Stack: In operating systems stack is to stored memory locations when a function is called, when a function calls an another one the OS pushes the return address on the top, when the current routine returns it pops the memory location and the control jumps there. Think how recursive functions can be replaced with a stack?

Queue: While we work with a computer, several processes runs behind, each process wants to get some CPU time. Some process needs a lot of time, some need a very little time, some processes needs to processed very urgently. What OS does is to put them in a queue. There are different CPU allocation methods such as batch, time shared etc. In most cases priority queues are used.  Queues are used for job scheduling all the time in our operating system , for example while requesting for a document to be printed , it is added to the print queue of the printing device .

Linked List: Think about an selection sort algorithm, each time we find the element which needs to be put in the correct position we need to shift the entire elements by one position if we use an array. That could take a lot of time, instead if we use a linked list, all we need to update is 3 links. The major benefits of linked list is space saving over array since for array we must know in advance how many elements it is going to hold . For large application or software it’s not known in advance . Even though it’s known then we have to estimate maxm limit on input/ouput.

E.g.

a ) Let’s you are writing  a program to sort given numbers .

How to handle input ?
1 . You may assume input size would be maxm 10^6  and declare an array of this size
2. Use linked list  to store inputs

b) Other sorting problem :   Let’s input contains a database of employees
which includes { IDNumber , name (first , last , middle ) , salary , JoinDate } sort this database based on IDNumber . If we use array then we have to do lots of swap when input is in reverse order . But by using linked list it can be minimized .

More practical applications would be:

• A list of images that need to be burned to a CD in any imaging application
• A list of users of a website that need to be emailed some notification
• A list of objects in a 3D game that need to be rendered to the screen

Tree: Trees have a wide variety of applications, for example a binary tree is used in applications were a lot of searching needs to be done. This is a very simple example. Heap sort, which has minimal space complexity is implemented using a Tree. Applications range from systems programming to social networking websites. 