World's most popular travel blog for travel bloggers.

[Solved]: Where can I find information on Data Structures used in common software?

, , No Comments
Problem Detail: 

As part of a course I am teaching on Data Structures, I want students to research and present the use of Data Structures in popular software/services. However, basic googling shows me that this information is not so readily available.

Can someone point me to the right resources that I may share with the students as a starting point for their research?


Judging from the received replies, the original question is not sufficiently clear so I am adding more details.

I am looking for resources of the type that state, for example, that service-x uses data-structure-a in order to perform functionality-y because of property-b. This is the ideal case. Other resources that provide similar information are also welcome.

Asked By : wsaleem

Answered By : Pseudonym

Off the top of my head:

Every modern operating system uses balanced binary search trees to implement the virtual memory map of a process. Windows uses splay trees, Linux and OS X use red-black trees, and Solaris uses AVL trees. They do this because the operating system needs to store the virtual memory map in order (by virtual address), to allow for fast insertion and removal, and to look for unused regions where it could allocate space.

Many modern 3D games (e.g. anything which uses a recent version of Unreal Engine) use octrees to determine what objects are visible to the camera. They do this because it's quite efficient to calculate what nodes overlap with a camera's view frustum.

Many (if not most) routers use radix trees to implement routing tables. They do this because it is often the prefix of a network address (i.e. the most significant bits) which is important, not the whole key. Moreover, lookup takes time which only depends on the size of the address, not the number of routing table entries, which makes predicting timing easier.

Hash tables are, of course, used everywhere. Antivirus software uses it to perform lookups in its database of known malware, word processors use it to perform spelling checks, etc.

Graph data structures are used by spreadsheets to implement evaluation. Think of each occupied cell as a node, and draw an arc between to cells if the value of one directly depends on the value of the other. When an entry changes in a cell, the graph is traversed to determine which cells need updating based on that change.

Best Answer from StackOverflow

Question Source :

3.2K people like this

 Download Related Notes/Documents


Post a Comment

Let us know your responses and feedback