This section describes different types of data structures that can be used to implement collections: Array, Linked List, Binary Tree, and Hash Table. Implementing collections with different data structures will have different performance impacts.
In the previous section, we only talked about the functionalities of collections,
and divided collections into 3 types based on the differences in their
functionalities. In the section, we will look at what kind of data structures
we are going to use to store the data elements. Choosing any data structure
to implement a collection should not affect the accuracy of its functionalities,
but it will affect the performance.
There 4 major types of data structures that can be used in the implementation
of collections: array, linked list, binary tree, hash table.
Before going into any details on each data structures, we need to clarify one
thing: when a user wants to store a data element into a collection, we only
need to store the reference number of that data element in the collection.
The reference member of a data element is usually the memory address where
that data element is actually stored.
Array: Reference numbers of data elements are stored consecutively in
the memory, one immediately after another.
Linked List: Reference numbers of data elements are stored randomly
in the memory, but they are linked with a pointer associated with each reference
number pointing to the next reference number.
Binary Tree: Reference numbers of data elements are stored randomly in the
memory, but they are linked with two pointers associated with each reference
number pointing to two other reference numbers.
Hash table: Reference numbers of data elements are stored in one single section
of memory. The exact location of the each reference number is based the hash number
obtained from the data element.
Of course, I am only giving a rough description for each data structure here. For
more details, please read any data structure text book.
