O'Reilly logo

Data Structures and the Java Collections Framework, Third Edition by William J. Collins

Stay ahead with the world's most comprehensive technology and business learning platform.

With Safari, you learn the way you learn best. Get unlimited access to videos, live online training, learning paths, books, tutorials, and more.

Start Free Trial

No credit card required

APPENDIX 3

Choosing a Data Structure

A3.1 Introduction

This appendix serves as a brief summary of much of the material from Chapters 68 and 1215. In particular, we will categorize the eight major collection classes (ArrayList, LinkedList, Stack, Queue1, 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 ...

With Safari, you learn the way you learn best. Get unlimited access to videos, live online training, learning paths, books, interactive tutorials, and more.

Start Free Trial

No credit card required