자료구조 — 배열 vs 연결 리스트

개요 — 왜 자료구조 선택이 게임 성능에 직결되는가

Unreal Engine 게임 서버는 매 프레임 수백 개의 Actor를 순회하고, 클라이언트는 60fps 기준 단 16.67ms 안에 렌더링과 게임 로직을 모두 처리해야 합니다. 이 환경에서 “어떤 컨테이너에 데이터를 넣느냐”는 단순한 코딩 스타일 문제가 아니라 프레임 예산을 지키느냐 못 지키느냐의 문제입니다.

배열과 연결 리스트는 가장 기초적인 두 자료구조이지만, 내부 동작 방식이 완전히 다르기 때문에 같은 알고리즘이라도 성능 차이가 수십 배에 달할 수 있습니다. 특히 CPU 캐시 활용 방식의 차이는 현대 하드웨어에서 이론적 시간복잡도보다 더 큰 영향을 미치는 경우가 많습니다.

---

1. 내부 구조와 메모리 레이아웃

1.1 배열(Array)의 메모리 구조

배열은 동일한 크기의 원소를 메모리 상에 연속으로 배치한 자료구조입니다. 첫 번째 원소의 주소(Base Address)와 원소 크기(Element Size)를 알면, n번째 원소의 주소를 즉시 계산할 수 있습니다.

Address = BaseAddress + (Index × ElementSize)

메모리 레이아웃 (int32 배열, 원소 크기 4바이트):

주소:   0x1000  0x1004  0x1008  0x100C  0x1010
값:     [ 10 ]  [ 20 ]  [ 30 ]  [ 40 ]  [ 50 ]
인덱스:   [0]     [1]     [2]     [3]     [4]

→ 연속된 메모리 블록, 원소 간 간격 = sizeof(T)

std::vector<T>와 Unreal의 TArray<T>는 모두 이 원리를 사용하며, 내부적으로 힙(Heap)에 할당된 하나의 연속 메모리 블록을 관리합니다.

// TArray 내부 구조 (단순화)
// Engine/Source/Runtime/Core/Public/Containers/Array.h 참조
template<typename T>
class TArray
{
    T*    AllocatorInstance; // 연속 메모리 블록의 시작 포인터
    int32 ArrayNum;          // 현재 원소 수
    int32 ArrayMax;          // 할당된 용량 (Capacity)
};

용량(ArrayMax)이 꽉 차면 더 큰 메모리 블록을 새로 할당하고 기존 원소를 전부 복사합니다. 이를 **동적 배열(Dynamic Array)**이라고 합니다. 재할당 비용은 O(n)이지만, **평균적으로 끝 삽입은 O(1) 상각(Amortized)**으로 처리됩니다.

1.2 연결 리스트(Linked List)의 메모리 구조

연결 리스트는 노드(Node)라는 독립적인 구조체들을 포인터로 연결한 자료구조입니다. 각 노드는 데이터와 다음 노드를 가리키는 포인터를 함께 보유합니다.

단일 연결 리스트 (Singly Linked List):

[Node A]        [Node B]        [Node C]
Data: 10   →    Data: 20   →    Data: 30   → nullptr
Next: 0x2A00    Next: 0x3F10    Next: nullptr

→ 각 노드는 힙의 임의 위치에 개별 할당
→ 물리적 메모리 주소가 불연속

이중 연결 리스트 (Doubly Linked List):

nullptr ← [Node A] ⇄ [Node B] ⇄ [Node C] → nullptr
           Data:10     Data:20     Data:30

노드들이 메모리의 임의 위치에 산재해 있기 때문에, 특정 인덱스의 노드에 접근하려면 Head 포인터부터 포인터를 따라가며 순차적으로 탐색해야 합니다.

1.3 메모리 레이아웃 시각적 비교

배열 (TArray / std::vector):
RAM: [■][■][■][■][■][■][■][■]  ← 연속 배치
      10  20  30  40  50

