동적 배열

C#에는 다양하게 이미 배열,동적배열,연결리스트가 구현되어있는데
동적배열의 이해를 위해 작성

public int[] _data = new int[25]; //배열
public List<int> _data2 =  new List<int>(); //동적 배열
public LinkedList<int> _data3 = new LinkedList<int>(); //연결 리스트

---

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 배열의 초기 사이즈는 1로 설정한다. (빈 리스트를 만들었을 때 사이즈)
Count는 데이터가 추가,삭제 될때 유동적으로 관리한다.
Capacity는 실제 우리가 예약된 데이터의 개수니까 _data의 크기랑 같을 것이다.
그러므로 _data.Length와 같을 것이다.

---

Add 함수

//시간복잡도 : if문에서 Count만큼 N개만큼이니 O(N)인거 같지만 예외케이스로 실행되지 않는다고 하고 O(1) 이다. 
public void Add(T item)
{
	//1.공간이 충분히 남아 있는지 확인
    if(Count >= Capacity) //실제 사용중인 데이터의 개수가 예약된 데이터크기보다 많다면 공간부족
    {
    	//공간을 확보
        T[] newArray = new T[Count * 2]; //새로운 배열을 용량 2배씩 늘려서 생성해서 이사준비
        for(int i=0; i<Count ; i++)
        {
        	newArry[i] = _data[i];
        }
        _data = newArray; //원본으로 이사
    }
    
    //2.공간이 확보됐다면 데이터를 넣어준다.
    _data[Count] = item;
    Count++;
}

---

인덱서

public List<int> _data2 = new List<int>();
_data2.Add(101);
_data2.Add(102);
_data2.Add(103);
_data2.Add(104);
_data2.Add(105);

int temp = _data2[2]; // 인덱서의 get부분
_data2[2] = 3; //인덱서의 set부분

int temp에 동적배열의 index를 통해 가져오는 부분을 인덱서 라고하는데
인덱서는 클래스나 구조체의 인스턴스를 배열처럼 인덱싱이 가능하다.
인덱싱 값은 형식이나 인스턴스 멤버를 명시적으로 지정하지않고도 설정하거나 검색할 수 있다.

//시간복잡도 : O(1)
public T this[int index]
{
	get{return _data[index]; }
    set{_data[index] = value; }
}

---

RemoveAt

//시간복잡도 : index에 따라 for문에서 실행횟수가 달라지는데 이럴때는 최대 실행일때를 생각하여 O(N)
public void RemoveAt(int index)
{
	for(int i = index; i < Count - 1; i++)
    {
    	_data[i] = _data[i + 1];
    }
    _data[Count-1] = default(T);
	Count--;
}

_data[index]를 삭제해야하니 _data[index]부분부터 실제 사용중인 (Count-1)까지 한칸씩 데이터를 옮기면 된다.
for문에서 i < Count-1 부분에서 Count-1인지 Count인지 헷갈리면
_data[ i + 1] -> _data[Count - 2 + 1 ] -> _data [Count -1] 이니까 실제 사용하고있는 개수의 최대가 되니까 Count -1이다.
i에 Count -2를 대입하는 이유는 실제로 i가 Count - 1 보다 작을 때 들어오는게 되니까 _data[Count - 2 + 1]가 된다.
이해가 되지 않는다면 Count에 5를 index에 2를 넣고 생각해보면
_data(2) = _data(3)
_data(3) = _data(4)가 된다.

실제로 값이 101 102 103 104 105가 있다면
위에 로직을 실행하면 101 102 104 105 105 가 될텐데
마지막 105가 남아있는 상태가 된다.
_data[Count-1] = default(T) 에서 마지막 값을 정수형이 오면 0으로 클래스타입이 오면 null로 초기화 시켜준다.