JDK Tutorials - Herong's Tutorial Examples - v6.32, by Herong Yang
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.
Of course, I am only giving a rough description for each data structure here. For more details, please read any data structure text book.
Table of Contents
Date, Time and Calendar Classes
Date and Time Object and String Conversion
Number Object and Numeric String Conversion
Locales, Localization Methods and Resource Bundles
Calling and Importing Classes Defined in Unnamed Packages
►HashSet, Vector, HashMap and Collection Classes
Types of Collections of Elements
►Data Structures of Collection Implementations
Collection Implementations in JDK
Search Operation Performance of Different Collection Classes
Comparable Interface and compareTo() Method
Character Set Encoding Classes and Methods
Encoding Conversion Programs for Encoded Text Files
Datagram Network Communication
DOM (Document Object Model) - API for XML Files
DTD (Document Type Definition) - XML Validation
XSD (XML Schema Definition) - XML Validation
XSL (Extensible Stylesheet Language)
Message Digest Algorithm Implementations in JDK
Private key and Public Key Pair Generation
PKCS#8/X.509 Private/Public Encoding Standards
Digital Signature Algorithm and Sample Program
"keytool" Commands and "keystore" Files
KeyStore and Certificate Classes
Secret Key Generation and Management
Cipher - Encryption and Decryption
The SSL (Secure Socket Layer) Protocol
SSL Socket Communication Testing Programs