연결 리스트 (TLinkedList / std::list):
RAM: [■]...[■][■]...[■][■][■]  ← 흩어진 위치
     10      20       30
      ↓       ↓        ↓
    0x1000  0x4F20   0x2B80

이 물리적 배치의 차이가 **캐시 지역성(Cache Locality)**에서 결정적 성능 차이를 만들어냅니다 (Section 5에서 상세 설명).

---

2. 연산별 시간복잡도 비교

2.1 접근(Access) — 특정 인덱스 원소 읽기

배열: O(1)

인덱스로 주소를 직접 계산하므로 항상 상수 시간입니다.

TArray<int32> Scores = {100, 85, 72, 60};
int32 ThirdScore = Scores[2]; // 즉시 접근, O(1)
// BaseAddress + 2 * sizeof(int32) 계산 한 번으로 완료

연결 리스트: O(n)

Head에서 포인터를 따라가며 n번 이동해야 합니다.

// std::list는 임의 접근 연산자 operator[]를 제공하지 않음
// n번째 원소에 접근하려면 이터레이터를 n번 전진시켜야 함
std::list<int32> ScoreList = {100, 85, 72, 60};
auto It = ScoreList.begin();
std::advance(It, 2); // 포인터 2번 추적, O(n)
int32 ThirdScore = *It;

2.2 탐색(Search) — 특정 값을 가진 원소 찾기

두 자료구조 모두 정렬되어 있지 않다면 전체 순회가 필요합니다.

배열: O(n) — 연속 메모리를 순회하므로 캐시 효율 우수 연결 리스트: O(n) — 포인터를 따라가므로 캐시 미스 빈발

// 배열 탐색 — O(n), 캐시 친화적
TArray<FString> EnemyNames = {TEXT("Goblin"), TEXT("Orc"), TEXT("Dragon")};
int32 FoundIdx = EnemyNames.IndexOfByPredicate([](const FString& Name)
{
    return Name == TEXT("Orc");
}); // FoundIdx == 1

// 연결 리스트 탐색 — O(n), 캐시 비친화적
std::list<std::string> NameList = {"Goblin", "Orc", "Dragon"};
auto It = std::find(NameList.begin(), NameList.end(), "Orc");

정렬된 배열에 한해 이진 탐색을 적용하면 **O(log n)**으로 개선됩니다. 연결 리스트는 임의 접근이 불가하므로 이진 탐색을 적용할 수 없습니다.

2.3 삽입(Insertion)

배열 끝 삽입: O(1) 상각

용량이 충분하면 끝에 추가만 하므로 O(1). 재할당 시 O(n)이지만 평균 상각 비용은 O(1)입니다.

배열 중간/앞 삽입: O(n)

삽입 위치 이후 원소를 모두 한 칸씩 오른쪽으로 이동시켜야 합니다.

TArray<int32> Values = {1, 2, 4, 5};

// 끝 삽입: O(1) 상각
Values.Add(6); // {1, 2, 4, 5, 6}

// 중간 삽입: O(n) — 이후 원소 전체 이동
Values.Insert(3, 2); // 인덱스 2에 3 삽입 → {1, 2, 3, 4, 5, 6}
// 기존 4, 5, 6을 각각 한 칸씩 오른쪽으로 복사

연결 리스트 삽입 (포인터 보유 시): O(1)

삽입 위치의 이전 노드 포인터만 있다면 포인터 변경만으로 완료됩니다.

// std::list: 이터레이터가 가리키는 위치 앞에 삽입 — O(1)
std::list<int32> NumList = {1, 2, 4, 5};
auto InsertPos = std::next(NumList.begin(), 2); // 인덱스 2로 이동 = O(n)
NumList.insert(InsertPos, 3); // 포인터 교체 = O(1)
// 탐색 비용 O(n) + 실제 삽입 O(1) → 전체는 O(n)

