C# - 동적 배열 구현

동적 배열 구현

1. 기본 설정

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

---

2. Add

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)

요소 이동은 무시한다.

---

3. Indexer

public T this[int index]
{
    // indexer를 통해 데이터 가져오기
    get { return _data[index]; }
    // indexer를 통해 데이터 할당
    set { _data[index] = value; }
}

예시

MyList<int> myList = new MyList<int>();
myList[0] = 5; // set : 인덱스 0에 5를 할당
int value = myList[0]; // get : 인덱스 0의 값 읽기

시간 복잡도 : O(1)

---

4. RemoveAt

public void RemoveAt(int index)
{
    // 이사한 친구를 기준으로 한칸씩 땡겨주기
    // 101 102 103 104 105인데 102를 뺀다고 치면 103,104,105를 앞으로 땡겨주면된다.
    for(int i = index; i<Count -1;i++)
    {
        _data[i] = _data[i + 1];
    }
    // 그러면 101 103 104 105 105 이렇게 되므로 데이터를 제거해주기 위해 default사용
    // 제네릭 타입 T형식인 경우에는 0으로 초기화되고 참조 타입(class)이면 null로 초기화된다.
    _data[Count-1] = default(T);
    Count--;
}

시간복잡도 : O(N)

데이터 크기에 비례한 루프를 돌므로 시간복잡도는 O(N)이다.

 

 

 

 

 

 

 

 

 

 

 

 

참고 :  본 내용은 MMORPG  PART2 강의를 수강하여 작성하였습니다.

https://www.inflearn.com/course/%EC%9C%A0%EB%8B%88%ED%8B%B0-mmorpg-%EA%B0%9C%EB%B0%9C-part2/dashboard