6 Common data structures: List, Stack, and Queue

This chapter explains why built-in collections like List, Stack, and Queue are often a poor fit for data-oriented Unity code. Although they are convenient, they can hide expensive behavior such as dynamic resizing, data copying, extra branching, and memory fragmentation. The chapter emphasizes that arrays of primitive types are usually faster and more predictable because they preserve data locality, reduce garbage collection pressure, and make performance easier to reason about.

Using a simple enemy-spawning game as the example, the chapter shows how to replace a traditional List-based approach with explicit array-based structures. Alive enemies are tracked with an array of indices plus a count, while dead enemies are managed with a stack-like array so indices can be reused efficiently. Removal is handled by compacting arrays or copying data as needed, and the code is written directly rather than wrapped in abstraction, because the chapter argues that clarity about data movement matters more than mimicking familiar collection APIs.

The chapter also extends the idea to temporary data shared between logic and presentation. Instead of checking and updating every GameObject every frame, the logic layer records which enemies were added or removed in stack-allocated arrays, and the board uses that information to activate or deactivate only the necessary objects. A queue is discussed as a more general FIFO structure, but it is presented mainly as a contrast: if FIFO behavior is not required, a simpler stack-like or index-based array is usually better. Overall, the chapter’s message is that explicit, array-driven design gives better performance, better control over memory, and less hidden cost than relying on built-in collections.

The C# List data structure uses an array internally to manage its data. A linked list, on the other hand, is a collection of nodes spread across heap memory.

C# Lists use an array that is stored in a single contiguous block of memory, while Linked Lists allocate nodes wherever there is room, breaking data locality.

Dynamic list resizing requires copying, which affects performance and triggers garbage collection.

Removing an element at a specific index is done by copying over all the elements after the index.

Inserting a new element at a specific index requires copying all the elements after it to make room, which can be a very costly operation.

Results of incrementing an array and a List of 10,000 elements 10,000 times. The array was 6-8x faster than List.

In OOP, all our enemy data would be included in the Enemy object. To reference the data, we need a reference to the object. In DOD, our data is in arrays. To reference a specific enemy's data, we just need its index.

Removing a value from a list requires copying all the values over by one and changing the Length variable.

Changing the count value inside the loop can lead to unexpected bugs.

An example showing how our code removes the value 30 from the array with values 10, 20, 30, and 40. Count is only incremented for values that are not 30. Once we encounter the value 30, the count is smaller than i, and the values are effectively shifted left when copied over.

Array.Copy() can shift values to the left to remove a single value from an array.

To implement a queue using a circular array, we use two indices: start and end. If either index reaches the array limit, we reset it to the beginning. Start points to the first element added, which is 10. End points to the next empty index, the one after 40. When we dequeue, we output the first element (10), then increment start, so it now points to 20. When we enqueue 50, we write it at the current end index. Then we increment end. Since end has now reached the array limit, it wraps back to 0.

• Built-in data structures such as List, Stack, and Queue can hide implementation details that affect performance and memory management.
• Avoid using black-box code without understanding how it can affect performance and memory management.
• A List differs from a Linked List. List allocates data in a contiguous array, while a Linked List spreads data across memory, breaking data locality.
• In our increment benchmark, arrays were approximately 6–8 times faster than List across the devices tested.
• With DOD, we reference an object's data by index rather than by the object itself.
• Instead of adding a boolean array for branching, we can skip the branch check by creating multiple arrays that hold the indices of the relevant data. In our case, instead of using an aliveEnemy boolean array, we created two arrays, one to hold the indices of alive enemies and the other to hold the indices of dead enemies.
• When generating arrays that hold dynamic data, we create a separate integer to keep track of the count, so we know how much of the array's data is relevant.
• We want to pack our arrays so our data is always in a contiguous chunk, meaning we shift the data left whenever a variable is removed.
• We can use Array.Copy() to shift our array, but its performance depends on the size of the array that needs to be copied. It can slow our code if our arrays are large or if we remove multiple elements, which requires multiple shifts of small chunks of data.
• Instead of thinking about data structures, we should solve the problem at hand. That means sometimes avoiding helper functions for array manipulation.
• Every time we move code into a separate function, we increase complexity because we have to jump around the codebase to understand what is happening.
• Using helper functions can hide performance costs. For example, dequeuing from a circular Queue is more costly than popping from a Stack because the Queue needs to maintain a start index, an end index, a count, and wraparound checks.
• To visually show changes in Logic, we can use stack-allocated temporary arrays to track changes each frame.

FAQ