배열의 형태
- 연속된 메모리의 공간에 순차적으로 데이터를 저장하는 선형 자료구조이다.
배열의 특징
- 연속된 메모리의 공간에 순차적으로 데이터를 저장하는 선형 자료구조이다.
- 크기가 고정적이고 공간이 낭비되거나 재할당이 필요할 수 있다.
- 자바스크립트 처럼 대부분의 스크립트 언어는 배열의 크기를 동적으로 변경할 수 있다.
- 논리적인 저장 순서와 물리적(메모리) 저장 순서가 일치한다.
- 인덱스를 사용해 특정 원소에 접근이 가능하다.(Random Access => 비순차적 접근)
- 메모리는 배열이 선언될 때(컴파일 할 때) Stack영역에 할당한다.
배열의 시간복잡도
-
배열의 맨 뒤에 데이터를 삽입 / 삭제 하는 경우 : O(1)
배열의 끝 주소 = 시작 주소 + (1칸이 차지하는 주소 X 배열 길이)
위 수식을 통해 배열의 끝 주소를 찾고, 배열의 길이를 1 증가시킨 후, 추가할 원소 데이터를 저장하면 된다.
그러므로 시간복잡도는 O(1)이다.
위에서 알아본 배열의 가장 끝에 원소 추가하기와 비슷하게 배열의 끝 주소를 찾고, 배열의 길이를 1만큼 줄이면 되므로 시간복잡도는 O(1)이다. -
배열의 맨 뒤를 제외한 경우의 위치에 데이터를 삽입 / 삭제 하는 경우 : O(N)
임의의 위치에 원소를 새로 추가해서 끼워넣으려면 그 뒤에 존재하는 모든 원소들을 한 칸씩 뒤로 밀어야 한다.
뒤로 미는 연산이 한 번 일어날 때 O(1)이 걸린다. 만약 N개의 원소를 한 칸씩 밀어야 한다면 O(1XN) = O(N)이 걸리게 된다.
추가하려는 위치가 배열의 끝과 가까울수록 그 뒤에 존재하는 원소의 개수가 적어져 뒤로 밀어내는 연산의 수도 줄어든다.
평균적으로 N/2 개의 원소를 뒤로 밀어내야 하므로 시간복잡도는 O(N/2) = O(N)이다.
삭제 연산도 임의의 위치에 원소를 추가하는 것과 비슷하게 수행된다.
임의의 위치에 있는 원소를 삭제하면 그 뒤에 존재하는 모든 원소들을 한 칸씩 앞으로 당겨와야 한다.
왜 굳이 앞으로 당겨와야 할까?
배열의 정의 상 배열은 메모리의 데이터(원소)를 연속하게 배치한 자료구조이기 때문이다.
앞으로 당기는 연산이 한 번 일어날 때 O(1)이 걸린다. 만약 N개의 원소를 한 칸씩 앞으로 당겨야 한다면 O(1XN) = O(N)이 걸리게 된다.
제거하려는 원소의 위치가 배열의 끝과 가까울수록 그 뒤에 존재하는 원소의 개수가 적어져 앞으로 당기는 연산의 수도 줄어든다.
반대로 제거하려는 위치가 배열의 처음과 가까울수록 그 뒤에 존재하는 원소의 개수가 많아져 앞으로 당기는 연산의 수도 늘어난다.
평균적으로 N/2 개의 원소를 앞으로 당겨야 하므로 시간복잡도는 O(N/2) = O(N)이다. -
배열의 특정 위치 데이터를 탐색하는 경우 : O(1)
메모리 상에 일렬로 나열되어 있으니 배열의 시작 주소에서 k칸 만큼 더하면 k번째 원소를 찾을 수 있다.
k번째 원소의 위치 = 시작주소 + (1칸이 차지하는 주소 X k)
단순 사칙연산 계산에 의해 O(1)만에 k번째 원소를 찾을 수 있다.
장점
- 인덱스를 통해 찾으려는 원소에 O(1)의 시간복잡도 만에 빠르게 접근할 수 있다.
- 자료구조의 크기가 클수록 더 강력한 장점이다. - 연속된 메모리 공간에 존재하기 때문에 관리가 편하다.
단점
- 새로운 원소의 삽입 / 삭제의 경우 O(N)의 시간복잡도가 걸려 느리다.
- 연속된 메모리 상에 원소들이 존재하므로 처음 배열을 선언한 크기만큼 데이터를 저장하지 않는다면 메모리 낭비가 발생한다.
- 연속적인 메모리 할당이 필요하여 메모리 공간을 많이 사용하게 될 수 있다.
배열을 사용하기 좋은 경우
- 데이터의 수가 확실하게 정해진 경우.
- 데이터의 삭제와 삽입이 적은 경우.
- 데이터의 탐색이 많이 이루어지는 경우.
구현 - javaScript
- javaScript는 내장된 배열 메소드들이 많지만 메소드들을 사용하지 않고 구현해보았다.
- javaScript에서의 배열은 배열의 크기가 가변적이라 배열의 밀고 당기는 메소드를 구현할 필요가 없으나 다른 언어의 관점에서 구현해보았다.
'use strict';
class Array {
constructor() {
// 배열의 빈 공간을 제외한 데이터들의 개수
this.length = 0;
this.data = [];
}
// 배열의 원소 탐색
// 인덱스를 알고 있다면 특정 원소에 접근하는 시간 복잡도는 O(1)이다.
get(idx) {
console.log(this.data[idx]);
}
// 배열의 맨 뒤에 원소 추가
push(value) {
this.data[this.length] = value;
this.length++;
}
// 배열의 맨 뒤 원소 제거
pop() {
const popValue = this.data[this.length - 1];
delete this.data[this.length - 1];
this.length--;
return popValue;
}
// 배열의 맨 앞 원소 추가
unshift(value) {
this.pushArray(0);
this.data[0] = value;
this.length++;
}
// 배열의 맨 앞 원소 제거
shift() {
const shiftValue = this.data[0];
delete this.data[0];
this.pullArray(0);
this.length--;
return shiftValue;
}
// 배열의 맨 앞과 뒤가 아닌 특정 위치에 원소 추가
insert(idx, value) {
this.pushArray(idx);
this.data[idx] = value;
this.length++;
}
// 배열의 맨 앞과 뒤가 아닌 특정 위치에 원소 제거
delete(idx) {
const deleteValue = this.data[idx];
delete this.data[idx];
this.pullArray(idx);
this.length--;
return deleteValue;
}
// 배열의 데이터를 뒤로 밀기
pushArray(idx) {
for (let i = this.length - 1; i >= idx; i--) {
this.data[i + 1] = this.data[i];
}
}
// 배열의 데이터를 앞으로 당기기
pullArray(idx) {
for (let i = idx; i < this.length; i++) {
this.data[i] = this.data[i + 1];
}
delete this.data[this.length - 1];
}
}
const myArray = new Array();
myArray.push(1);
console.log(myArray);
myArray.push(2);
console.log(myArray);
myArray.push(3);
console.log(myArray);
myArray.delete(1);
console.log(myArray);
myArray.pop();
console.log(myArray);
myArray.push(4);
console.log(myArray);
myArray.insert(1, 5);
console.log(myArray);
myArray.unshift(6);
console.log(myArray);
myArray.shift();
console.log(myArray);
- 결과
참고자료
