Data Structures of Collection Implementations

JDK Tutorials - Herong's Tutorial Examples

∟HashSet, Vector, HashMap and Collection Classes

∟Data Structures of Collection Implementations

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 are 4 major types of data structures that can be used in the implementation of collections: array, linked list, binary tree, and 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.