핵심 포인트: 연결 리스트의 삽입이 O(1)이 되려면 삽입 위치의 이터레이터/포인터를 이미 알고 있어야 합니다. 탐색 비용까지 포함하면 대부분의 실제 상황에서 O(n)입니다.

2.4 삭제(Deletion)

배열 끝 삭제: O(1)

Values.Pop(); // 끝 원소 제거, O(1)

배열 중간 삭제: O(n)

삭제 위치 이후 원소를 전부 한 칸씩 왼쪽으로 이동시켜야 합니다.

// RemoveAt: O(n) — 이후 원소 전체 이동
Values.RemoveAt(2);

// RemoveAtSwap: O(1) — 마지막 원소와 교체 후 Pop (순서 파괴)
Values.RemoveAtSwap(2); // 순서가 중요하지 않을 때 사용

연결 리스트 삭제 (포인터 보유 시): O(1)

std::list<int32> NumList = {1, 2, 3, 4, 5};
auto DelPos = std::next(NumList.begin(), 2); // 탐색 O(n)
NumList.erase(DelPos); // 포인터 교체 O(1)

2.5 종합 비교 테이블

연산	배열 (Array)	연결 리스트 (Linked List)	비고
인덱스 접근	O(1)	O(n)	배열 압승
탐색 (비정렬)	O(n)	O(n)	동일, 캐시 효율은 배열이 우세
탐색 (정렬 후 이진탐색)	O(log n)	불가	배열 압승
끝 삽입	O(1) 상각	O(1)	실질적 동일
중간 삽입	O(n)	O(1) (포인터 보유 시)	연결 리스트 우세
끝 삭제	O(1)	O(1)	동일
중간 삭제	O(n)	O(1) (포인터 보유 시)	연결 리스트 우세
메모리 오버헤드	낮음	높음 (포인터 per 노드)	배열 우세

---

3. C++ 코드 예시

3.1 std::vector vs std::list

#include <vector>
#include <list>
#include <algorithm>

// ===== std::vector (동적 배열) =====
void VectorExample()
{
    std::vector<int32> Vec = {10, 20, 30, 40, 50};

    // O(1) 임의 접근
    int32 Third = Vec[2]; // 30

    // O(1) 상각 끝 삽입
    Vec.push_back(60);

    // O(n) 중간 삽입 (이후 원소 이동 발생)
    Vec.insert(Vec.begin() + 2, 25);
    // → {10, 20, 25, 30, 40, 50, 60}

    // O(n) 중간 삭제 (이후 원소 이동 발생)
    Vec.erase(Vec.begin() + 2);
    // → {10, 20, 30, 40, 50, 60}

    // 용량 사전 예약 (재할당 방지)
    Vec.reserve(100);

    // O(n) 정렬 후 O(log n) 이진 탐색 가능
    std::sort(Vec.begin(), Vec.end());
    bool bFound = std::binary_search(Vec.begin(), Vec.end(), 30);
}

// ===== std::list (이중 연결 리스트) =====
void ListExample()
{
    std::list<int32> List = {10, 20, 30, 40, 50};

    // O(n) 임의 접근 (이터레이터 전진 필요)
    auto It = List.begin();
    std::advance(It, 2); // 2번 포인터 추적
    int32 Third = *It;   // 30

    // O(1) 끝 삽입
    List.push_back(60);
    List.push_front(5);

    // O(1) 삽입 (이터레이터를 이미 보유 중일 때)
    auto InsertPos = std::next(List.begin(), 3);
    List.insert(InsertPos, 25);

    // O(1) 삭제 (이터레이터를 이미 보유 중일 때)
    List.erase(InsertPos);

    // 이진 탐색 불가 (임의 접근 미지원)
    // std::binary_search는 RandomAccessIterator가 필요
}

3.2 Unreal TArray vs TLinkedList / TDoubleLinkedList

#include "Containers/Array.h"
#include "Containers/LinkedList.h"

