2. 동적 배열 구현 연습

동적 배열 구현해보기

c# List(동적배열)에 대해 MyList라는 임의 클래스를 생성하여 비슷하게 구현해보려고 합니다.

public class MyList<T>  
{  
	private const int DEFALUT_SIZE = 1;  
	private T[] _data = new T[DEFALUT_SIZE]; // 처음 배열의 사이즈는 1이라고 가정하고 시작.
	
	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];  // 1.5~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; }  
	}  

	// 최적의 경우를 봐야한다. index가 만약 0부터 시작한다면 전체를 다 돌아야 한다  
	// O(N)  
	public void RemoveAt(int index)
	{  
		for (int i = index; i < Count - 1; i++) // index하나가 지워졌으니깐 전체 갯수가 줄어든다.   
		{  
			_data[i] = _data[i + 1]; // 뒤에 있는 데이터가 앞으로 땡겨진다.  
		}  

		_data[Count - 1] = default(T);  
		Count--;  
	}  
}  

변수

• Count : 데이터가 담겨있는 갯수를 의미한다. 데이터를 담는 인덱스를 의미하기도 함.
• Capacity : 예약된 여유분의 데이터 갯수를 의미한다. 실제 데이터가 담겨 있는 Count보다 예약분을 늘려 준다.
• Count >= Capacity 조건에 따라 _ data의 전체 배열 사이즈는 변경된다.

함수

• [ ] 연산자 오버로딩
  • get { return _data[index]; } : 배열이름[index]에 있는 데이터를 가져옴
  • set { _data[index] = value; } : 배열이름[index] = value 로 데이터 저장.
• Add : 데이터 추가 작업
  • 공간이 충분한지 여부에 따라 _data배열의 사이즈가 변경된다.
    • Count >= Capacity 조건 == true
      • newArray를 선언하고, 현재 데이터가 담겨있는 갯수(Count) x 1.5~2
      • 새로운 배열은 기존보다 Capacity가 늘어남.
      • 현재 데이터를 새로운 배열에 있는 데이터에 삽입.
      • 현재 배열에 새로 만든 배열을 삽입.
    • 추가된 데이터를 배열의 Count(index)에 할당.
    • Count++;
  • 시간복잡도 : O(1) : 예외(이사비용)상황을 제외하기 때문에.
• RemoveAt : 데이터 삭제
  • 삭제되는 데이터의 인덱스부터 마지막(index하나가 지워짐으로, Count(데이터 담긴 갯수)- 1)까지 데이터 이동(앞으로)
  • 삭제된 인덱스부터 뒤에 있는 모든 배열이 이동한다는 것을 의미한다.
  • 시간복잡도 : 0부터 시작한다면 O(N)의 시간복잡도를 가지게 된다.
  • defalut(T)
    • 참조형 타입 (Reference Type): default(T)는 null을 반환
    • 값형 타입 (Value Type): default(T)는 해당 값형 타입의 기본값을 반환. 예를 들어, int의 기본값은 0, bool의 기본값은 false, char의 기본값은 '\0' (null 문자)입니다.

정리

동적 배열은 필요에 따라 크기를 유연하게 조절할 수 있는 배열이다. 또한 인덱스를 통해 접근이 가능하다는 점에서 고정 배열의 장점을 함께 가지고 있다.

또한 특정 조건(배열 재할당)이 아닐 경우 O(1)의 시간 복잡도를 가지고 있는 장점이 있다.

하지만 삽입 / 삭제 / (때떄로지만)재할당의 경우 O(N)의 시간 복잡도를 가지고 있고, 실제 사용하지 않는 메모리 공간을 예약함으로 어떻게보면 메모리 낭비라 할 수 있겠다.

데이터의 크기를 유연하게 가질 수 있다는 점에서 데이터의 양이 정해져있지 않은 경우 유용하게 사용될 수 있을 것으로 보인다.