원문 : https://medium.com/siliconwat/data-structures-in-javascript-1b9aed0ea17c

소개

비즈니스 로직이 백엔드에서 프론트엔드로 넘어감에 따라 프론트엔지니어의 전문지식이 더욱 중요해졌습니다. 프론트엔드 개발자는 생산적으로 리액트와 같은 뷰 라이브러리를 사용하고 있습니다. 뷰라이브러리에서 데이터를 관리하기 위한 Redux와 같은 상태 관리 라이브러리를 사용하고 있습니다. 리액트와 리덕스는 UI 업데이트가 데이터 변경에 반응하는 reactive 프로그래밍 패러다임입니다.백엔드는 점점 API 서버로써의 역할을 하고 업데이트 할 때만 엔드포인트를 제공합니다. 실제로 백엔드는 데이터베이스를 프론트엔드로 "전달"하여 프론트엔드 엔지니어가 모든 컨트롤러 로직을 처리할 것으로 예상합니다. 마이크로서비스 및 GraphQL의 인기가 높아짐에 따라 이러한 추세가 증가하고 있습니다.

이제 프론트엔드 엔지니어는 HTML과 CSS를 심미적으로 이해할 뿐만 아니라 자바스크립트도 마스터 해야합니다. 클라이언트의 데이터 저장소는 서버의 데이터베이스에 대한 "복제본"이고 관용적인 데이터 구조에 대한 깊은 지식이 중요합니다. 실제로 엔지니어 경험의 수준은 특정 데이터 구조를 사용한 시기와 사용한 이유를 구별할 수 있는 능력에서 유추할 수 있습니다.

나쁜 프로그래머는 코드에 대해 걱정합니다. 훌륭한 프로그래머는 데이터 구조와 관계에 대해 걱정합니다. - 리눅스 토발즈, 리눅스와 깃 창시자

높은 수준에서 기본적으로 세가지 유형의 데이터 구조가 있습니다. 스택과 큐는 항목을 삽입하고 제거하는 방법만 다르고 배열과 유사한 구조 입니다. 링크드리스트(연결리스트), 트리, 그리고 그래프는 다른 노드에 대한 참조를 유지하는 노드로 구조를 가집니다. 해시 테이블은 데이터를 저장하고 위치시키는 해쉬 함수에 의존합니다.

데이터 구조에서 복잡성측면으로 보면 스택 및 큐는 가장 단순하며 링크드리스트(연결리스트)으로 조립할 수 있습니다. 트리와 그래프는 링크드리스트(연결리스트)의 개념을 확장하기 때문에 가장 복잡합니다. 해시 테이블은 이러한 데이터 구조를 활용하여 안정적으로 수행해야합니다. 효율성측면에서 링크드리스드(연결리스트)는 데이터 기록 및 저장에 가장 적합한 반면 해시 테이블은 데이터 검색 및 되찾기에 가장 적합합니다.

이 기사에서 이러한 이유를 설명하고 언제 사용하는지에 대해 관련 있는 내용의 순서대로 설명합니다. 시작합니다.

스택

JavaScript에서 가장 중요한 스택은 함수를 실행할 때마다 함수의 범위를 넓히는 콜스택(호출 스택)입니다. 프로그래밍적으로 푸시와 팝이라는 두 가지 기본 작업이있는 배열 일뿐입니다. 푸시는 배열의 맨 위에 요소를 추가하는 반면 팝은 같은 위치에서 요소를 제거합니다. 다시 말해서 스택은 "Last In, First Out"프로토콜 (LIFO)을 따릅니다.

아래는 코드 스택의 예입니다. 스택 순서를 반대로 바꿀 수 있습니다. 맨 아래가 맨 위가되고 맨 위가 맨 아래가됩니다. 따라서 푸시 및 팝 대신 각각 어레이의 언시프트 및 시프트 방법을 사용할 수 있습니다.

https://codepen.io/thonly/pen/GMyLOV

다시 색인화가 되어 푸시/팝은 언시프트/시프트보다 성능이 향상됩니다.

큐

