JS_JS로 알아보는 자료구조

배열

자바스크립트에서 배열은 사실 진짜 Array가 아니다.

즉, 배열의 요소를 위한 각각의 메모리 공간은 동일한 크기를 갖지 않아도 되며 연속적으로 이어져 있지 않을 수도 있다. 배열의 요소가 연속적으로 이어져 있지 않는 배열을 희소 배열(sparse array)이라 한다.

자바스크립트에서의 배열은 파이썬의 리스트와 마찬가지로 추상 자료형이다.

추상자료형이란 어떻게 구현되었는지 크게 신경쓰지 않고 기능에만 집중하여 사용할 수 있는 자료형이다.

https://codermun-log.tistory.com/267?category=927598 

---

자바스크립트의 배열은 배열이 아니다.

위에서 언급하였듯 정적/동적 배열의 경우 메모리의 특정영역에 연속적으로 공간을 할당하고 저장되는 특징이 있는데

자바스크립트의 배열에서는 메모리 공간이 연속적으로 이어져 있지 않을 수도 있다.(희소 배열)

console.log(Object.getOwnPropertyDescriptors([1, 2, 3]));
/*
{
  '0': { value: 1, writable: true, enumerable: true, configurable: true },
  '1': { value: 2, writable: true, enumerable: true, configurable: true },
  '2': { value: 3, writable: true, enumerable: true, configurable: true },
  length: { value: 3, writable: true, enumerable: false, configurable: false }
}
*/

아래와 같이 배열 [1, 2, 3]의 프로퍼티 값을 살펴보면 한 눈에 알 수 있다.

이처럼 자바스크립트에서의 배열은 인덱스를 프로퍼티의 키 값이며, length 프로퍼티를 갖는 특수한 객체이다.

---

즉, 자바스크립트 배열의 요소는 값 자체가 아닌, 프로퍼티 (속성)값이다.

자바스크립트에서는 사용 할 수 있는 모든 값은 객체의 프로퍼티 값이 될 수 있기 때문에 C언어의 배열과 다르게 다양한 타입의 요소를 가질 수 있게 되는 것이다.

파이썬에서의 리스트도 아래와 같이 다양한 타입의 요소를 가질 수 있으며 이때 요소도 값 자체가 아닌 값을 나타내는 레퍼런스를 참고하고 있는 값이기에 다양한 타입의 데이터를 요소로 가질 수 있었던 상황과 비슷하다.

---

그래서 자바스크립트의 배열은 무엇인가?

희소 배열이라 부를 뿐 그런 자료구조는 존재하지 않는다.

결론부터 말하자면 자바스크립트에서의 배열은 내부적으로 해시테이블로 구현되어 있는 객체라고 한다.

---

일반적인 배열 (C언어)에서는 메모리 주소만 알고 있다면 특정 값을 접근하는데 O(1)으로 굉장히 효율적이지만

특정 값을 탐색, 삽입, 삭제하는데는 O(n)으로 상대적으로 비효율적인 자료구조이다.

---

자바스크립트에서의 배열은 해시테이블로 구현되어 있기 때문에 인덱스로 요소에 접근하는 연산을 실행하는 경우

일반적인 배열보다 상대적으로 비효율적일 수 밖에 없는 구조이다.(상대적!!!)

이유는 일반적인 배열은 인덱스로 요소에 O(1)으로 빠르게 접근할 수 있지만, 자바스크립트에서의 배열은 해시테이블이기에 특정 요소를 찾기 위해선 추가로 해시 함수를 거치는 로직을 거쳐야하기 때문이라고 생각한다. 

하지만 이는 모던자바스크립트 엔진으로 상당부분 해결되었다고 하니 O(1)과 O(n) 사이라고 생각해도 되지 않을까 싶다.

일반적인 배열보다는 조금 느릴 수 있다로 받아들이면 될 것 같다.

---

하지만, 특정 요소를 탐색하거나 삭제하는 연산의 경우 배열보다 훨씬 효율적으로 수행할 수 있다.

즉, 자바스크립트 배열은 인덱스로 배열 요소에 접근하는 경우에는 일반적인 배열보다 느리지만

특정 요소를 탐색하거나 요소를 삽입 또는 삭제하는 경우에는 일반적인 배열보다 빠르다.

자바스크립트 배열은 인덱스로 접근하는 경우의 성능 대신 특정 요소를 탐색하거나 배열 요소를 삽입 또는 삭제하는 경우의 성능을 선택한 것이다.

---

SUMMARY

자바스크립트의 배열은 해시테이블로 구현된 객체이다.

자바스크립트의 배열은 인덱스로 배열 요소에 접근하는 경우 일반 배열보다 (상대적)으로 느리지만 탐색, 삽입, 삭제 연산에서는 일반 배열보다 효율적이다.

---

이는 해시테이블의 특징으로 아래 포스트를 참고하면 좋다!

https://codermun-log.tistory.com/265?category=927598 

해시테이블의 시간복잡도

 

배열(C, C++ .. 등의 일반적인 배열 !== js.arr)의 시간복잡도

---

링크드리스트(연결리스트)

앞서 배열에서는 삽입, 삭제 연산의 경우 O(n)으로 삽입과 삭제가 자주 일어나는 연산에는 적합하지 않았다.

그렇기에 이 문제를 해결하기 위해 링크드리스트가 고안되었다.

 

싱글리 링크드리스트

더블리 링크드리스트

Circular-Linked-List(환형 링크드리스트)

싱글리, 더블리 링크드리스트 참고(https://codermun-log.tistory.com/261?category=927598)

---

Circular-Linked-List

다른 2가지 링크드리스트에서  Tail Node가 Head Node로 연결되는 링크드 리스트이다.

메모리를 아낄 수 있으며 원형 큐를 만들때 사용되기도 한다.

특징으로는 링크드 리스트 중간 노드로 부터 시작해도 탐색을 시작하더라도 한바퀴 모두 탐색할 수 있다.

출처 : https://www.geeksforgeeks.org/sorted-insert-for-circular-linked-list/

JS로 구현해보기

 

 

---

출처 및 참고:

---

배열

https://nunucompany.tistory.com/29

[Javascript/JS] 자바스크립트에서의 배열과 시간복잡도

https://poiemaweb.com/js-array-is-not-arrray

Array | PoiemaWeb

https://codermun-log.tistory.com/260?category=927598 

배열

https://codermun-log.tistory.com/265?category=927598 

해시 테이블

https://codermun-log.tistory.com/267?category=927598 

추상 자료형(No 자료구조)

---