// ===== TArray<T> — Unreal 표준 동적 배열 =====
void TArrayExample()
{
    TArray<int32> Scores;

    // 용량 사전 예약 (재할당 최소화)
    Scores.Reserve(64);

    // O(1) 상각 끝 삽입
    Scores.Add(100);
    Scores.Add(85);
    Scores.Add(72);

    // O(1) 인덱스 접근
    int32 TopScore = Scores[0]; // 100

    // O(n) 중간 삽입
    Scores.Insert(90, 1); // 인덱스 1에 90 삽입

    // O(1) 끝 삭제
    Scores.Pop();

    // O(n) 중간 삭제 (순서 유지)
    Scores.RemoveAt(1);

    // O(1) 중간 삭제 (순서 파괴, 성능 우선)
    Scores.RemoveAtSwap(0);

    // 람다로 조건 삭제
    Scores.RemoveAll([](int32 Score)
    {
        return Score < 50;
    });

    // 정렬
    Scores.Sort([](int32 A, int32 B)
    {
        return A > B; // 내림차순
    });
}

// ===== TLinkedList<T> — Unreal 단일 연결 리스트 =====
// TLinkedList는 노드 자체가 리스트의 구성원이 되는 침투형(Intrusive) 방식
// 외부에서 노드를 직접 관리해야 함
void TLinkedListExample()
{
    // TLinkedList<T> 노드는 스택/힙에서 수동으로 관리
    TLinkedList<int32> Node1(10);
    TLinkedList<int32> Node2(20);
    TLinkedList<int32> Node3(30);

    // 연결 (이전 노드의 다음으로 삽입)
    Node1.LinkAfter(&Node2); // Node2 → Node1 연결
    Node2.LinkAfter(&Node3); // Node3 → Node2 연결

    // 순회
    for (TLinkedList<int32>::TIterator It(&Node3); It; ++It)
    {
        UE_LOG(LogTemp, Log, TEXT("Value: %d"), *It);
    }

    // 연결 해제
    Node1.Unlink();
}

// ===== TDoubleLinkedList<T> — Unreal 이중 연결 리스트 =====
// 더 일반적인 연결 리스트 용도에는 TDoubleLinkedList를 사용
void TDoubleLinkedListExample()
{
    TDoubleLinkedList<int32> DList;

    // 끝에 추가 — O(1)
    DList.AddTail(10);
    DList.AddTail(20);
    DList.AddTail(30);

    // 앞에 추가 — O(1)
    DList.AddHead(5);

    // 특정 노드 앞에 삽입 — O(1) (노드 포인터 보유 시)
    auto* Node20 = DList.FindNode(20); // 탐색 O(n)
    if (Node20)
    {
        DList.InsertNode(25, Node20); // 삽입 O(1)
    }

    // 노드 삭제 — O(1) (노드 포인터 보유 시)
    auto* NodeToDelete = DList.FindNode(25);
    if (NodeToDelete)
    {
        DList.RemoveNode(NodeToDelete); // O(1)
    }

    // Head부터 순회
    for (auto* Node = DList.GetHead(); Node != nullptr; Node = Node->GetNextNode())
    {
        UE_LOG(LogTemp, Log, TEXT("Value: %d"), Node->GetValue());
    }

    UE_LOG(LogTemp, Log, TEXT("List Size: %d"), DList.Num());
}

실무 참고: Unreal Engine에서 일반적인 컨테이너 사용 시 TArray가 기본 선택지입니다. TLinkedList와 TDoubleLinkedList는 엔진 내부(애니메이션 노드 그래프, 렌더링 패스 큐 등)에서 특수 목적으로 사용되며, 일반 게임플레이 코드에서는 드물게 사용됩니다.

---

4. 캐시 지역성(Cache Locality)과 게임 성능

4.1 CPU 캐시 구조 이해

현대 CPU는 RAM에 직접 접근하는 것이 너무 느리기 때문에 **여러 계층의 캐시(L1/L2/L3)**를 사용합니다.

