Up to this point, we have created various objects, and you have learned the intricacies of object-oriented programming: encapsulation, inheritance, and polymorphism. After we have our objects defined we're going to have to do something meaningful with them.
Consider, for example, storing a collection of employees where the unique differentiator is the employee's Social Security number. We can store each employee in sequential order by his Social Security number, but what is that going to look like in memory? Are we going to block out enough memory to store 1,000 employees, and then insert them in sequential order? What happens when we have 500 records filled, and we have a new employee with a low Social Security number, are we going to move all 500 records down in memory and insert the new record at the beginning? Or, do we create a mapping that knows the location of each object? These are some of the questions we are going to have to answer when determining how to store collections of objects.
When considering the operations we will have to perform on a collection of objects, the main three are
Adding a new object
Removing an object
Finding an object
We must determine how a new object will be added to the collection. It can be added at the end of the collection, at the beginning, or at some logical location in the middle.
After we remove an object from our collection, how does that affect the existing objects in the collection? Memory might have to be shifted around, or we can just leave an empty hole where the existing objects used to reside.
After we have a collection of objects in memory, we must determine how we are going to locate a specific object. We might have a mechanism to go directly to the object we want based on some search criteria (such as a security number), or we might need to traverse every object in the collection until we find the one we are looking for.
To answer each of these questions, computer scientists have designed containers that hold objects in different forms.