Data Structures and the Java Collections Framework, Third Edition

APPENDIX 3

Choosing a Data Structure

A3.1 Introduction

This appendix serves as a brief summary of much of the material from Chapters 6–8 and 12–15. In particular, we will categorize the eight major collection classes (ArrayList, LinkedList, Stack, Queue¹, TreeMap, PriorityQueue, HashMap, Network) from those chapters in two different ways. The first classification will be by the ordering of the elements in the collection: time-based, index-based, comparison-based and hash-based. The second classification will be by the time to perform common operations on an element in the collection: access, insertion, deletion and search. For each such operation, averageTime(n) will be provided, that is, the average time (assuming each event is equally likely) to perform the operation in a collection of n elements. Whenever the estimate of averageTime(n) differs from the corresponding estimate for worstTime(n), both estimates will be given.

A3.2 Time-Based Ordering

For applications that utilize a time-based ordering, elements are removed from the collection in the same order they were inserted (First In, First Out), or in the reverse of that order (Last In, First Out). In the first case, an instance of the LinkedList class (Section 8.2.2) is appropriate, and an instance of the Stack class (Section 8.1) is called for in the second case.

For a LinkedList object, accessing the front element takes constant time, as does inserting at the back and deleting from the front. To search for a specific element ...