계층        크기        지연 시간(Latency)
L1 Cache    32~64 KB    ~4 cycles  (매우 빠름)
L2 Cache    256 KB~1 MB ~12 cycles
L3 Cache    8~32 MB     ~40 cycles
RAM (DRAM)  수 GB       ~200+ cycles (매우 느림)

CPU는 메모리를 캐시 라인(Cache Line) 단위로 읽습니다. 캐시 라인 크기는 일반적으로 64바이트입니다. 즉, 어떤 주소의 데이터를 읽으면 그 주소를 포함한 64바이트 블록 전체가 캐시에 올라옵니다.

4.2 배열의 캐시 친화성 (Cache-Friendly)

int32 배열 (원소 크기 4바이트, 캐시 라인 64바이트 = 16개 원소):

캐시 라인:  [10][20][30][40][50][60][70][80][90][100][...][...][...][...][...][...]
                                                  ← 64바이트 한 번에 로드 →

배열[0] 접근 → 캐시 미스 발생 → 64바이트 전체 캐시 적재
배열[1] 접근 → 캐시 히트! (이미 캐시에 있음)
배열[2] 접근 → 캐시 히트!
...
배열[15] 접근 → 캐시 히트!
배열[16] 접근 → 캐시 미스 (다음 캐시 라인 적재)

배열을 순차적으로 순회할 때 캐시 미스는 16번에 1번꼴로만 발생합니다 (int32 기준). CPU의 하드웨어 프리페처(Prefetcher)도 연속 접근 패턴을 감지하면 다음 캐시 라인을 미리 로드합니다.

4.3 연결 리스트의 캐시 미스 문제

연결 리스트 노드 (노드마다 힙의 임의 위치에 할당):

RAM의 여러 위치에 산재:
0x1000: [Data:10][Next:0x4F20]  ← Node A
...
0x4F20: [Data:20][Next:0x2B80]  ← Node B (캐시 라인이 다름)
...
0x2B80: [Data:30][Next:nullptr] ← Node C (또 다른 캐시 라인)

Node A 접근 → 캐시 미스 → 0x1000 영역 64바이트 캐시 적재
Node B 접근 → 캐시 미스! (0x4F20은 다른 캐시 라인)
Node C 접근 → 캐시 미스! (0x2B80도 다른 캐시 라인)

연결 리스트는 노드마다 캐시 미스가 발생할 수 있습니다. 각 캐시 미스마다 RAM 접근 지연 200+ cycles가 추가됩니다.

4.4 실제 벤치마크 시나리오

아래 시나리오는 1만 개의 원소를 순차 탐색할 때의 차이를 보여줍니다.

// 시나리오: 1만 명 적 체력 합산 (Tick에서 매 프레임 실행)

// 나쁜 예: 연결 리스트 순회 — 캐시 미스 폭발
void SumHealthLinkedList()
{
    std::list<int32> HealthList; // 각 노드가 힙의 임의 위치
    // 10,000개 원소 → 최대 10,000번 캐시 미스 → ~2,000,000 cycles 낭비
    int32 Total = 0;
    for (int32 HP : HealthList)
    {
        Total += HP;
    }
}

// 좋은 예: 배열 순회 — 캐시 라인 활용 최적
void SumHealthArray()
{
    TArray<int32> HealthArray; // 연속 메모리
    // 10,000개 원소 → 캐시 미스 약 625번 (10000/16)
    int32 Total = 0;
    for (int32 HP : HealthArray)
    {
        Total += HP;
    }
}

실제 측정 결과(Intel i7 기준, 원소 10만 개):

자료구조	순회 시간
std::vector / TArray	~0.3 ms
std::list / TDoubleLinkedList	~3.0 ms 이상

약 10배 이상의 성능 차이가 알고리즘 복잡도가 동일(O(n))한데도 발생합니다. 이것이 현대 하드웨어에서 캐시 지역성이 중요한 이유입니다.

4.5 구조체 배열(AoS) vs 배열의 구조체(SoA)

