동적 배열 Add, RemoveAt 구현

동적 배열

*동적 배열의 Add, RemoveAt을 구현하는 연습

- 제네릭 클래스 내부에 Array, Count, Capacity 변수 설정.

public class MyList2<T> {
    public T[] _data = new T[1];
    public int Count = 0;
    public int Capacity { get { return _data.Length; } }

 

- Add 함수를 구현

public void Add(T item) {
    //수용공간이 꽉 찼는지 확인 후 꽉 찼으면 크기를 늘려서 배열 생성
    if(Count >= Capacity) {
        T[] array = new T[Count * 2];
        for (int i = 0; i < Count; i++) {
            array[i] = _data[i];
        }
        _data = array;
    }

    //아이템 추가
    _data[Count] = item;
    Count++;
}

 

- Remove At 함수를 구현

public void RemoveAt(int index) {
    //index 지점으로 뒤에 있는 배열을 앞으로 땡긴다.
    for (int i = index; i < Count-1; i++) {
        _data[i] = _data[i + 1];
    }
    //마지막에 남은 데이터는 default 처리한다.
    _data[Count - 1] = default;
    Count--;
}

 

 

*Add와 RemoveAt의 Big-O 표기

 

 

Add 함수: O(1)

RemoveAt 함수: O(n) 

 

 

Big-O 표기법 (빅오)