자료구조가 선정되는 방식
: 자료구조는 해당 자료구조의 동작 OPERATION에 의해 결정된다.
✨ 배열
여러 데이터를 하나의 이름으로 그룹핑해서 관리하기 위한 데이터 스토리지
삽입과 삭제의 경우 O(N)의 시간 복잡도를 갖는다.
원소에 접근할 때는 O(1)의 시간 복잡도를 갖는다.❓ 배열은 왜 생겨났을까?
그것은 데이터가 적을 때는 문제가 되지 않는다.
A와 B가 있다면 배열은 필요없다.
직접적으로 A와 B한테 다가가면 되기 때문이다.
하지만 문제는 데이터가 많아지면 발생한다.
❓데이터가 많아진다면?
데이터가 많아지면 그룹관리의 필요성이 생긴다.
다른말로 하면 그룹에 관련된 요소들만 활용할 수 있어야 한다
배열은 element의 집합체라고 볼 수 있다
이러한 element는 index와 value를 가진다.
위의 그림에서 0은 index 10은 value이다.
❓배열의 기능은?
배열의 기능이라 함은 크기가 정해져 있으면서 기능이 없다는 점이다.
기능이 없다는 것이 의미하는 것이 상당히 애매할 수 있다.
배열은 단순함이 그 자체다. 이에 대해서 조금 더 깊이 알아보고자 한다.
배열은 동일한 크기의 메모리 공간이 빈틈없이 연속적으로 나열된 자료 구조이다.
배열의 요소는 하나의 타입으로 통일되어 있으며 서로 연속적으로 인접해 있다.
(배열 자체가 하나의 타입으로 이루어져 있지는 않다. 배열의 타입은 자유롭다)
배열은 인덱스를 통해 단 한번의 연산으로 임의의 요소에 임의 접근을 할 수 있다.
여기에 시간복잡도는 O(1) 다음과 같다.
<출처 : https://poiemaweb.com/js-array-is-not-arrray>
이는 배열이 임의의 요소에 접근하는 경우라면 매우 빠르게 동작할 수 있다는 말이 된다.
하지만 배열의 단점은 정렬되지 않은 배열에서 찾고자 하는 요소에 접근할 때 발생한다.
function linearSearch(array, target) {
for (let i = 0; i < array.length; i++) {
if (array[i] === target) {
return console.log('target_index :',i); // target 값을 찾았으므로, 그 위치를 반환
}
}
return console.log('찾지 못하였습니다');
}
arr=[3,4,2,5,1,2,5,6,8,9,13]
linearSearch(arr, 13) // target_index : 10배열에는 찾고자 하는 요소에 접근하는 기능이 없다.
위의 작성한 코드는 우리가 직접 배열속으로 들어가서 요소를 확인하는 과정이다.
간단한 선형검색의 경우 시간 복잡도는 선형적으로 타겟 데이터를 찾아야 함으로 O(n)이 된다.
이 외에도 삭제와 원하는 위치에 삽입 등에서도 배열은 비교적으로 느리다.
왜냐하면 앞에서 언급했듯이 배열은 이러한 기능이 없기 때문이다.
우리가 직접 배열에 들어가서 작업을 해주어야 한다.
<출처 : https://poiemaweb.com/js-array-is-not-arrray>
하지만 여기서 의문점이 생긴다.
자바스크립트에서 배열에 원하는 위치에 데이터를 삽입하거나 데이터를 삭제하는 것은 아주 편하다.
예를들어 배열에 특정한 데이터를 넣고 싶으면 Array.splice()를 사용하면 된다.
원하는 데이터가 존재하는 지 확인하는 것도 쉽다.
Array.include()를 사용하면 된다.
여기서 우리는 한가지 개념을 짚고 넘어가야 할 필요가 있다...
✨ 리스트
처음, 중간, 끝에 Element를 추가/삭제하는 기능, 리스트 내에 데이터가 있는 지 확인 가능한 기능이 있는 자료구조
원소에 접근할 때 O(N)의 시간 복잡도를 갖는다.
삽입과 삭제의 경우 O(N)의 시간 복잡도를 갖는다.
(처음과 끝 요소에 삽입하는 경우 시간복잡도 O(1))
빈 공간이 없기 때문에 메모리 낭비가 적다앞서 제일 먼저 언급했듯이
자료구조는 해당 자료구조의 동작 OPERATION에 의해 결정된다.
리스트는 위의 정의와 같은 OPERATION을 가지고 있는 자료구조이다.
리스트는 데이터가 저장되어 있는 순서가 중요하다.
Delete하는 과정을 예로 들어서 배열과 리스트를 비교해볼 수 있다.
배열의 경우 인덱스 3번 위치의 요소를 삭제한다고 하면 그 공간은 사라지지 않는다.
배열의 특징 중 하나인 크기가 정해져 있다 라는 OPERATION 구조 때문에 만약에 해당 공간 또한 없애야 한다면 배열 속으로 직접 들어가서 지우고 나와야 한다.
반면에 리스트의 경우는 다르다.
리스트의 경우 데이터가 저장되어 있는 순서가 중요하다.
즉 만약에 3번 인덱스 위치의 요소를 삭제한다면 리스트의 공간이 아닌 순서의 의거해서 빈 공간을 자연스럽게 뒤에 따라오는 요소가 채운다.
이를 조금 더 쉽게 이해해 보고자 한다.
✅ 배열 == 영화관 좌석
배열은 영화관의 좌석이다.
영화관의 좌석은 줄당 크기가 정해져 있다.
만약 영화 관람 도중에 누군가 나간다 해도
영화관의 좌석 자리는 바뀌지 않는다.
이것 외로도, 영화관의 좌석 자리를 줄이려면 대 공사를 해야한다.
또한 영화가 시작하고 어둑어둑한 상태의 영화관에서 특정한 사람을 찾는 것은 상당히 어렵다. 처음 자리부터 하나하나 살펴보아야 한다.
✅ 리스트 == 줄서기
리스트는 줄서기이다.
만약에 3번째 있는 팽귄을 제거한다면
그 위치로 4번째 있는 팽귄이 순서를 지키게 된다.
이외에도 추가와 제거를 함에 있어서도 상당히 간단하다.
리스트의 시작점으로 들어갈 수 있고
리스트의 꼬리로 들어갈 수 있다. 이는 매우 빠르다.
하지만 원하는 타겟의 인덱스를 조회하는 것은 상당히 두려운 일이다.
요소 하나하나를 다 검사해야 하기 때문이다. 리스트를 linkedList 그리고 배열을 JAVA의 개념을 빌려 ArrayList라고 가정하면 LinkedList는 ArrayList보다 느리다.
✨ 자바스크립트는??
자바스크립트의 배열은 리스트를 추가하고 삭제하는 기능들을 내장 프로토타입 메소드로 가지고 있다. 즉 자바스크립트의 배열은 리스트라고 볼 수 있다.
자바스크립트 배열의 Property를 보면 일반 배열과 다른 것을 알 수 있다.
자바스크립트의 배열은 특별한 유형의 객체 라고 할 수 있다
인덱스가 프로퍼티 키key로 작용하는 동시에 length 프로퍼티를 통해 배열의 크기를 알 수 있다.
또한 배열의 각 요소는 객체의 프로퍼티 값value로 취급된다.
이로 인해 자바스크립트 배열은 다양한 타입의 값을 포함할 수 있다.
이외에도 리스트가 주는 삽입, 삭제등의 기능을 더 편리하게 할 수 있는 다양한 프로토타입 메소드들을 통해서 리스트의 OPERATION을 사용할 수 있다.
이러한 이유는 자바스크립트가 유저 친화적인 언어를 목적으로 만들어졌기 때문이다.
또한 기본적인 Static 배열과는 다르게 우리는 배열의 크기를 정해주지 않아도 배열에 요소를 추가할 수 있다.
어떻게 가능할까??
이러한 특징은 바로 자바스크립트의 배열이 동적배열이기 때문이다.
❓동적배열이란?
동적배열이란 Size를 자동적으로 Resize하는 배열이라고 할 수 있다.
미리 예상한 것 보다 더 많은 수의 Data를 저장하는라 Array의 Size를 넘어서게 됐다면,
평소 Static Array가 Compile 단계에서 Size를 확정 짓는 것과는 다르게
Dynamic Array는 Runtime 단계에서 Resize가 가능하기 때문에 유연하게 데이터를 저장할 수 있다.
이 Resizing을 하는 과정에서 방식은 주로 Doubling에 의해 일어난다.
❓더블링?
더블링이란 데이터를 추가 (O(1))하거나 메모리를 초과하게되면 기존 배열의 Size보다 2배 더 큰 배열을 선언하고 데이터를 일일히 옮기는 (O(n))방법이다.
이렇게 더블링을 통해 Dynamic Array는 우리가 배열의 크기를 초과해도 계속해서 데이터를 추가할 수 있도록 만들어주고 있었던 것이다...!
✨ 결론
: 자료구조를 공부하는 목적은 가장 최적의 자료구조를 활용하는 것이다. 즉 사용자가 원하는 OPERATION을 시간복잡도 개념에서 가장 빠르고 효율적으로 사용할 수 있는 자료구조를 선택하는 것이 목적이라고 할 수 있다.
