Skip to main content

Distributed for Athabasca University Press

Open Data Structures

An Introduction

Offered as an introduction to the field of data structures and algorithms, Open Data Structures covers the implementation and analysis of data structures for sequences (lists), queues, priority queues, unordered dictionaries, ordered dictionaries, and graphs. Focusing on a mathematically rigorous approach that is fast, practical, and efficient, Morin clearly and briskly presents instruction along with source code.

Table of Contents

Acknowledgments- xi

Why This Book?- xiii

1. Introduction- 1

            1.1 The Need for Efficiency- 2

            1.2 Interfaces- 4

            1.3 Mathematical Background- 9

            1.4 The Model of Computation- 18

            1.5 Correctness, Time Complexity, and Space Complexity- 19

            1.6 Code Samples- 22

            1.7 List of Data Structures- 22

            1.8 Discussion and Exercises- 26

2. Array-Based Lists- 29

            2.1 ArrayStack: Fast Stack Operations Using an Array- 30

2.2 FastArrayStack: An Optimized ArrayStack- 35

2.3 ArrayQueue: An Array-Based Queue- 36

2.4 ArrayDeque: Fast Deque Operations Using an Array- 40

2.5 DualArrayDeque: Building a Deque from Two Stacks- 43

2.6 RootishArrayStack: A Space-Efficient Array Stack- 49

2.7 Discussion and Exercises- 59

3. Linked Lists- 63

            3.1 SLList: A Singly-Linked List- 63

            3.2 DLList: A Doubly-Linked List- 67

            3.3 SEList:

Be the first to know

Get the latest updates on new releases, special offers, and media highlights when you subscribe to our email lists!

Sign up here for updates about the Press