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 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.

Last update: 2014.

Table of Contents

 About This JDK Tutorial Book

 Downloading and Installing JDK 1.8.0 on Windows

 Downloading and Installing JDK 1.7.0 on Windows

 Downloading and Installing JDK 1.6.2 on Windows

 Java Date-Time API

 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

 Character Set Encoding Maps

 Encoding Conversion Programs for Encoded Text Files

 Socket Network Communication

 Datagram Network Communication

 DOM (Document Object Model) - API for XML Files

 SAX (Simple API for XML)

 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 - Secret Key Encryption and Decryption

 The SSL (Secure Socket Layer) Protocol

 SSL Socket Communication Testing Programs

 SSL Client Authentication

 HTTPS (Hypertext Transfer Protocol Secure)

 Outdated Tutorials

 References

 PDF Printing Version