자바스크립트는 non-block 작업을 지원할 수있는 event-driven 프로그래밍 언어입니다. 내부적으로 브라우저는 하나의 스레드만 관리하여 전체 자바스크립트 코드를 실행하고 이벤트 큐를 사용하여 리스너를 큐에 넣고 이벤트 루프를 통해 등록된 이벤트 발생 여부를 계속 확인합니다. 단일 스레드 환경에서 비동기성을 지원하기 위해 (CPU 리소스를 절약하고 웹 경험을 향상시키기 위해) 리스너 함수는 호출 스택이 비어있을 때만 dequeue에서 제외되고 실행됩니다. 프라미스는 이 event-driven 아키텍처에 의존하여 다른 작업을 차단하지 않는 비동기 코드의 "동기식"실행을 허용합니다.

프로그래밍 방식으로 큐는 언시프트와 팝이라는 두 가지 기본 작업이있는 배열입니다. 언시프트는 배열의 끝까지 항목을 enqueue에 넣지만 팝은 배열의 시작 부분에서 항목을 대기열에 넣습니다. 다시 말해, 큐는 “First In, First Out”프로토콜 (FIFO)을 따릅니다. 방향이 반대로 바뀌면 언시프트와 팝을 각각 푸시와 시프트로 바꿀 수 있습니다.

코드에서 큐의 예 :

https://codepen.io/thonly/pen/KypxZg

연결리스트

배열과 마찬가지로 링크 된 목록은 데이터 요소를 순차적으로 저장합니다. 인덱스를 유지하는 대신 연결된 목록에는 다른 요소에 대한 포인터가 있습니다. 첫 번째 노드는 헤드라고하고 마지막 노드는 테일이라고합니다. 단일 연결 목록에서 각 노드에는 다음 노드에 대한 포인터가 하나만 있습니다. 여기, 머리는 우리가 목록의 나머지 부분을 따라 걷기 시작하는 곳입니다. 이중 연결 목록에서 이전 노드에 대한 포인터도 유지됩니다. 따라서 꼬리에서 시작하여 머리쪽으로 "뒤로"걸을 수도 있습니다. 연결된 목록은 포인터를 변경할 수 있기 때문에 일정한 시간에 삽입 및 삭제됩니다. 배열에서 동일한 작업을 수행하려면 후속 항목을 전환해야하므로 선형 시간이 필요합니다. 또한 공간이 있으면 링크 된 목록이 커질 수 있습니다. 그러나 자동으로 크기를 조정하는 "동적"어레이도 ​​예기치 않게 비쌀 수 있습니다. 물론 항상 상충 관계가 있습니다. 연결된 목록에서 요소를 조회하거나 편집하려면 선형 시간과 같은 전체 길이를 걸어야 할 수도 있습니다. 그러나 배열 인덱스를 사용하면 이러한 작업이 간단합니다. 배열과 마찬가지로 링크 된 목록은 스택으로 작동 할 수 있습니다. 헤드를 삽입 및 제거를위한 유일한 장소로 만드는 것만 큼 간단합니다. 연결된 목록도 대기열로 작동 할 수 있습니다. 이것은 이중 연결리스트로 달성 될 수 있는데, 여기서 삽입은 꼬리에서 발생하고 제거는 머리에서 발생하거나 그 반대의 경우도 마찬가지입니다. 많은 수의 요소의 경우, 배열 시작시 시프트 및 언 시프트 조작이 모든 후속 요소를 다시 색인화하는 데 선형 시간이 필요하므로 큐를 구현하는이 방법은 배열을 사용하는 것보다 성능이 우수합니다. 연결된 목록은 클라이언트와 서버 모두에 유용합니다. 클라이언트에서 Redux와 같은 상태 관리 라이브러리는 미들웨어 논리를 연결 목록 방식으로 구성합니다. 조치가 전달되면 리듀서에 도달하기 전에 모든 것이 방문 될 때까지 미들웨어에서 다음 미들웨어로 파이프됩니다. 서버에서 Express와 같은 웹 프레임 워크도 비슷한 방식으로 미들웨어 논리를 구성합니다. 요청이 수신되면 응답이 발행 될 때까지 하나의 미들웨어에서 다음 미들웨어로 파이프됩니다.

