While i was studying The Algorithm Design Manual by Skienna and i have came across a sentence that says:
We use the term container to denote a data structure that permits storage and retrieval of data items independent of content.
My question is what is container? Which data structure is a container and what is the differrence from other data structures? Is it a collection type like list, dictionaries or is it differrent? What does these mean permits storage and retrieval of data items independent of content?
The container has a classic definition here:
In computer science, a container is a class, a data structure, or an abstract data type (ADT) whose instances are collections of other objects. In other words, they store objects in an organized way that follows specific access rules. The size of the container depends on the number of objects (elements) it contains. Underlying (inherited) implementations of various container types may vary in size and complexity, and provide flexibility in choosing the right implementation for any given scenario.
Hence, the answer is:
Container abstract data types include:
- FIFO queues
- LIFO stacks
- Priority queues
- Arrays and their derivatives
- Linked lists
- Lookup tables (LUTs)
- Key-associated data structures
- Sets, containing and indexing objects by value or by specific property;
- Maps, associating to each key a "value" for lookup
- Binary search trees (BSTs), particularly self-balancing BSTs
- Hash tables