22.6. Static Methods for Lists and Collections
The Goddess Chalchihuitlicue, found in the Valley of Mexico, 1300-1500 AD (stone), Aztec / Muse de l'Homme, Paris, France / Bridgeman Art Library
The design and implementation of efficient data structures is an important subject in computer science. Data structures such as lists, stacks, queues, sets, maps, heaps, and binary trees have many applications in compiler construction, computer operating systems, and file management. Java provides the data structures for lists, stacks, sets, and maps in the collections framework. This part of the book introduces the main subjects in a typical data structures course. You will learn the concepts and implementation of several popular data structures in Chapter 20, "Lists, Stacks, Queues, Trees, and Heaps," JDK 1.5 generics in Chapter 21, "Generics," the Java collection framework in Chapter 22, "Java Collections Framework," and finally, algorithm efficiency and sorting algorithms in Chapter 23 "Algorithm Efficiency and Sorting."
[Page 658] Prerequisites for Part 5
All the chapters after Chapter 16, "Applets and Multimedia," are designed with minimal dependencies so that they can be reordered flexibly.
Chapter 20 , "Lists, Stacks, Queues, Trees, and Heaps," can be covered after Chapter 10, "Abstract Classes and Interfaces."
Chapter 21 , "Generics," can be intertwined with Chapter 11, "Object-Oriented Design."
Chapter 22 , "Java Collections Framework," can be covered after Chapter 11, "Object-Oriented Design," and Chapter 21, "Generics."
Chapter 23 , "Algorithm Efficiency and Sorting," can be covered after Chapter 19, "Recursion."
| |||
| |||
| |||
| |||
Chapter 20. Lists, Stacks, Queues, Trees, and Heaps
Mayan God Shel, Mexico. Photographer: Philip Coblentz. Courtesy Brand X Pictures.
Objectives |
|
20.1. Introduction
A data structure is a collection of data organized in some fashion. A data structure not only stores data, but also supports the operations for accessing and manipulating data in the structure. For example, an array is a data structure that holds a collection of data in sequential order. You can find the size of the array, and store, retrieve, and modify data in the array. Arrays are simple and easy to use, but they have two limitations: (1) once an array is created, its size cannot be altered ; (2) an array does not provide adequate support for insertion and deletion operations. This chapter introduces dynamic data structures that grow and shrink at runtime. ArrayList , introduced in 9.9, are examples of dynamic data structures. You have used this class. You will learn how to design and implement it in this chapter.
Five classic dynamic data structures are introduced in this chapter: lists, stacks, queues, binary trees, and heaps. A list is a collection of data stored sequentially. It supports insertion and deletion anywhere in the list. A stack can be perceived as a special type of list where insertions and deletions take place only at one end, referred to as the top of the stack. A queue represents a waiting list, where insertions take place at the back (also referred to as the tail) of the queue, and deletions take place from the front (also referred to as the head) of the queue. A binary tree is a data structure that supports searching, sorting, inserting, and deleting data efficiently . A heap is a data structure that can be used to develop efficient sorting and priority queue algorithms.
In object-oriented thinking, a data structure is an object that stores other objects, referred to as data or elements. Some people refer to data structures as container objects or collection objects . To define a data structure is essentially to declare a class. The class for a data structure should use data fields to store data and provide methods to support such operations as insertion and deletion. To create a data structure is therefore to create an instance from the class. You can then apply the methods on the instance to manipulate the data structure, such as inserting an element into the data structure or deleting an element from the data structure.
The focus of this chapter is to introduce the design and implementation of the interfaces and classes for data structures: lists, stacks, queues, binary trees, heaps, and priority queues. These are classic data structures typically covered in a data structures course. Lists, stacks, queues, and heaps are supported in the Java API. Chapter 22, "Java Collections Framework," introduces how to use these data structures in the Java API. Some useful applications of data structures are provided in Supplement Part 3 on the Companion Website. Since knowledge of implementing data structures is not required for learning the Java collections framework, this chapter is designed independently of Chapter 22 and therefore can be skipped .
EAN: N/A
Pages: 503