Data Structures and Algorithms in C++, Second Edition

Chapter 3. Arrays, Linked Lists, and Recursion

Contents

3.1 Using Arrays	104
3.1.1 Storing Game Entries in an Array	104
3.1.2 Sorting an Array	109
3.1.3 Two-Dimensional Arrays and Positional Games	111
3.2 Singly Linked Lists	117
3.2.1 Implementing a Singly Linked List	117
3.2.2 Insertion to the Front of a Singly Linked List	119
3.2.3 Removal from the Front of a Singly Linked List	119
3.2.4 Implementing a Generic Singly Linked List	121
3.3 Doubly Linked Lists	123
3.3.1 Insertion into a Doubly Linked List	123
3.3.2 Removal from a Doubly Linked List	124
3.3.3 A C++ Implementation	125
3.4 Circularly Linked Lists and List Reversal	129
3.4.1 Circularly Linked Lists	129
3.4.2 Reversing a Linked List	133
3.5 Recursion	134
3.5.1 Linear Recursion	140
3.5.2 Binary Recursion	144
3.5.3 Multiple Recursion	147
3.6 Exercises	149

Using Arrays

In this section, we explore a few applications of arrays—the concrete data structures introduced in Section 1.1.3 that access their entries using integer indices.

Storing Game Entries in an Array

The first application we study is for storing entries in an array; in particular, high score entries for a video game. Storing objects in arrays is a common use for arrays, and we could just as easily have chosen to store records for patients in a hospital or the names of players on a football team. Nevertheless, let us focus on storing high score entries, which is a simple application that is already rich enough ...