The Need for Efficiency
Explore the importance of efficiency in data structures by examining how performance scales with large data sets. Understand why straightforward implementations slow down searches and discover how carefully organized data can drastically reduce operation time, improving software performance.
We'll cover the following...
The operations supported by the most commonly used data structures are not hard to implement correctly. We can store the data in an array or a linked list. Each operation can be implemented by iterating over all the elements of the array or list and possibly adding or removing an element.
This kind of implementation is easy but not very efficient. Does this really matter? Computers are becoming faster and faster. Maybe the obvious implementation is good enough. Let’s do some rough calculations to find out.
Number of operations
Imagine an application with a moderately-sized data set, say of one million items. In most applications, it is reasonable to assume that the application will want to look up each item at least once. This means we can expect to do at least one million () searches in this data. If each of these searches inspects each of the ...
