[자료구조] 동적 배열(Dynamic Array)

동적 배열의 필요성

-배열은 고정된 크기의 연속된 배열 요소들의 집합이므로 배열을 초기화 시 미리 배열의 크기를 정해야 한다.

-그러나 때론 미리 이 크기를 정할수 없는 경우가 있고, 중간에 배열을 확장해야 하는 경우가 있다.

-이런 상황에 사용하는 것이 동적 배열이며 .NET에는 ArrayList와 List<T>가 있다.

 

동적 배열의 시간 복잡도

-배열(정적 배열)과 같이 인덱스를 통해 한 요소에 접근시 O(1)

-배열의 요소 개수 n개에 대하여 특정 값을 탐색하는 시간 O(n)

 

ArrayList 클래스

-모든 배열 요소가 object 타입인 Non-Generic 동적 배열 클래스다.

-.Net의 Non-Generic클래스들은 System.Collections namespace 안에 있다.

-박싱(value 타입을  reference 타입으로 변환하는 것), 언박싱(reference 타입을 value 타입으로 변환하는 것)이 일어나게 된다.

-ArrayList는 배열 요소를 읽어 사용할 때 object를 return하므로 일반적으로 원하는 타입으로 casting한 후 사용해야 한다.

 

List<T> 클래스

-배열 요소가 T 타입인 Generics이다.

-내부적으론 배열을 가지고 있으며, 동일한 타입의 데이터를 저장한다.

-만약 미리 할당된 배열 크기가 부족하면 내부적으로 배열을 2배 늘려 동적으로 배열을 확장한다.

-ArrayList와 배열 요소를 읽어 사용시 casting할 필요가 없으며, 박싱/언박싱 문제가 일어나지 않는다.

 

사용 예시

using System;
using System.Collections;
using System.Collections.Generic;
using System.IO;

class Program
{
    static void Main(string[] args)
    {
    	ArrayList arrayList = new ArrayList();
        List<int> list = new List<int>();
        arrayList.Add(12);
        list.Add(24);
        int first = arrayList[0];
        int second = list[1];
        arrayList.Add("사랑합니다");
        Console.WriteLine(first + "월" + second + "일" + third); //12월 24일 사랑합니다 출력
    }
}