[자료구조] 배열

배열이란?

- 같은 자료형의 값들의 묶음으로 연속적인 메모리를 사용

- 조회시 인덱스를 이용여 속도가 빠름

- 메모리 공간을 사전 할당하므로 공간 이상의 값을 저장시 메모리 재할당 필요

- 접근 시간 복잡도: O(1)

- 탐색 시간 복잡도: O(N)

- 삽입/삭제 시간 복잡도: O(N)

배열 ADT

배열 구조

배열 조회

배열 추가

배열 삭제

 

void insert()
void remove()

 

프로그램 언어별 메서드

- C: 동일한 자료형의 묶음

/* 배열 선언 및 초기화 */
type arr[size];
type arr[size] = {val1, ...};

/* 2차원 배열 선언 및 초기화 */
type arr[size][size];
type arr[size][size] = {{val1, ...}, {val2, ...}};

/* 동적배열 할당*/
type *arr = (type*)malloc(sizeof(type) * size);
free(arr);

/* 2차원 동적배열 할당*/
type** arr = (int**)malloc(sizeof(type*) * size);
for (int i = 0; i < size; i++) {
    arr[i] = (type*)malloc(sizeof(type) * size);
}
for (int i = 0; i < size; i++) {
    free(arr[i]);
}
free(arr);

/* 예시 */
int arr[3];
int arr[5] = {1, 3, 6, 2, 1};
int arr[2][3];
int arr[2][3] = {{1, 2, 3}, {4, 5, 6}};

/* 배열 접근 */
arr[index];
*(arr + i);

/* 예시 */
arr[1];
*(arr + 1);

- C++: 동일한 자료형의 묶음

/* 배열 선언 및 초기화 */
type arr[size];
type arr[size] = {val1, ...};

/* 2차원 배열 선언 및 초기화 */
type arr[size][size];
type arr[size][size] = {{val1, ...}, {val2, ...}};

/* 동적배열 할당 및 초기화*/
type *arr = new type[size];
type *arr = new type[size] {val1, ...};
delete []arr;

/* 2차원 동적배열 할당*/
type** arr = new type*[size];
for (int i = 0; i < size; i++) {
    arr[i] = new type[size];
}
for (int i = 0; i < size; i++) {
    delete[] arr[i]);
}
delete[] arr;

/* 예시 */
int arr[3];
int arr[5] = {1, 3, 6, 2, 1};
int arr[2][3];
int arr[2][3] = {{1, 2, 3}, {4, 5, 6}};

/* 배열 접근 */
arr[index];
*(arr + i);

/* 예시 */
arr[1];
*(arr + 1);

- C#: 배열은 고정 길이. List는 가변길이로 연산 속도가 느림

/* 배열 선언 및 초기화 */
type[] arr = new type[size];
type[] arr = new type[size] {val1, ...};

/* 다차원 배열 선언 */
type[,] arr = new type[size, size];
type[,] arr = new type[size, size] {{val1, ...}, {val2, ...}};
type[,,] arr = new type[size, size, size];

/* 배열 접근 */
arr[index];

/* 리스트 사용 */
using System;
using System.Collections.Generic;
List<type> list = new List<type>();

/* 리스트 접근 */
list[index];

/* 리스트 추가/삭제 */
list.Add(val);
list.RemoveAt(index);

- Java

 

- Python: 리스트를 사용하므로 동일한 자료형이 아닌 단순한 값들의 묶음

/* 배열 정의 및 초기화 */
arr = list()
arr= []
arr = [val1, ...]

/* 예시 */
arr = [i for i in range(10)]
arr = [3, 6, 10]

/* 배열 접근 */
arr[index]
arr[start:end:step]

/* 예시 */
arr[-1]
arr[1: 10: 2]

- JavaScript