[자료구조] 배열(Array)의 개념

 

오늘은 자료구조에서 가장 기본으로 다루는 배열에 대해 정리해보겠습니다.

 

배열이란?

같은 타입의 변수들로 이루어진 유한 집합

배열의 구조

배열은 같은 종류의 데이터를 다뤄야 하는 경우에 사용할 수 있는 가장 기본적인 자료구조 입니다.

중요한 건 int 데이터를 모으는 int 배열, String 데이터를 모으는 String 배열처럼 같은 자료형 데이터들만 담을 수 있습니다.

 

배열을 구성하는 각각의 배열 요소를 element라고 하며, 배열에서의 위치를 가리키는 숫자를 index라고 합니다. 자바에서 인덱스는 언제나 0부터 시작하며, 0을 포함한 양의 정수만을 가질 수 있습니다.

 

배열은 선언되는 형식에 따라 1차원 배열, 2차원 배열, 3차원 배열 등 다차원 배열로 선언이 가능하지만 현실적으로 이해하기 쉬운 2차원 배열까지가 주로 사용됩니다.

---

주요 특징 및 장단점

• Java의 모든 배열은 동적으로 할당됩니다.

동적 할당 : 실행 시간(Runtime) 동안 사용할 공간을 힙(heap) 메모리에 할당하는 것을 말합니다.

 

• 배열의 크기는 정수값으로만 지정할 수 있습니다.

 

• 배열의 변수는 순서가 지정되며 0부터 시작하는 인덱스를 가집니다.

배열에 n개의 데이터가 존재할 때 인덱스 번호는 [0 ~ n-1]으로 순차적임.
인덱스도 정수값임.

 

• 배열의 크기는 초기화되면 변경할 수 없습니다.

배열의 크기를 실시간으로 변경할 수 없지만 다른 배열을 가리키도록 만들 순 있음.
다른 크기의 배열을 사용하기 위해서는 새 배열을 만들어 할당해야 함.

 

• 다차원 배열 구현이 가능합니다. (보통 2차원 이상은 잘 사용하지 않음)

 

가장 큰 특징은 순차적으로 데이터를 저장한다는 것입니다.

index를 사용해 특정 요소에 바로 접근이 가능한 것이 배열의 주요 장점입니다.

순차적으로 존재하는 데이터 중간 요소를 삽입 또는 삭제하는 경우에는 요소 뒤쪽의 데이터들을 모두 한 칸씩 옮겨주어야 하기 때문에 상대적으로 번거롭습니다.
-> 잦은 추가, 삭제시 배열 사용은 부적합 합니다. 

따라서 배열은 주식차트와 같이 순서가 주요한 경우에 적합한 자료구조 입니다.

---

생성과 초기화

: 배열 선언은 컴퓨터에게 해당 크기만큼 메모리를 잡아놓도록 하는 것이고

   초기화란 잡아놓은 메모리에 값을 채워넣는 것을 말합니다.

 

배열 선언

1차원 배열은 주로 다음 두 가지 문법에 따라 선언합니다.

// 1. type[] name;
int[] array;

// 2. type name[];
int array[];

일반적으로 1번의 방법을 사용합니다. 앞으로 예시에서는 모두 1번 방식을 사용하도록 하겠습니다.

타입은 배열 요소로 저장되는 변수의 자료형을 나타냅니다.
배열 이름은 배열이 선언된 후 배열에 접근하기 위해 사용됩니다.

 

배열의 생성

// 타입[] 배열이름 = new 타입[배열 길이];
int[] array = new int[10];

String[] dayOfWeek = new String[7];

첫 번째 배열 array는 int 자료형 10개를 담을 수 있는 배열입니다.

두 번째 배열 dayOfWeek는 String 자료형 7개를 담을 수 있는 배열입니다.

 

배열의 초기화

: 배열 초기화는 필요한 시기에 따라 다양한 방식으로 이루어질 수 있습니다. 3가지 경우를 간단한 예시와 함께 살펴보겠습니다.

 

1) 배열 선언과 동시에 초기화

int[] array = {10, 20, 30};

int[] array2 = new int[]{3, 6, 9};

 

2) 배열 선언 후 생성과 함께 초기화

int[] array;
array = new int[]{1,2,3};

 

3) 인덱스를 이용한 접근 후 초기화

int[] array = new int[3];

for(int i = 0; i< 3; i++) {
    array[i] = i+1;
}

// array[0] = 1
// array[1] = 2
// array[2] = 3

 

---

for 반복문과 배열

: 배열에 값을 초기화하거나 요소 접근 및 특정 요소 검색을 위해서 반복문과 함께 사용되는 경우가 많습니다.

간단하게 배열에 요일값을 초기화하고 원하는 요일을 검색하는 예시를 확인해보겠습니다.

 

String[] weeks = {"월요일", "화요일", "수요일", "목요일", "금요일", "토요일", "일요일"};

// 토요일 찾기
for(int i = 0; i< 7; i++) {
    if(weeks[i].equals("토요일")) {
        System.out.println("토요일은 " + (i+1) +"번째!");
    }
}

// 출력: "토요일은 6번째!"

 

---

Array와 ArrayList 비교

주요 차이점은 다음과 같습니다.

• 배열(Array)은 크기가 고정적인데 반해 ArrayList는 크기가 가변적입니다.
• 배열(Array)는 초기화 시 메모리에 할당되어 속도가 빠르지만, ArrayList는 데이터 추가 및 삭제시 메모리 재할당이 필요하여 배열에 비해 속도가 느립니다.

 

---

Array와 LinkedList 비교

• Array는 인덱스로 해당 원소에 접근할 수 있어 찾고자 하는 원소의 인덱스를 알고 있다면 O(1)로 접근 가능
• 삭제시에는 이후 배열 요소들을 옮겨줘야 하기 때문에 O(n)의 시간복잡도를 가짐

 

• LinkedList는 각각의 요소들은 자기 자신 다음에 어떤 요소인지만 기억하고 있기 때문에 이 부분을 다른 값으로 바꿔주면 O(1) 비용으로 삽입과 삭제가 가능함
• 원하는 위치에 한 번만 접근할 수 없다는 단점이 있음. 원하는 위치를 Search하는 과정에 있어서 첫번째 원소부터 다시 확인해봐야 함.

 

Array -> 검색이 빠르지만 삽입, 삭제는 느림

LinkedList -> 삽입 삭제가 빠르지만 검색이 느림

---

 

참고

https://www.softwaretestinghelp.com/c-sharp/csharp-arrays/

http://tcpschool.com/java/java_array_oneDimensional

https://dev-coco.tistory.com/159?category=1056309