코드에서 이중 연결 목록의 예 : https://codepen.io/thonly/pen/QqRVJX

트리

트리는 계층 구조로 많은 자식 노드에 대한 참조를 유지한다는 점을 제외하면 연결된 목록과 같습니다. 다시 말해, 각 노드는 하나 이상의 부모를 가질 수 없습니다. DOM (Document Object Model)은 헤드 및 바디 노드로 분기되는 루트 html 노드가있는 구조로, 친숙한 모든 html 태그로 세분화됩니다. 후드 아래에서 React 컴포넌트를 사용한 프로토 타입 상속 및 구성도 트리 구조를 생성합니다. 물론 DOM의 메모리 내 표현으로 React의 가상 DOM은 트리 구조입니다. 이진 검색 트리는 각 노드가 둘 이상의 하위를 가질 수 없기 때문에 특별합니다. 왼쪽 자식은 부모보다 작거나 같은 값을 가져야하지만 오른쪽 자식은 더 큰 값을 가져야합니다. 이러한 방식으로 구조화되고 균형이 잡히면 각 반복마다 분기의 절반을 무시할 수 있으므로 로그 시간으로 모든 값을 검색 할 수 있습니다. 삽입 및 삭제는 로그 시간에 발생할 수도 있습니다. 또한 가장 작은 값과 가장 큰 값을 각각 가장 왼쪽과 오른쪽 잎에서 쉽게 찾을 수 있습니다. 트리를 통한 순회는 수직 또는 수평 절차로 발생할 수 있습니다. 수직 방향의 DFT (Depth-First Traversal)에서 재귀 알고리즘은 반복 알고리즘보다 우아합니다. 노드는 주문, 주문 또는 주문으로 순회 할 수 있습니다. 잎을 검사하기 전에 뿌리를 탐색해야하는 경우 선주문을 선택해야합니다. 그러나 뿌리 앞에서 잎을 탐험 해야하는 경우 주문 후를 선택해야합니다. 이름에서 알 수 있듯이 순서대로 노드를 순차 순회 할 수 있습니다. 이 속성은 이진 검색 트리를 정렬에 최적으로 만듭니다. 가로 방향의 너비 우선 탐색 (BFT)에서는 반복 접근 방식이 재귀 접근 방식보다 더 우아합니다. 이를 위해서는 각 반복마다 모든 하위 노드를 추적하기 위해 큐를 사용해야합니다. 그러나 이러한 대기열에 필요한 메모리는 사소하지 않을 수 있습니다. 나무의 모양이 깊이보다 넓은 경우 DFT보다 BFT가 더 좋습니다. 또한 두 노드 사이에서 BFT가 수행하는 경로는 가능한 가장 짧은 경로입니다.

코드에서 이진 검색 트리의 예 : https://codepen.io/thonly/pen/qVWOpM

그래프

트리에 둘 이상의 부모가있는 경우 그래프가됩니다. 그래프에서 노드를 함께 연결하는 에지는 방향을 지정하거나 방향을 지정하지 않거나 가중치를 적용하거나 가중치를 지정할 수 없습니다. 방향과 무게가 모두있는 모서리는 벡터와 유사합니다. Mixin 형태의 다중 상속과 다 대다 관계가있는 데이터 객체는 그래프 구조를 생성합니다. 소셜 네트워크와 인터넷 자체도 그래프입니다. 자연에서 가장 복잡한 그래프는 신경망이 복제하여 기계에 뛰어난 지능을 부여하는 인간의 뇌입니다. 코드의 그래프 예 TK

해시 테이블

