O'Reilly logo

Data Structures and Algorithms in C++, Second Edition by David M. Mount, Roberto Tamassia, Michael T. Goodrich

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

Chapter 3. Arrays, Linked Lists, and Recursion

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 ...

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