References

https://www.geeksforgeeks.org/direct-address-table/

Concept

A direct address table is a collection of key-value pairs, implemented through an array. We're going to create an array with the size of out data's maximum value. So, this said, our data must have some integer value, because we need to use integers as keys (or something that can be converted to an integer).

Example:

https://s3-us-west-2.amazonaws.com/secure.notion-static.com/6e988edd-7938-489e-b50a-3202ba84f451/example.png

Here, our data has the RollNumber property, which has an integer value. We're using the RollNumber value as the key for our direct address table. So, we have another conclusion: our data must have an unique integer value to be used as a key to our structure.

Advantages:

  1. Searching in O(1) time: Direct address tables use arrays which are random access data structure, so, the key values (which are also the index of the array) can be easily used to search the records in O(1) time.
  2. Insertion in O(1) time: We can easily insert an element in an array in O(1) time. The same thing follows in a direct address table also.
  3. Deletion in O(1) time: Deletion of an element takes O(1) time in an array. Similarly, to delete an element in a direct address table we need O(1) time.

Limitations:

  1. We need to know, from the start, the maximum value of whatever we're going to use as a key.
  2. If the maximum value is very high, we can run out of memory (or, at least, have a performance problem).
  3. It causes wastage of memory space if there is a significant difference between our total records and our maximum value. For example:
    1. Imagine a software for a board game. In our board game, we're going to have 3 players and, for each player, it's position (on the board). Our positions goes from 1 to 60, and it's going to be used as our key.
    2. In this scenario, we're going to have only 3 records for 60 positions in our array. We're going to have, always, 57 empty slots (and it would be a big waste of memory).