---

Some contents of the Book

Introduction

• The Need for Efficiency
• Interfaces
  • The Queue, Stack, and Deque Interfaces
  • The List Interface: Linear Sequences
  • The USet Interface: Unordered Sets
  • The SSet Interface: Sorted Sets
• Mathematical Background
  • Exponentials and Logarithms
  • Factorials
  • Asymptotic Notation
  • Randomization and Probability
• The Model of Computation
• Correctness, Time Complexity, and Space Complexity
• Code Samples
• List of Data Structures
• Discussion and Exercises

Array-Based Lists

• ArrayStack: Fast Stack Operations Using an Array
  • The Basics
  • Growing and Shrinking
  • Summary
• FastArrayStack: An Optimized ArrayStack
• ArrayQueue: An Array-Based Queue
  • Summary
• ArrayDeque: Fast Deque Operations Using an Array
  • Summary
• DualArrayDeque: Building a Deque from Two Stacks
  • Balancing
  • Summary
• RootishArrayStack: A Space-Efficient Array Stack
  • Analysis of Growing and Shrinking
  • Space Usage
  • Summary
  • Computing Square Roots
• Discussion and Exercises

Linked Lists

• SLList: A Singly-Linked List
  • Queue Operations
  • Summary
• DLList: A Doubly-Linked List
  • Adding and Removing
  • Summary
• SEList: A Space-Efficient Linked List
  • Space Requirements
  • Finding Elements
  • Adding an Element
  • Removing an Element
  • Amortized Analysis of Spreading and Gathering
  • Summary
• Discussion and Exercises

Skiplists

• The Basic Structure
• SkiplistSSet: An Efficient SSet
  • Summary
• SkiplistList: An Efficient Random-Access List
  • Summary
• Analysis of Skiplists
• Discussion and Exercises

Hash Tables

• ChainedHashTable: Hashing with Chaining
  • Multiplicative Hashing
  • Summary
• LinearHashTable: Linear Probing
  • Analysis of Linear Probing
  • Summary
  • Tabulation Hashing
• Hash Codes
  • Hash Codes for Primitive Data Types
  • Hash Codes for Compound Objects
  • Hash Codes for Arrays and Strings
• Discussion and Exercises

Binary Trees

• BinaryTree: A Basic Binary Tree
  • Recursive Algorithms
  • Traversing Binary Trees
• BinarySearchTree: An Unbalanced Binary Search Tree
  • Searching
  • Addition

Book Overview

This book dives deep into various data structures, including lists, trees, and graphs. Each chapter focuses on a specific structure, detailing its implementation in C++. Morin emphasizes the importance of efficiency and performance. He includes numerous code snippets to help readers grasp the concepts better. The book also covers algorithms associated with each data structure. This hands-on approach makes learning enjoyable and effective.

Why Read This Book

The author says

There are plenty of books that teach introductory data structures. Some of them are very good. Most of them cost money, and the vast majority of computer science undergraduate students will shell out at least some cash on a data structures book. Several free data structures books are available online. Some are very good, but most of them are getting old. The majority of these books became free when their authors and/or publishers decided to stop updating them.

Updating these books is usually not possible, for two reasons: (1) The copyright belongs to the author and/or publisher, either of whom may not allow it. (2) The source code for these books is often not available. That is, the Word, WordPerfect, FrameMaker, or LATEX source for the book is not available, and even the version of the software that handles this source may not be available.

The goal of this project is to free undergraduate computer science students from having to pay for an introductory data structures book. I have decided to implement this goal by treating this book like an Open Source software project. The LATEX source, C++ source, and build scripts for the book are available to download from the author’s website1 and also, more importantly, on a reliable source code management sit

Who This Book Is For

This book is ideal for students and professionals alike. If you are studying computer science, this book will enhance your knowledge. It is also suitable for software developers looking to deepen their understanding of data structures. Whether you are a novice or an experienced programmer, you will find value in this text.

What You Will Learn

• How to implement various data structures in C++.
• Techniques for optimizing performance and efficiency.
• Practical applications of algorithms related to data structures.

Report Broken Link

File Copyright Claim