Data Structures FM 11/5/02 9:28 AM Page xiv
xiv
Contents
Playing the Game . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 141
Comparing Performance . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 142
Comparing Size . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 144
Analysis of Multi-Dimensional Arrays in Games. . . . . . . . . . . . . . . . . . . . . . . 144
Conclusion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 145
Chapter 6
Linked Lists . . . . . . . . . . . . . . . 147
What Is a Linked List? . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 148
Singly Linked Lists . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 149
Graphical Demonstration: Singly Linked Lists. . . . . . . . . . . . . . . . . . . . . . . . . . . . 149
Structure . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 150
Example 6-4. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 168
Final Thoughts on Singly Linked Lists . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 169
Doubly Linked Lists . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 169
Graphical Demonstration: Doubly Linked Lists . . . . . . . . . . . . . . . . . . . . . . . . . . 170
Creating a Doubly Linked List . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 171
Doubly Linked List Algorithms . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 172
Reading and Writing Lists to Disk . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 174
Writing a Linked List . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 174
Reading a Linked List . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 175
Application: Game Inventories . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 176
The Player Class . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 177
The Item Class . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 177
Adding an Item to the Inventory . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 178
Removing an Item from the Inventory . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 178
Playing the Demo . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 179
Application: Layered Tilemaps Revisited . . . . . . . . . . . . . . . . . . . . . . . . . . . 180
Declaring the Tilemap . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 181
Creating the Tilemap . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 182
Drawing the Tilemap . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 182
Analysis and Comparison of Linked Lists . . . . . . . . . . . . . . . . . . . . . . . . . . 184
Algorithm Comparisons. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 184