선형 자료구조 - 1. 배열

배열 (Array)

출처 : https://wikidocs.net/22958

배열이란 순서대로 번호가 붙은 원소들이 연속적인 형태로 구성된 구조를 의미합니다.

 

원소들에게 붙은 번호를 인덱스(Index)라고 하며, 데이터들은 메모리 상에 연속적으로 저장됩니다.

 

장점

배열은 인덱스를 이용하여 데이터에 빠르게 접근할 수 있다는 장점이 있습니다.

 

배열의 데이터들이 물리적으로 메모리 상에 연속적으로 저장되어 있기 때문에, 첫 번째의 주소만 안다면 배열의 모든 값에 바로 접근할 수 있습니다.

출처 : http://www.tcpschool.com/c/c_array_oneDimensional

 

이러한 특성으로 인해 배열의 원소를 검색하는 시간은 O(1) 으로 임의접근이 가능하여 굉장히 빠릅니다.

 

임의 접근(Random Access)
집합 내의 요소의 수에 관계없이 주소 할당이 가능한 요소들로부터 임의의 시점에 임의의 데이터에 접근하는 기능

 

다만, 인덱스를 사용하는 것이 아닌 특정한 값을 찾기 위해 탐색하는 것은 처음부터 끝까지 순서대로 찾아봐야하는 선형탐색을 하므로 O(N)이 걸립니다.

 

 

단점

배열은 생성할 때 미리 최대 길이를 설정해 두고 생성해야 하기 때문에 데이터의 추가 / 삭제가 느리다는 장점이 있습니다.

 

메모리 주소가 연속되어야 하기 때문에 배열의 크기를 변경하는 것이 불가능하고, 그로 인해 배열에 데이터가 추가되거나 삭제되면 새로운 배열을 만들어 기존 내용을 복사해야하는 과정을 거쳐야 합니다. 

 

이러한 특성으로 배열은 데이터를 추가/삭제에 걸리는 시간이 O(N)이 걸리며 데이터 접근에 비해 상대적으로 느린 속도를 가지고 있습니다.

 

 

프로그래밍 언어에서의 구현

Java

자바에서는 배열이 필요할 때, 제공되는 Array 자료형을 그냥 사용하거나 ArrayList를 사용하곤 합니다.

밑의 구현은 ArrayList 와 비슷하게 구현해둔 자료이며, ArrayList에 관한 내용은 해당 내용을 다루는 게시글에서 자세히 다루겠습니다.

public class ExampleArray {

   int[] arr;

   // 배열 초기 사이즈 지정
   public ExampleArray(int size) {
      this.arr = new int[size];
   }

   // 배열에 데이터 삽입
   public void insert(int idx, int data) {
      if (idx < 0 || idx > arr.length) {
         throw new IndexOutOfBoundsException("인덱스가 범위 밖에 존재합니다.");
      }

      int[] arrDup = arr.clone();

      this.arr = new int[arr.length + 1];

      for (int i = 0; i < idx; i++) {
         arr[i] = arrDup[i];
      }

      arr[idx] = data;

      for (int i = idx + 1; i < arr.length; i++) {
         arr[i] = arrDup[i - 1];
      }
   }

   // 특정 데이터 삭제
   public void remove(int data) {
      int targetIdx = -1;

      for (int i = 0; i < arr.length; i++) {
         if (arr[i] == data) {
            targetIdx = i;
            break;
         }
      }

      if (targetIdx == -1) {
         throw new NoSuchElementException("삭제하려는 데이터가 존재하지 않습니다.");
      } else {
         int[] arrDup = arr.clone();

         arr = new int[arr.length - 1];

         for (int i = 0; i < targetIdx; i++) {
            arr[i] = arrDup[i];
         }

         for (int i = targetIdx; i < arr.length; i++) {
            arr[i] = arrDup[i + 1];
         }
         
      }
   }
}