Array

데이터가 여러 개 있을 때 매번 처음부터 세어 가며 n번째 값을 찾는 방식은 반복 접근이 많아질수록 비효율적입니다. 특히 반복문, 이미지 처리, 수치 계산, 테이블 기반 알고리즘처럼 위치 번호로 바로 값을 읽어야 하는 상황에서는 '어디 있는지'를 즉시 계산할 수 있어야 합니다. Array는 이 위치 접근 문제를 해결하기 위해 쓰입니다.

초기 프로그래밍과 시스템 구현에서는 메모리 위치를 예측 가능하게 다루는 일이 중요했습니다. 수치 계산, 버퍼 처리, 문자열 저장처럼 같은 형태의 값을 많이 다룰수록 연속된 메모리와 오프셋 계산은 단순하면서도 강력한 모델이었습니다. 그래서 array는 특정 언어나 라이브러리의 선택이 아니라, 거의 모든 언어와 런타임이 공유하는 가장 오래된 기본 구조로 자리 잡았습니다.

Array는 연속된 메모리 블록을 하나 확보하고, 시작 위치(base address)에 인덱스와 원소 크기를 곱한 값을 더해 원하는 칸으로 이동합니다. 그래서 a[i]는 '앞에서부터 i번 따라간다'가 아니라 '시작 주소에서 i칸 떨어진 위치를 계산한다'에 가깝습니다. 이 계산 덕분에 읽기와 덮어쓰기는 빠르지만, 중간에 새 값을 넣거나 삭제하면 뒤 원소들을 한 칸씩 밀거나 당겨야 하므로 이동 비용이 생깁니다.

Array와 linked list는 둘 다 순차 컬렉션이지만 강점이 다릅니다. Array는 임의 위치 접근과 순차 순회가 빠른 대신, 중간 삽입과 삭제가 비쌉니다. Linked list는 노드 재연결로 삽입과 삭제를 다루기 쉬운 대신, 원하는 위치까지 직접 따라가야 하므로 인덱스 접근이 느립니다. 또 array는 정수 위치로 접근하는 구조이지, 키를 해싱해 찾는 hash table과도 다릅니다.

Array는 화면 목록, 수치 계산 벡터, 이미지 픽셀 버퍼, 동적 계획법 표, 정렬 대상 모음처럼 '순서'와 '위치 번호'가 함께 중요한 곳에서 널리 쓰입니다. 또 heap처럼 겉으로는 트리처럼 보이는 구조도 내부 저장은 array로 하는 경우가 많습니다. 데이터가 자주 재배치되지 않고 반복 읽기와 순차 처리 비중이 높을수록 array의 장점이 크게 드러납니다.