[자료구조] 배열(Array)

 

 

 

 

 

 

자료구조, 배열(Array)에 대해 알아보기 

---

 

 

 

 

 

 

 

 

Array의 구조와 특징 

 

배열은 컴퓨터에서 리스트를 저장하는 데이터 타입 중 하나입니다. 

 

• 연속된 메모리 공간에 순차적으로 데이터가 저장되며 같은 타입의 데이터를 여러개 나열한 선형 자료구조이다.
• 대부분의 프로그램 언어에서 동일한 타입의 데이터를 저장한다.
• index가 존재하여 indexing 및 slicing이 가능하다. 

 

 

 

 

Array의 선언

 

자바에서 배열을 선언하는 경우, 해당 배열의 자료형과 크기를 지정해야 합니다.

 

//1차원 배열
int[] arr1 = new int[5];

//2차원 배열 
int[][] arr2 = new int[3][5];

 

 

 

 

 

 

Array의 활용

 

배열을 반복문과 결합하면 많은 데이터도 효율적으로 처리할 수 있습니다. 

• 순차적인 데이터를 저장하며, 값 보다는 순서가 중요한 경우
• 다차원 데이터를 다루는 경우
• 어떤 특정 요소를 빠르게 읽어야 하는 경우
• 데이터 사이즈가 자주 바뀌지 않으며 요소가 자주 추가되거나 삭제되지 않는 경우 

 

 

 

 

Array의 연산

 

1. 접근(accecss)

 

배열의 접근은 O(1)의 시간 복잡도를 갖습니다. 

 

찾고자 하는 값의 인덱스 값을 알고 있다면 빠른 검색 속도를 갖습니다. 

 

2. 검색(search)

 

배열의 검색은 순차검색이므로 인덱스를 알지 못할 때 원하는 값을 찾기 위해 배열을 하나하나 확인해야 합니다. 

 

따라서 최대 O(n)의 시간 복잡도를 가집니다. 

 

3. 추가, 삭제(remove)

 

추가, 삭제의 시간복잡도는 접근과 검색의 방법 차이에 따라 시간 복잡도가 나뉩니다.

 

인덱스 값을 알고 있다면 접근의 개념으로 O(1)의 시간복잡도를 가집니다.

 

하지만 해당 인덱스를 찾아야한다면, 검색의 시간복잡도인 O(n)을 가집니다. 

 

 

 

 

Array의 시간 복잡도

 

배열의 시간복잡도

 

 

 

 

Array의 장점

 

• 인덱스을 알고 있는 경우 모든 요소에 빠르게 접근이 가능하다. 
• 기록 밀도가 1이기 때문에 공간 낭비가 적다.
• 사용하기 쉽다.

 

 

 

 

 

Array의 단점

 

• 배열을 선언 한 후에는 할당된 정적 메모리 떄문에 크기를 변경할 수 없다.
• 순차적 특성 때문에 삽입 및 삭제에 비용이 많이 든다. 
• 크기가 대부분 정적으로 결정되기 때문에 삽입 및 삭제가 동적으로 발생하는 상황에선 오버 플로우나 저장공간의 낭비를 초래할 수 있다.