Unity Development: Don’t Use Lists for Everything! (Part 1)

Unity developers often default to using lists for collections, but this approach isn’t always the most efficient or effective. While lists offer simplicity and direct access to elements, they may not be the optimal choice for all scenarios. Understanding when to use different data structures like Linked Lists, Stacks, and Queues can significantly impact the performance and functionality of your Unity projects.

Understanding Linked Lists in Unity

Before discussing when and how to use Linked Lists in Unity, it’s crucial to understand what a LinkedList is and how it differs from other collection types like arrays and lists.

What is a LinkedList?

A Linked List is a dynamic data structure that consists of a sequence of elements, each linked to the next. It’s a collection of nodes, where each node contains two (or three) parts:

1. Data: The actual value or object stored in the node.
2. Next Reference: A pointer or link to the next node in the sequence.
3. Previous Reference: A pointer or link to the previous node in the sequence (in the case of a Doubly Linked List).

In C#, the LinkedList<t> is actually a doubly linked list, so the previous-reference link applies.

Unlike arrays and lists, where elements are indexed and stored in contiguous memory locations, the elements in a Linked List are scattered throughout memory and connected through links. This structure has several implications for performance and usability:

• Dynamic Size: The size of a Linked List is not fixed and can grow or shrink dynamically, so it doesn’t need to allocate more memory than it uses.
• Efficient Insertions and Deletions: Adding or removing elements from a Linked List doesn’t require shifting other elements (as with arrays or lists), making these operations more efficient in large collections.
• No Direct Element Access: Unlike arrays, Linked Lists do not allow direct access by index. To access an element, you must traverse from the start (or end, in a doubly linked list).

When to Use Linked Lists in Unity

Linked Lists are particularly useful in Unity when dealing with collections that undergo frequent modifications, such as adding or removing items. Common use cases include:

• Managing Dynamic Game Elements: When you frequently add or remove objects—like enemies, items, or particles—Linked Lists can outperform lists or arrays.
• Complex Data Structures: When building trees, graphs, or other structures, Linked Lists serve as a flexible foundation for node management.
• Game State Management: Useful for undo/redo systems or state history, where bidirectional traversal is beneficial.

Example: Using LinkedList Instead of List

Suppose we have an Enemy class and these enemy game objects are managed by an EnemyController class.

// Enemy.cs
using UnityEngine;

public class Enemy : MonoBehaviour {
  public bool IsAlive { get; set; }

  void Start() {
    IsAlive = true;
  }

  // Update logic per frame
  public void HandleUpdate() {
    // Movement, AI, etc.
  }
}
  

// EnemyController.cs
using System.Collections.Generic;
using UnityEngine;

public class EnemyController : MonoBehaviour {
  private LinkedList enemies;

  void Start() {
    enemies = new LinkedList();
  }

  public void AddEnemy(Enemy enemy) {
    enemies.AddLast(enemy);
  }

  void Update() {
    UpdateEnemies();
  }

  private void UpdateEnemies() {
    var node = enemies.First;
    while (node != null) {
      var nextNode = node.Next;
      node.Value.HandleUpdate();

      if (!node.Value.IsAlive) {
        enemies.Remove(node);
      }

      node = nextNode;
    }
  }
}
  

Analyzing the Example and Performance Comparison

Key Takeaways

1. Dynamic Collection Management: Efficiently add/remove elements without shifting.
2. Reduced Modification Overhead: No array-style element shifts—nodes link directly to neighbors.
3. Simplified Iteration/Removal: You can remove nodes safely during traversal by pre-fetching Next.

LinkedList vs. List

LinkedList Advantages:

• Fast insertions and deletions anywhere in the list.
• Allocates per-element memory, efficient for fluctuating sizes.

List Advantages:

• O(1) random access by index.
• Contiguous memory can be more efficient for static or seldom-changed collections.
• Directly serializable (LinkedLists require conversion).

Conclusion: Choosing the Right Structure

Lists are simple and often sufficient, but LinkedLists shine when your collection changes frequently or requires bidirectional traversal. Match the data structure to your Unity project’s needs for optimal performance.

In the next article, we’ll explore Stacks and Queues and how they can further streamline your game’s performance and logic.