게임에서 자주 마주치는 고급 캐시 최적화 패턴입니다.

// AoS (Array of Structures) — 일반적 방식
// 모든 정보를 하나의 구조체에 묶어서 배열로 관리
struct FEnemyData
{
    FVector Location;  // 12바이트
    float   Health;    // 4바이트
    float   Damage;    // 4바이트
    int32   TeamID;    // 4바이트
    // 총 24바이트 per 원소
};
TArray<FEnemyData> AllEnemies;

// 위치만 순회할 때 → 24바이트 중 12바이트만 사용 → 캐시 효율 50%

// SoA (Structure of Arrays) — 캐시 최적화 방식
// 필드별로 별도 배열로 분리
struct FEnemyDatabase
{
    TArray<FVector> Locations; // 위치만 모아서 연속 저장
    TArray<float>   Healths;
    TArray<float>   Damages;
    TArray<int32>   TeamIDs;
};
FEnemyDatabase EnemyDB;

// 위치만 순회할 때 → Locations 배열만 접근 → 캐시 효율 100%
// 적 AI 위치 업데이트, 컬링 등 단일 필드 대량 처리 시 유리

---

5. 이터레이터 무효화(Iterator Invalidation)와 std::span

5.1 이터레이터 무효화란

컨테이너를 수정하면 기존에 보유하던 이터레이터(포인터, 참조)가 무효(dangling) 상태가 되는 현상입니다. 무효화된 이터레이터를 역참조하면 **정의되지 않은 동작(UB, Undefined Behavior)**이 발생합니다.

// 위험한 코드: 순회 중 TArray 수정
TArray<int32> Scores = {50, 30, 80, 10, 60};

// 잘못된 패턴 — Scores.Add() 시 재할당 발생 → 모든 포인터 무효화
for (int32& Score : Scores)   // Score는 내부 원소의 참조
{
    if (Score < 40)
    {
        Scores.Add(Score * 2); // 재할당 발생 시 Score 참조 무효!
    }
}
// 결과: 정의되지 않은 동작 (크래시 또는 오염된 데이터)

TArray 이터레이터 무효화 시점:

연산	이터레이터 무효화	이유
Add / Push	재할당 시 전부 무효화	내부 버퍼 이동
Insert	삽입 위치 이후 전부 무효화	원소 이동
RemoveAt	삭제 위치 이후 전부 무효화	원소 이동
RemoveAtSwap	삭제 위치만 무효화	마지막 원소와 교체
Reserve	재할당 시 전부 무효화	내부 버퍼 재할당
SetNum (축소)	제거된 원소 이후 무효화	원소 제거

std::list 이터레이터 무효화 시점:

연산	이터레이터 무효화
push_back / push_front	무효화 없음 (새 노드 할당)
insert	무효화 없음
erase	삭제된 노드의 이터레이터만 무효화

이 차이가 연결 리스트의 핵심 장점 중 하나입니다.

// 안전한 패턴 1: 별도 컨테이너에 수집 후 처리
TArray<int32> ToAdd;
for (int32 Score : Scores)
{
    if (Score < 40)
    {
        ToAdd.Add(Score * 2);
    }
}
Scores.Append(ToAdd); // 순회 완료 후 한 번에 추가

// 안전한 패턴 2: 역방향 순회로 RemoveAt (앞 원소 인덱스 안전)
for (int32 i = Scores.Num() - 1; i >= 0; --i)
{
    if (Scores[i] < 40)
    {
        Scores.RemoveAt(i); // 역방향이므로 i 앞 인덱스는 유효
    }
}

// 안전한 패턴 3: RemoveAll 람다 (내부적으로 안전하게 처리)
Scores.RemoveAll([](int32 Score) { return Score < 40; });

5.2 std::span — 복사 없이 배열 뷰 전달 (C++20)

std::span<T>은 연속 메모리(배열, std::vector, TArray 등)를 **복사 없이 참조하는 경량 뷰(View)**입니다. 함수에 배열을 전달할 때 불필요한 복사를 방지합니다.

