liveBook · Manning

Chapter 6: Common data structures: List, Stack, and Queue

What you will learn in chapter 6 of High Performance Unity Game Development

The introduction explains why arrays fit data-oriented design and why built-in collections, despite making dynamic changes easier, warrant scrutiny.

After this chapter you will be able to

What it builds on

Section by section

Introduction

The introduction explains why arrays fit data-oriented design and why built-in collections, despite making dynamic changes easier, warrant scrutiny.

Key terms: arrays of primitive types, data locality, L1 cache, object pools, arrays, List, Stack, Queue, data-oriented design, black-box code

6.1 C# List

Introduces what C# List provides for changing collections of enemies and flags potential memory and performance costs.

Key terms: C# List, index, dynamically, List, memory fragmentation, performance slowdowns

6.1.1 C# List vs Linked List

This section compares the memory layout and traversal performance of C# List and Linked List, then cautions that List’s convenient interface can conceal performance costs.

Key terms: C# List, Linked List, data locality, contiguous memory, nodes, List, GameData, EnemyPosition array, dynamic resizing

6.1.2 List and dynamic resizing

This section explains the performance costs of a List growing dynamically and how preallocating capacity avoids resize-related costs.

Key terms: List, dynamic resizing, garbage collector, preallocate, RemoveAt()

6.1.3 List and built-in functions

This section explains the copying and allocation costs hidden behind C# List insertion and removal helpers.

Key terms: List, Insert(), RemoveAt(), capacity, array

6.1.4 List and performance

This section compares List and array access performance, uses the result to argue for measuring built-in structures, and explains why compiler optimizations cannot replace simple, performance-conscious code.

Key terms: List, array, data-oriented design, built-in data structures, black-box code, garbage collector, compiler optimizations, SIMD instructions, arrays

6.1.5 Replacing List with an array

The section motivates replacing per-enemy alive checks with arrays of alive and dead enemy indices so enemies can be removed and respawned while retaining array-based data.

Key terms: data-oriented design, index, arrays, EnemyAlive, branch check, branch prediction, moveEnemies(), alive enemy array, dead enemy array, Stack

6.2 DOD List Implementation

This section introduces a preallocated array of alive enemy indices and a count that lets gameplay process only the indices currently in use.

Key terms: AliveEnemyIndices, GameData, EnemyPosition, AliveEnemyCount, preallocated size, Logic.AllocateGameData()

6.2.1 DOD Implementation of List.Add()

This section shows how to append an enemy index to an array-backed list and why the count must be incremented after it is used as the array index.

Key terms: List.Add(), AliveEnemyIndices, AliveEnemyCount, enemyIndex, spawnEnemy(), increment operator (++)

6.2.2 DOD implementation of List Remove()

This section explains how to remove enemy indices from a DOD array by compacting its values and updating its logical count.

Key terms: gameData.AliveEnemyIndices, gameData.AliveEnemyCount, count, enemyIndex, removeEnemy()

6.2.3 DOD List helper functions, or lack of

Explains why the DOD implementation uses explicit, problem-specific array manipulation instead of generic List-like helper functions.

Key terms: DOD, helper functions, abstractions, List, alive enemy indices, data structures

6.2.4 Array.Copy()

This section shows how Array.Copy() can remove one alive-enemy index by shifting later entries left, and when a manual loop is preferable.

Key terms: Array.Copy(), removeEnemy(), gameData.AliveEnemyIndices, enemyIndex, gameData.AliveEnemyCount, List.Remove(), first occurrence, AliveEnemyIndices

6.2.5 Using the AliveEnemyIndices array

The section changes enemy movement to process only alive enemies and explains why an unsorted index array can still benefit from cache locality.

Key terms: moveEnemies(), balance.NumEnemies, gameData.AliveEnemyCount, gameData.AliveEnemyIndices, enemyIndex, data locality, cache line, L1 cache, main memory

6.3 DOD stack implementation

The section shows how to reuse dead enemy indices with a simple array-backed stack instead of a FIFO queue.

Key terms: DeadEnemyIndices, Stack, Queue, first-in, first-out (FIFO), DeadEnemyCount, enemyIndex, push, pop, removeEnemy()

6.4 Queue

This section explains when FIFO order matters and how a fixed-size circular array can implement a queue without shifting stored values.

Key terms: Queue, Stack, FIFO, LIFO, circular array, queueStart, queueEnd, queueCount, enqueueing, dequeuing

6.5 Putting it all together

6.5.1 Adding the alive and dead indices arrays to GameData

This subsection adds enemy-status arrays and a spawn timer to GameData to support dynamic spawning and dying.

Key terms: GameData, alive enemy indices, dead enemy indices, GameData.SpawnTime, Balance.SpawnTime, delta time, Tick()

6.5.2 Allocating the alive and dead indices arrays

This subsection explains how large to make the alive and dead enemy-index arrays and why both need the full capacity.

Key terms: Balance.NumEnemies, alive and dead indices arrays

6.5.3 Initializing the alive and dead indices arrays

Explains how StartGame() initializes the alive and dead enemy index arrays and their counts before enemies spawn.

Key terms: StartGame(), GameData.AliveEnemiesCount, GameData.DeadEnemyIndices, GameData.DeadEnemyCount, balance.NumEnemies, Stack

6.5.4 Spawning and positioning enemies

The section updates enemy spawning and out-of-bounds removal to use alive and dead index arrays, while avoiding skipped enemies and temporary heap allocations.

Key terms: spawnEnemy(), removeEnemy(), alive enemy indices array, dead enemy indices array, AliveEnemyIndices, AliveEnemyCount, temporary array, Span<int>, stackalloc, stack

6.6 Visualizing enemy changes on the board

The section explains why the Board needs per-frame enemy changes, rather than current alive/dead lists alone, and why temporary change arrays suit that job.

Key terms: AliveEnemyIndices, DeadEnemyIndices, AliveEnemyCount, Board, Logic, addedEnemyIndices, removedEnemyIndices, GameObjects, GameData, Board.Tick()

6.6.1 Allocating temporary arrays in the Board

Board.Tick() prepares stack-allocated temporary arrays to track enemy indices added and removed during a frame.

Key terms: Board.Tick(), Span<int>, stackalloc, enemy indices, Logic

6.6.2 Populating the addedEnemyIndices array

This section shows how spawning an enemy records its index in a temporary array for newly added enemies.

Key terms: spawnEnemy(), Tick(), Span<int>, addedEnemyIndices, enemyIndex, addedEnemyCount

6.6.3 Populating the removedEnemyIndices array

The section records removed enemy indices, passes them to the board, and uses added and removed indices to keep enemy GameObjects visually in sync with gameplay.

Key terms: removeEnemy(), removedEnemyIndices, removedEnemyCount, enemyIndex, Board.Tick(), addedEnemyIndices, addedEnemyCount, GameObject, Board.Show(), StartGame()

6.7 Conclusion

The section concludes that purpose-built arrays and index-based data can replace general-purpose collections while keeping gameplay logic separate from visual updates.

Key terms: List, Stack, Queue, data locality, dynamic growth, circular Queue, index, GameData, arrays of indices, Logic

6.8 Summary

The summary draws together the chapter’s performance lessons about built-in collections, index-based arrays, and problem-specific array operations.

Where this is used later

Concepts explained in this chapter

← Chapter 5: Game board and game loop Chapter 7: Separating data and logic →

These guides are generated from the text of Manning books by Manning's knowledge graph and link to the sections they draw on. The full books are available on liveBook and at manning.com.