How to choose the best data structure to solve a problem.

1. Analyse your problem to determine the operations that must be suported. Examples may include inserting a data item into the data structure, deleting, and finding a specified data item.
2. Quantify the resource constraints for each operation.
3. Select the data structure that best meets these requirements.

This three-step approach to selecting a dsa operationalizes a data-centered view of the design process. The first concern is for the data and the operations to be performed on them, the next concern is the representation for those data, and the final concern is the implementation of that representation.
Resource constraints on certain key operations, such as search, inserting data records, and deleting data records, normally drive the data structure selection process.

• Are all data items inserted into the data structure at the beginning, or are insertions interspersed with other operations?
• Can data items be deleted? If so, this will probably make the implementation more complicated.
• Are all data items processed in some well-defined order, or is search for specific data items allowed? "Random access" search generally requires more complex data structures.

---

Example: A bank must support many types of transactions with its customers. From a database perspectice, we see that ATM transaction do not modify the database significantly. For simplicity, assume that if money is added or removed, this transaction simply changes the valued stored in an account record. Adding a new account to the database is allowed to take several minutes. Deleting an account need have no time constraint, because from the customer's point of view all that matters is that all the money be returned (equivalent to a withdrawal). Typically they are not willing to wait more than a brief time for individual account transactions such as a deposit or withdrawal.
When considering the choice of data structure to use in the database system that manages customer accounts, we see that a data structure that has little concern for the cost of deletion, but is highly efficient for search and moderately efficient for insertion, should meet the resource constraints imposed by this problem. Records are accessible by unique account number. One data structure that meets these requirements is the hash table. 

• Hash Tables allow for extremely fast exact-match search. A record can be modified quickly when the modification does not affect its space requirements.
• Hash Tables also support efficient insertion of new records.
• While **deletions **can also be supported efficiently, too many deletions lead to some degradation in performance for the remaining operations.
• However, the hash table can be reorganized periodically to restore the system to peak efficiency (search for load factor. Such reorganization can occur offline so as not to affect ATM transactions.