동적 배열 구현 연습

전체 코드

class MyList<T>
{
    const int DEFAULT_SIZE = 1;
    T[] _data = new T[DEFAULT_SIZE];
    public int Count = 0; // 실제로 사용 중인 데이터 개수
    public int Capacity { get { return _data.Length; } } // 예약된 데이터 개수

    // O(1) : 예외 케이스 이사 비용은 무시한다.
    public void Add(T item)
    {
        // 거의 시행 되지 않음 어느 순간부터 예외 케이스
        // 1. 공간이 충분히 남아 있는지 확인한다.
        if (Count >= Capacity)
        {
            // 공간을 다시 늘려서 확보한다.
            T[] newArray = new T[Count * 2];
            for (int i = 0; i < Count; i++)
            {
                newArray[i] = _data[i];
            }
            _data = newArray;
        }
        // 2. 공간에 데이터를 넣어준다.
        _data[Count] = item;
        Count++;
    }

    // 인덱서 문법
    // O(1)
    public T this[int index]
    {
        get { return _data[index]; }
        set { _data[index] = value; }
    }

    // O(N)
    public void RemoveAt(int index)
    {
        // 101, 102, 104, 105 106 -> 0
        for (int i = index; i < Count; i++)
        {
            _data[i] = _data[i + 1];
        }
        _data[Count - 1] = default(T); // null or 0으로 밀음
        Count--;
    }
}

🔍 MyList<T> 클래스 분석 및 설명

MyList<T>는 C#의 List<T>와 유사하게 동작하는 동적 배열(Dynamic Array)을 직접 구현한 것입니다.
C++의 vector<T>와도 유사한 방식으로 동적 크기 조정을 수행하며, 내부적으로 배열(Array)을 사용하여 원소를 저장합니다.

---

📌 MyList<T> 클래스 개요

✅ 핵심 개념

• 배열을 기반으로 동작하며, 원소 추가(Add) 시 공간이 부족하면 더 큰 배열로 이사(복사)하여 크기를 확장.
• 인덱스 접근이 가능 (this[] 연산자 오버로딩)
• 원소 삭제 가능 (RemoveAt(int index))
• 연속적인 메모리를 사용하여 빠른 접근(O(1))이 가능하지만,
  삽입/삭제 시 O(N) 복잡도로 인해 성능이 저하될 수 있음.

---

📜 코드 분석

class MyList<T>
{
    const int DEFAULT_SIZE = 1;  // 초기 배열 크기
    T[] _data = new T[DEFAULT_SIZE];   // 내부 배열
    public int Count = 0;  // 실제 사용 중인 데이터 개수
    public int Capacity { get { return _data.Length; } } // 예약된 데이터 개수 (배열 크기)

✅ 멤버 변수

• _data
  • 배열을 사용하여 데이터를 저장.
  • 처음에는 DEFAULT_SIZE = 1 크기로 시작하며, 원소가 추가될 때 크기를 확장함.
• Count
  • 현재 사용 중인 데이터의 개수.
• Capacity
  • 예약된 데이터 개수.
  • 실제 _data 배열의 크기와 동일하며, Count보다 클 수 있음.

---

1️⃣ Add(T item) - 원소 추가

public void Add(T item)
{
    // 1. 공간이 충분한지 확인
    if (Count >= Capacity)
    {
        // 공간이 부족하면 크기를 두 배로 확장
        T[] newArray = new T[Count * 2];

        // 기존 배열의 데이터 복사 (이사 과정)
        for (int i = 0; i < Count; i++)
            newArray[i] = _data[i];

        // 새 배열을 _data로 변경
        _data = newArray;
    }

    // 2. 데이터 추가
    _data[Count] = item;
    Count++;
}

✅ 원소 추가(Add)의 동작 원리

1. 현재 배열의 공간이 부족하면 크기를 2배로 확장.
2. 새로운 배열을 생성하고 기존 데이터를 이사(복사).
3. 새로운 배열을 _data로 변경 (기존 배열은 가비지 컬렉터(GC)가 처리).
4. Count 위치에 데이터를 삽입 후 개수를 증가.

🔹 시간 복잡도

• 일반적인 경우: O(1)
  • 여유 공간이 있는 경우 단순히 추가하는 연산.
• 이사하는 경우: O(N)
  • 배열의 크기가 부족할 때 전체 원소를 복사해야 하므로 O(N) 발생.
• 평균적으로는 O(1)
  • 크기를 2배씩 증가하기 때문에 N번 추가할 때 전체 복사 비용이 O(N),
    즉 한 번의 추가 연산당 O(1) 비용.

---

2️⃣ this[int index] - 인덱스 접근

public T this[int index]
{
    get { return _data[index]; }
    set { _data[index] = value; }
}

✅ 기능

• myList[0]처럼 인덱스를 사용하여 원소에 접근 가능.
• 내부적으로 _data[index]를 반환하는 인덱서(Indexer) 문법.

🔹 시간 복잡도

• O(1)
  • 배열은 메모리에 연속적으로 저장되므로 임의 접근이 빠름.

---

3️⃣ RemoveAt(int index) - 원소 삭제

public void RemoveAt(int index)
{
    // 101, 102, 104, 105 106 -> 0
    for (int i = index; i < Count - 1; i++)
    {
        _data[i] = _data[i + 1];  // 한 칸씩 앞으로 이동
    }

    _data[Count - 1] = default(T); // 마지막 자리 초기화
    Count--;
}

✅ 삭제(RemoveAt)의 동작 원리

1. index 이후의 모든 요소를 한 칸씩 앞으로 이동.
2. 마지막 원소를 default(T)로 초기화.
3. Count--하여 사용 중인 데이터 개수를 줄임.

🔹 시간 복잡도

• O(N)
  • 삭제된 위치 이후의 모든 요소를 이동해야 하므로 최악의 경우 O(N) 발생.

---

📌 시간 복잡도 정리

연산	시간 복잡도	설명
추가(Add)	O(1) (평균) / O(N) (최악)	크기 확장 시 O(N), 일반적 O(1)
접근(Indexer)	O(1)	배열은 연속적인 메모리라서 빠름
삭제(RemoveAt)	O(N)	원소를 한 칸씩 이동해야 함

---

🚀 MyList<T>의 특징

✅ 장점

1. 동적 크기 조정 가능
   • Count가 Capacity를 초과하면 자동으로 확장.
2. 배열 기반이라 빠른 접근 가능 (O(1))
   • this[int index]로 빠르게 접근 가능.
3. 메모리 연속성 유지
   • 기존 배열(Array)과 동일한 메모리 구조를 가짐.

❌ 단점

1. 중간 삭제 성능 저하 (O(N))
   • RemoveAt(index)를 호출하면 모든 원소를 이동해야 함.
2. 확장 시 메모리 복사 비용 발생 (O(N))
   • 배열 크기가 변경될 때마다 모든 원소를 새로운 배열로 복사해야 함.

---