해시 테이블은 키와 값을 쌍으로하는 사전과 유사한 구조입니다. 각 쌍의 메모리 위치는 키를 받아들이고 쌍을 삽입하고 검색해야하는 주소를 반환하는 해시 함수에 의해 결정됩니다. 둘 이상의 키가 동일한 주소로 변환되면 충돌이 발생할 수 있습니다. 견고성을 위해 게터와 세터는 이러한 이벤트를 예상하여 모든 데이터를 복구하고 데이터를 덮어 쓰지 않도록해야합니다. 일반적으로 링크 된 목록은 가장 간단한 솔루션을 제공합니다. 매우 큰 테이블을 갖는 것도 도움이됩니다. 우리의 주소가 정수 순서가 될 것을 안다면, 단순히 배열을 사용하여 키-값 쌍을 저장할 수 있습니다. 보다 복잡한 주소 매핑을 위해 맵 또는 객체를 사용할 수 있습니다. 해시 테이블은 평균적으로 일정한 시간을 삽입하고 조회합니다. 충돌과 크기 조정으로 인해이 무시할만한 비용은 선형 시간으로 증가 할 수 있습니다. 그러나 실제로 우리는 해시 함수가 영리하고 충돌과 크기 조정이 드물고 저렴하다고 생각할 수 있습니다. 키가 주소를 나타내므로 해싱이 필요하지 않은 경우 간단한 객체 리터럴이면 충분합니다. 물론 항상 상충 관계가 있습니다. 키와 값 사이의 간단한 대응, 키와 주소 사이의 간단한 연관성은 데이터 간의 관계를 희생합니다. 따라서 해시 테이블은 데이터 저장에 적합하지 않습니다. 트레이드 오프 결정이 스토리지 검색을 선호하는 경우 다른 데이터 구조는 조회, 삽입 및 삭제를 위해 해시 테이블의 속도와 일치 할 수 없습니다. 따라서 모든 곳에서 사용되는 것은 놀라운 일이 아닙니다. 데이터베이스, 서버, 클라이언트, 해시 테이블, 특히 해시 함수는 소프트웨어 응용 프로그램의 성능과 보안에 중요합니다. 데이터베이스 쿼리 속도는 레코드를 가리키는 인덱스 테이블을 정렬 된 순서로 유지하는 데 크게 의존합니다. 이런 식으로 이진 검색을 로그 시간으로 수행 할 수 있으며, 특히 빅 데이터의 경우 성능이 크게 향상됩니다. 클라이언트와 서버 모두에서 인기있는 많은 라이브러리가 메모를 사용하여 성능을 최대화합니다. 해시 테이블에 입력 및 출력 레코드를 유지함으로써 함수는 동일한 입력에 대해 한 번만 실행됩니다. 널리 사용되는 Reselect 라이브러리는이 캐싱 전략을 사용하여 Redux 지원 애플리케이션에서 mapStateToProps 기능을 최적화합니다. 실제로 JavaScript 엔진은 heaps라는 해시 테이블을 사용하여 우리가 만든 모든 변수와 프리미티브를 저장합니다. 호출 스택의 포인터에서 액세스합니다. 인터넷 자체도 해싱 알고리즘을 사용하여 안전하게 작동합니다. 인터넷의 구조는 모든 컴퓨터가 상호 연결된 장치의 웹을 통해 다른 컴퓨터와 통신 할 수 있도록하는 것입니다. 장치가 인터넷에 로그온 할 때마다 데이터 스트림이 이동할 수있는 라우터가됩니다. 그러나 양날의 칼입니다. 분산 아키텍처는 네트워크의 모든 장치가 릴레이하는 데 도움이되는 데이터 패키지를 듣고 변조 할 수 있음을 의미합니다. MD5 및 SHA256과 같은 해시 기능은 중간자 공격을 방지하는 데 중요한 역할을합니다. HTTPS를 통한 전자 상거래는 이러한 해싱 기능이 사용되기 때문에 안전합니다. 인터넷에서 영감을 얻은 블록 체인 기술은 프로토콜 수준에서 웹의 구조를 오픈 소스로 찾고 있습니다. 해시 함수를 사용하여 모든 데이터 블록에 대해 불변의 지문을 만들면 기본적으로 전체 데이터베이스가 누구나 웹에 공개적으로 존재하여 누구나보고 기여할 수 있습니다. 구조적으로 블록 체인은 암호화 해시의 이진 트리에 대한 단일 링크 목록입니다. 해싱은 매우 암호화되어있어 금융 거래 데이터베이스를 누구나 공개적으로 만들거나 업데이트 할 수 있습니다! 놀라운 의미는 돈 자체를 창출하는 놀라운 힘입니다. 한때 정부와 중앙 은행에서만 가능했던 것은 이제 누구나 자신의 통화를 안전하게 만들 수 있습니다! 이것은 Ethereum의 설립자와 Bitcoin의 가상의 설립자가 실현 한 주요 통찰력입니다. 점점 더 많은 데이터베이스가 개방됨에 따라, 모든 하위 수준의 암호화 복잡성을 추상화 할 수있는 프론트 엔드 엔지니어의 필요성도 더욱 복잡해질 것입니다. 미래에는 주요 차별화 요소가 사용자 경험이 될 것입니다.