#include <span>

// 기존 방식: TArray를 const 참조로 전달 (타입이 고정됨)
void ProcessScoresOld(const TArray<int32>& Scores)
{
    for (int32 Score : Scores) { /* ... */ }
}

// std::span 방식: 어떤 연속 컨테이너든 받을 수 있음 (복사 없음)
void ProcessScores(std::span<const int32> Scores)
{
    for (int32 Score : Scores) { /* ... */ }
}

void ExampleSpan()
{
    TArray<int32> TArrayScores = {100, 85, 72};
    std::vector<int32> VecScores = {90, 60, 75};
    int32 CArrayScores[] = {80, 55, 95};

    // 모두 동일한 함수로 처리 가능 (복사 없음)
    ProcessScores(std::span<const int32>(TArrayScores.GetData(), TArrayScores.Num()));
    ProcessScores(VecScores);           // std::vector → span 자동 변환
    ProcessScores(CArrayScores);        // C 배열 → span 자동 변환

    // 부분 뷰: 배열의 일부만 처리 (복사 없음)
    ProcessScores(std::span<const int32>(TArrayScores.GetData() + 1, 2)); // 인덱스 1~2만
}

Unreal Engine 프로젝트에서 C++20 표준이 활성화되지 않은 경우, 유사한 패턴으로 TArrayView<T>를 사용합니다.

// TArrayView: Unreal의 std::span 대응체 (C++17 이하 환경)
#include "Containers/ArrayView.h"

void ProcessScoresUE(TArrayView<const int32> Scores)
{
    for (int32 Score : Scores) { /* ... */ }
}

void ExampleTArrayView()
{
    TArray<int32> Scores = {100, 85, 72, 60};
    ProcessScoresUE(Scores);                    // TArray → TArrayView 자동 변환

    // 부분 뷰
    ProcessScoresUE(MakeArrayView(Scores).Slice(1, 2)); // 인덱스 1부터 2개
}

---

6. 언제 어떤 자료구조를 선택해야 하는가

6.1 배열 계열(TArray / std::vector)을 선택해야 할 때

• 인덱스 기반 임의 접근이 빈번한 경우 (예: 순찰 경로 포인트, 스킬 레벨별 데미지 테이블)
• 순차 순회가 주요 연산인 경우 (예: 매 Tick에서 전체 적 처리)
• 데이터 크기가 자주 변하지 않거나 끝 삽입/삭제가 주인 경우
• 정렬 후 이진 탐색이 필요한 경우
• 메모리 사용량 최소화가 중요한 경우 (연결 리스트는 포인터 오버헤드 발생)
• 캐시 성능이 중요한 실시간 게임 루프 내부

6.2 연결 리스트 계열(TDoubleLinkedList / std::list)을 선택해야 할 때

• 중간 삽입/삭제가 매우 빈번하고 해당 위치의 포인터를 항상 보유하는 경우
• 이터레이터 무효화(Iterator Invalidation)를 피해야 하는 경우 (TArray는 재할당 시 이터레이터 무효화)
• 원소 이동 비용이 매우 큰 대형 구조체를 자주 재배치해야 하는 경우
• 큐(Queue)나 덱(Deque) 구조로 앞/뒤 삽입·삭제가 모두 필요한 경우

6.3 실전 UE5 시나리오별 가이드

시나리오                                    권장 컨테이너     이유
────────────────────────────────────────────────────────────────────────
적 Actor 목록 (전체 순회)                  TArray           캐시 효율
순찰 경로 Waypoints                        TArray           인덱스 접근
스킬 레벨별 데미지 테이블                  TArray           인덱스 접근
렌더링 큐 (앞/뒤 삽입·삭제 빈번)          TDoubleLinkedList 앞뒤 O(1)
우선순위 변경 잦은 태스크 목록             TDoubleLinkedList 중간 삽입 O(1)
GameplayTag 컨테이너                       TArray(내부)     순서 유지
플레이어 인벤토리 (슬롯 기반)              TArray           인덱스 접근
스폰 풀(Object Pool)에서 사용 가능 목록   TArray           단순 Push/Pop
애니메이션 상태 전이 규칙                  TArray           정적 데이터

