chapter six

6 Common data structures: List, Stack, and Queue

 

This chapter covers

  • How built-in data structures like List, Stack, and Queue can negatively affect our performance.
  • Implementing common data structures like List, Stack, and Queue using data-oriented design.
  • Using stack-allocated arrays to pass data from Logic back to the Board.

So far, we have been using arrays of primitive types to store our data. We use arrays for two main reasons. First, they are allocated in a contiguous chunk of memory, which helps us practice data locality and maximizes the chance that our data will be in the L1 cache. Second, we can treat them similar to object pools, avoiding both memory fragmentation and triggering the garbage collector.

If you haven’t caught on yet, data-oriented design is all about using arrays, preferably arrays of primitive types. Arrays are great when we have a set amount of data, like a fixed number of enemies. But what happens when we want to add and remove enemies from an array dynamically? Languages like C# offer built-in data structures, for example, List, that make it easy to add and remove elements.

Unfortunately, popular data structures, including built-in ones like List, Stack, and Queue, don’t align well with data-oriented design. Using them can cause significant performance penalties, and they are detrimental to memory management.

6.1 C# List

6.1.1 C# List vs Linked List

6.1.2 List and dynamic resizing

6.1.3 List and built-in functions

6.1.4 List and performance

6.1.5 Replacing List with an array

6.2 DOD List Implementation

6.2.1 DOD Implementation of List.Add()

6.2.2 DOD implementation of List Remove()

6.2.3 DOD List helper functions, or lack of

6.2.4 Array.Copy()

6.2.5 Using the AliveEnemyIndices array

6.3 DOD stack implementation

6.4 Queue

6.5 Putting it all together

6.5.1 Adding the alive and dead indices arrays to GameData

6.5.2 Allocating the alive and dead indices arrays

6.5.3 Initializing the alive and dead indices arrays

6.5.4 Spawning and positioning enemies

6.6 Visualizing enemy changes on the board

6.6.1 Allocating temporary arrays in the Board

6.6.2 Populating the addedEnemyIndices array

6.6.3 Populating the removedEnemyIndices array

6.7 Conclusion

6.8 Summary