[c#/자료구조] 배열(Array)

 

자료구조 분류

 

• 단순 구조(Primitive Data Structure) : 기본적인 데이터 타입. 정수, 실수, 문자, 부울린 등의 기초 타입들
• 선형 구조(Linear Data Structure) : 자료가 선형적으로 연결되어 있는 구조. 배열, 연결리스트, 스택, 큐
• 비선형 구조(Non-linear Structure) : 자료 간 관계가 1대 다 혹은 다대다 구조.                                                                                                                             네트워크 혹은 계층구조를 가짐. 트리, 그래프
• 파일 구조 : 레코드의 집합인 파일에 대한 자료구조. 순차파일, 색인 파일, 직접파일.. 

 

 

 

---

 

 

 

1. 배열이란?

          ▶  배열 : 연속적인 메모리 상에 동일한 데이터 타입의 요소들을 순차적으로 저장하는 자료구조

                              -   각 요소마다 인덱스를 갖고 있음

                              -  크기가 고정되어 있음 

 

 

1차원 배열 선언

Int[] A = new int[10];

 

 

2차원 배열 선언

Int[,] A = new int[3,4];

 

 

 

 

1.2 가변 배열(Jagged Array)이란?

          ▶  가변 배열(Jagged Array) : 배열 요소가 배열 타입인 경우.

                             일반 다차원의 배열의 경우 [,] 와 같이 콤마로 차원을 분리한다

                         하지만, 가변 배열은 [][]와 같이 괄호를 겹처서 차원을 표시한다.

 

 

            ▶    사용 경우

                  1. 일반 다차원 배열로 했을 때, 공간의 낭비가 심해지는 경우 

                  2. 각 차원마다 다른 배열 크기를 가져야 하는 경우에 사용

 

 

//가변 배열 선언
int[][] A = new int[3][];

//각 1차원 배열 요소당 서로 다른 크기의 배열 할당
A[0] = new int[2];
A[1] = new int[6]{1,2,3,4,5,6};
A[2] = new int[3]{9,8,7};

 

 

 

 

 

1.3 동적 배열(Dynamic Array)이란? 

          ▶  정적 배열(Static Array) : 초기화시 크기가 미리 정해지며, 처음 지정한 고정 크기를 그대로 계속 유지함

                                                              ex) int[], strring[,] 과 같은 식으로 선언된 배열은 모두 정적 배열임

 

          ▶  동적 배열(Dynamic Array) : 배열의 최대 크기를 미리 알 수 없을 때,                                                                                                                                      배열을 중간에 확장 혹은 축소 해야 할 때 사용하면 용이하다. 

 

 

 

          동적 배열 만드는 방법 : 

                 1. 기존 배열 크기보가 1개 더 큰 임시 배열 생성

                 2. 임시 배열에 기존 배열값 복사

                 3. 기존 배열에 임시 배열 할당

                 4. 기존 배열의 마지막 요소에 새 배열 요소 추가 

 

    public object[] arr = new object[0];
    public void Add(object elemnet)
    {
        var temp = new object[arr.Length + 1]; //임시 배열 생성
        for(int i=0; i<arr.Length; i++)
        {
            temp[i] = arr[i]; //기존 배열 요소를 하나씩 복사함
        }
        arr = temp;  //기존 배열에 임시 배열 할당 

        arr[arr.Length - 1] = elemnet; //마지막 요소에 새 요소 할당 
    }

 

             단점 : 필요할 때마다 매번 새로운 배열 공간을 생성하고 기존 배열요소를 전부 복사해야 하는 번거로움이 있음 

                       O(n) 시간 복잡도 

 

 

           * 해결 방법 : 배열을 2배씩 확장한다. 

           Capacity : 배열의 최대 수용가능 용량

           Count : 현재 배열요소 수 

           count가 capacity 보다 크거나 같으면(배열이 꽉차면)  2배로 확장하고 새 배열 요소를 추가한다. 

    private object[] arr2;
    private const int GROWTH_FACTOR = 2;

    public int Count { get; private set; }
    public int Capacity
    {
        get { return arr2.Length; }
    }

    public void DynamicArray(int capacity = 16)
    {
        arr2 = new object[capacity];
        Count = 0;
    }

    public void AddArray(object element)
    {
        //배열이 꽉 찼을 때 확장
        if(Count >= Capacity)
        {
            int newSize = Capacity * GROWTH_FACTOR;
            var temp = new object[newSize];
            for(int i=0; i<arr2.Length; i++)
            {
                temp[i] = arr2[i];
            }
            arr2 = temp;
        }
        arr2[Count] = element;
        Count++;
    }

    public object Get(int index)
    {
        if(index > Capacity - 1)
        {
            throw new ApplicationException("Element not found");
        }
        return arr2[index];
    }

 

 

 

 

 

 

1.4 원형 배열(Circular Array) 이란? 

        ▶   원형 배열(Circular Array) : 고정된 크기의 배열을 양 끝이 연결된 것처럼 사용 가능 

                         배열의 크기가 N 일 때, 배열의 마지막 요소(N-1)에 도착하면, 다음 배열요소는 첫번째 요소(0)가 된다. 

 

                            - 원형 배열 : 선입선출(FIFO), 큐를 구현하거나 데이터 스트림 버퍼를 구현할 때 사용  

                            - 선형 배열 : 선입후출(LIFO)

 

 

                원형 배열 순찰을 위해서 mod 연산자를 사용하여 마지막 배열의 다음 인덱스가 첫 배열 인덱스로 돌아오게 한다. 

    char[] A = "abcdefgh".ToCharArray();
    int startIndex = 2;

    for(int i=0; i<A.Length; i++)
    {
        int index = (startIndex + i) % A.Length;
        Console.WriteLine(index);
    }

 

 

 

 

 

 

 

1.5 .NET 배열 클래스 

  .NET Framework에서 지원하는 동적 배열은 ArrayList와 List<T>가 있다. 

 

 

      ▶   ArrayList 

ArrayList ArrList = new ArrayList();

ArrList.Add("A");        // index 0
ArrList.Add("B");        // index 1
ArrList.Add("C");        // index 2

ArrList.RemoveAt(1);    

ArrList.Add("D");        // Add는 맨 끝에 추가하니깐 index 2 에 삽입됨

ArrList.Insert(2, "E");    //index 2의 자리를 E로 대체

 

 

     ▶    List<T>

                List<T>는 임의의 타입(T)을 지정할 수 있는 제네릭 동적 배열이다.

                   ex) List<int>, List<string>..

                지정된 타입만을 담을 수 있으며, 다양한 타입을 담을 때는 ArrayList가 더 유용하다.

    List<int> a = new List<int>();
    for(int i=1; i<=17; i++)
    {
        a.Add(i);
        Console.WriteLine("{0} : {1}", i, a.Capacity);
    }

         capacity는 2배씩 증가한다. 

 

 

 

 

 

출처 : C#으로 이해하는 자료구조