배열

컴퓨터 과학/프로그래밍에서 가장 기초적인 자료구조.

고정된 크기를 갖는 자료구조, 메모리 상에서 값들이 연속적으로 이어져있다.

하나의 메모리 덩어리에 데이터를 순차적으로 저장하는 구조.

size: 배열의 크기(요소의 개수)
index: 각 요소의 위치

연속적인 메모리 공간을 활용하기 때문에, 특정 요소에 빠른 접근 가능.
=> 위치와 상관없이 일정한 속도로 특정 요소에 접근 가능.

메모리 공간이 이미 할당된 이후에는 배열의 크기를 동적으로 조절할 수 없다.

=> 새로운 사이즈에 맞게 메모리 공간 재할당 => 기존 요소들을 새로운 공간으로 복사.

삭제할 요소 이후의 모든 요소들을 한 칸씩 앞으로 이동시켜야 한다.

• 연속된 메모리 공간에 데이터가 저장되며 사이즈가 고정.
• 특정 요소에 빠른 접근이 가능하다.
• 삽입/삭제 작업이 본질적으로 불가능 (새로운 배열 생성 또는 요소를 한 칸씩 이동시키는 방법 사용)

동적 배열

프로그램의 런타임에서 크기가 변경 가능(필요에 따라 확장 또는 축소 가능)

ex) Java: ArrayList // Python: List

	배열(정적)	동적 배열
크기 유연성	고정, 선언 시 결정된 크기 변경 불가	실행 중 크기 변경 가능, 자동 확장/축소
메모리 할당	컴파일 시간에 할당	런타임에 할당
성능	연속적인 메모리를 활용 빠른 읽기/쓰기	크기 변경 시 오버헤드 발생 가능
재할당/복사	수동으로 새 배열을 만들거나 덮어쓰기	필요에 따라 자동으로 조정

자바스크립트에서는 동적 배열처럼 동작한다. (자바스크립트에서의 배열은 사실 객체이다.)

let arr = [];
let arr2 = new Array(); // new 생략 가능.
let arr3 = new Array(5).fill(0) // 크기가 5이며, 요소들을 0으로 채운 배열

// 읽기 (상수 시간)
console.log(arr[0]);
console.log(arr[99]); // 범위가 벗어나면 undefined를 반환한다.

// 검색 (선형 시간) => O(n)?
arr.indexOf("a"); // 가장 처음 만난 a의 위치를 반환.

// 삽입
arr.push("b"); // 배열 끝에 요소를 추가한다. => 상수 시간
arr.unshift("c"); // 배열 앞에 요소를 추가한다. => 선형 시간

// 삭제
arr.pop(); // 배열 마지막 요소 제거. => 상수 시간
arr.shift(); // 배열 가장 앞 요소 제거. => 선형 시간
arr.splice(1, 1); // 시작 지점에서 요소 n개 제거. => 선형 시간