// 실전 예시 1: 적 Tick 처리 — TArray가 정답
UCLASS()
class AEnemyManager : public AActor
{
    GENERATED_BODY()

    // TArray: 매 Tick 순회 시 캐시 효율 최대
    UPROPERTY()
    TArray<TObjectPtr<AEnemy>> ManagedEnemies;

public:
    virtual void Tick(float DeltaTime) override
    {
        Super::Tick(DeltaTime);

        // 연속 메모리 순회 → 캐시 라인 활용 최적
        for (TObjectPtr<AEnemy>& Enemy : ManagedEnemies)
        {
            if (IsValid(Enemy))
            {
                Enemy->UpdateAI(DeltaTime);
            }
        }
    }

    void AddEnemy(AEnemy* Enemy)
    {
        ManagedEnemies.Add(Enemy); // O(1) 상각
    }

    void RemoveEnemy(AEnemy* Enemy)
    {
        // 순서가 중요하지 않다면 RemoveAtSwap (O(1))
        ManagedEnemies.RemoveSwap(Enemy);
    }
};

// 실전 예시 2: 렌더 커맨드 큐 — 앞뒤 삽입·삭제 빈번
// Unreal 엔진 내부 패턴 참조
class FRenderCommandQueue
{
    TDoubleLinkedList<FRenderCommand> CommandQueue;

public:
    void EnqueueHigh(FRenderCommand Cmd)
    {
        // 긴급 커맨드는 앞에 삽입 — O(1)
        CommandQueue.AddHead(MoveTemp(Cmd));
    }

    void Enqueue(FRenderCommand Cmd)
    {
        // 일반 커맨드는 뒤에 삽입 — O(1)
        CommandQueue.AddTail(MoveTemp(Cmd));
    }

    bool Dequeue(FRenderCommand& OutCmd)
    {
        auto* Head = CommandQueue.GetHead();
        if (!Head) return false;

        OutCmd = Head->GetValue();
        CommandQueue.RemoveNode(Head); // O(1)
        return true;
    }
};

---

7. 정리 및 체크리스트

한눈에 보는 선택 기준

질문	YES	NO
인덱스로 임의 접근하는가?	TArray	계속
매 프레임 전체 순회하는가?	TArray	계속
중간 삽입·삭제가 매우 빈번하고 포인터를 항상 보유하는가?	TDoubleLinkedList	계속
앞·뒤 양쪽에서 O(1) 삽입·삭제가 필요한가?	TDoubleLinkedList	TArray

게임 개발 자료구조 체크리스트

• Tick() 내부에서 전체 순회하는 컨테이너는 TArray를 사용하고 있는가?
• 중간 삭제 시 순서가 중요하지 않다면 RemoveAtSwap(O(1))을 사용하고 있는가?
• TArray 재할당을 최소화하기 위해 Reserve()로 용량을 사전 예약했는가?
• 연결 리스트가 반드시 필요한 이유를 설명할 수 있는가? (대부분은 TArray로 해결 가능)
• 캐시 성능이 중요한 대규모 데이터 처리에서 SoA 패턴을 고려했는가?
• 이터레이터 무효화 위험을 고려하여 컨테이너 수정 중 순회를 피하고 있는가?
• 순회 중 원소를 삭제해야 할 때 역방향 순회 또는 RemoveAll 람다를 사용하고 있는가?
• 함수에 배열을 전달할 때 불필요한 복사를 막기 위해 TArrayView 또는 std::span을 사용하고 있는가?
• 대형 구조체를 TArray에 넣을 때 복사 비용 대신 TObjectPtr나 인덱스 활용을 검토했는가?