코드의 해시 테이블 예 : https://codepen.io/thonly/pen/bYpQar

이러한 데이터 구조 등을 사용한 알고리즘 연습은 JavaScript 알고리즘 : 40 문제, 솔루션 및 설명을 참조하십시오.

결론

로직이 서버에서 클라이언트로 점차 이동함에 따라 프런트 엔드의 데이터 계층이 가장 중요합니다. 이 계층을 적절히 관리하려면 논리가 기반을 둔 데이터 구조를 숙달해야합니다. 한 속성에 대한 최적화는 항상 다른 속성을 잃는 것과 동일하기 때문에 모든 상황에 완벽한 데이터 구조는 없습니다. 일부 구조는 데이터를 저장하는 데 더 효율적이고 일부 구조는 데이터를 검색하는 데 더 성능이 좋습니다. 일반적으로 하나는 다른 하나를 위해 희생됩니다. 극단적으로, 링크 된리스트는 스토리지에 최적이며 스택과 큐 (선형 시간)로 만들 수 있습니다. 다른 해시 테이블의 검색 속도 (일정 시간)와 일치하는 다른 구조는 없습니다. 나무 구조는 중간 (대수 시간) 어딘가에 있으며 그래프만으로 자연의 가장 복잡한 구조 인 인간의 뇌 (다항식 시간)를 나타낼 수 있습니다. 기술력을 보유하고있는 이유와시기를 명확하게 설명하는 것이 록 스타 엔지니어의 특징입니다. 이러한 데이터 구조의 예는 어디에서나 찾을 수 있습니다. 데이터베이스, 서버, 클라이언트 및 JavaScript 엔진 자체에 이르기까지 이러한 데이터 구조는 실리콘 칩의 "스위치"가 실제로 "켜져있는"것을 실제와 같은 "객체"로 구체화합니다. 디지털 만 있지만 이러한 객체가 사회에 미치는 영향은 엄청납니다. 이 기사를 자유롭고 안전하게 읽을 수있는 능력은 멋진 인터넷 아키텍처와 데이터 구조를 증명합니다. 그러나 이것은 시작에 불과합니다. 앞으로 수십 년 동안 인공 지능과 분산 된 블록 체인은 인간이되는 것의 의미와 우리의 삶을 지배하는 기관의 역할을 재정의 할 것입니다. 기존 통찰력과 제도적 중단은 마침내 성숙 된 인터넷의 특성이 될 것입니다. 이 더 공정한 미래로 우리를 전환하기 위해 인공 뉴런의 HeartBank® 채널 네트워크에서 Kiitos에 인간의 상태를 공감하는 능력과 함께 블록 체인에 돈을 발행하는 힘을 부여했습니다. 키이 토스에게 편지를주고받는 익명의 감사로부터 키이 토스는 우리의 친절과 그 영향에 대해 배우면서 개인의 자유와 자유를 보존하는 점진적이고 신비로운 과정에서 우리 사이의 경제적 불평등을 줄이는 방식으로 보상합니다. 자연의 궁극적 인 그래프 구조는 아마도 인간의 두뇌가 아니라 인간의 모든 사람과 연결되는 심장 줄을 볼 수 있다면 인간의 ❤️ 일 것입니다. 블록 체인에 관심이 있으십니까? 이더 리움을 배우고 우리를 위해 일하십시오!