(번역) 자바스크립트 자료구조
October 9th 2018
이 포스팅은 개인적인 자료구조 학습을 위해 번역을 했습니다. 오역이 없게 하려 노력했지만, 번역한 일부 내용이 틀릴수도 있습니다. 그래도 학습에 도움이 되셨으면 좋겠습니다. :)
목차
- Introduction
- Stack
- Queue
- Linked List
- Tree
Introduction
웹개발에 있어 주요 로직이 벡엔드에서 프론트로 넘어오면서, 프론트엔드에 대한 전문 지식의 중요성이 점차 커지고 있습니다. 프론트엔트 개발자는 생산성 향상을 위해서 React와 같은 화면 구성을 위한 뷰 라이브러리를 사용합니다. 뷰 라이브러리는는 자료 관리를 위한 Redux와 같은 state 라이브러리에 의존합니다. React와 Redux는 프론트엔트 개발의 페러다임을 가져왔고, 데이터 변화에 따라 화면을 업데이트합니다. 점진적으로 벡엔드는 단순히 endpoint를 제공하고, 데이터를 받아 업데이트를 하는 API 서버 역할을 합니다. 실제로도 벡엔드에서 데이터베이스를 프론트로 전달하고, 프론트엔드 개발자가 필요한 로직을 짜는 일이 많습니다. microservices와 GraphQL의 인기가 이러한 트렌드를 반영하고 있습니다.
HTML과 CSS의 심미적 이해도뿐만 아니라, 프론트엔드 개발자라 하면 자바스크립트에 능숙해야합니다. 앞서 언급한 바와 같이, 클라이언트 측의 Datastore가 서버측의 데이터베이스를 그대로 가져오기 때문에, 자료구조에 대한 깊은 지식이 매주 중요합니다. 실제 개발자로서의 실력은 언제, 왜 특정한 자료구조를 사용하는지 구분할 수 있는 능력을 갖추었는지가 평가의 한 축이 될 수 있습니다.
기본적으로 자료구조는 크게 Stack, Queue, 유사배열 세 가지 타입이 있습니다. 이와 같은 자료구조는 데이터가 어떻게 추가되고 삭제되는지에 따라 구분됩니다. Linked Lists, Trees, Graphs는 다른 node를 참조하고 있는 node로 구조화 돼 있습니다. Hash Table은 hash function에 의존해 자료를 저장하고 찾습니다.
복잡성과 관련해서 Stack과 Queue가 가장 단순하며 Linked Lists로부터 구성될 수 있습니다. Tree와 Graphs는 Linked List의 컨셉을 확장한 것이기 때문에 가장 복잡합니다. Hash Table은 이들 자료구조를 효율적으로 사용하기 위해 이용합니다. 효율성과 관련해서, Linked Lists는 자료를 저장하는데 가장 최적화 되어 있으며, Hash Table은 자료를 찾고 가져오는데 효율적입니다.
자료구조에 있어서 why와 when을 설명하기 위해, 이 글은 위 유형의 순서에 따라 설명하겠습니다.
Stack
한가지 확실한 건 자바스크립트에서 가장 중요한 Stack은 함수를 호출할 때마다 새로운 Scope로 들어가는 Call Stack입니다. 프로그래밍적으로 보면 이것은 단순이 push와 pop에 근거한 배열입니다. Push는 새로운 요소를 배열의 맨 위에 추가합니다. 반면, Pop은 마지막 요소를 제거해 배열을 다시 원래대로 위치시킵니다. 다른 말로하면 후입선출입니다.('Last In, First Out'; LIFO)
아래는 Stack의 예제 코드입니다. 여기서 우리는 배열의 순서를 역으로 변경할 수 있습니다. push와 pop대신 unshift와 shift를 사용하면 위아래를 바꿀수 있습니다.
See the Pen Stacks in JavaScript by Thon Ly (@thonly) on CodePen.
## Queue 자바스크립트는 even-driven 프로그래밍 언어이며, 이것은 non-blocking operation을 가능하게 합니다. 내부적으로 자바스크립트는 한번에 한코드씩 실행을 하며(single-thread), event queue를 통해 lister를 추가하고, event loop로 등록된 event를 감지합니다. single-thread 환경에서 비동기 프로그래밍을 하기 위해서(CPU 자원을 아끼고, 사용자 경험을 더 좋게 하기 위해), listener function은 call stack이 빈 상태에서만 Queue에서 빠져나올수 있습니다. 자바스크립트의 Promise 또한 event-driven 구성에 의존하며 비동기적 코드를 동직적 스타일로 실행합니다.
프로그래밍적으로 Queue는 단순히 unshift와 pop으로 구성된 array입니다. unshift는 배열의 끝에 아이템을 추가하고, pop은 배열의 앞에 아이템을 제거합니다. 바꿔말하면, 선입선출입니다.('First In, First Out') 배열을 반대로 하고 싶으면, unshift와 pop대신 push와 shift를 사용할 수 있습니다. 아래는 Queue의 예제 코드입니다.
See the Pen Queues in JavaScript by Thon Ly (@thonly) on CodePen.
## Linked List Linked List는 배열과 유사하게 순서대로 데이터 요소를 저장합니다. 하지만, 인덱스 대신 다른 요소로의 Pointer를 가지고 있습니다. 첫번째 노드는 head라고하고, 마지막 노드를 tail이라고 합니다. Singly-linked list에서 노드는 오직 다음 노드만 가리키는 Pointer를 가지고 있습니다. 때문에 head가 데이터를 탐색하는 시작점이 됩니다. Doubly-linked list에서는 이전의 노드를 가리키는 Pointer 또한 가지고 있습니다. 때문에 tail에서 시작을 해 데이터를 거꾸로 탐색을 할 수 있습니다.
Linked List는 요소를 추가하고 삭제할 때 constant의 시간복잡도를 가지고 있습니다. 이것은 Pointer만 변경하면 되기 때문입니다. 동일한 작업을 Array에서 한다면 시간복잡도는 Linear가 됩니다. 수정되는 요소 다음의 요소들을 모두 재배치 해야하기 때문입니다. Linked List는 또한 저장 공간만 있다면 원하는 만큼 늘릴 수 있습니다. 반면, 동적배열에서도 동일한 작업은 시간 소요가 더 발생합니다. 물론, 모두 상대적인 특징이 있습니다. Linked List에서 데이터 검색을 하거나 수정을 위해서, 데이터 전체를 검토해야 하며 이것은 Linear의 시간복잡도가 소요됩니다. 배열에서 동일한 작업은 매우 간단하게 처리할 수 있습니다.
배열과 마찬가지로, Linked List으로 Stack을 구현할 수 있습니다. head만이 데이터의 추가 또는 삭제를 하는 역할을 하도록 설계하면 됩니다. Linked List는 Queue가 될 수도 있습니다. Doubly-linked list로 구현이 가능한데 head 또는 tail 한쪽에서만 데이터를 추가하고 반대쪽에서 데이터를 삭제하도록 설계하면 됩니다.
Linked list는 클라이언트, 서버 양쪽에서 모두 유용하게 사용할 수 있습니다. state management 라이브러리인 Redux는 미들웨어 로직에 Linked list 방식을 사용했습니다. 서버측에서는 Express가 미들웨어 구성에 Linked list 방식을 사용했습니다..
Doubly-linked list의 예를 든 코드는 아래와 같습니다.
See the Pen Linked List in JavaScript by Thon Ly (@thonly) on CodePen.
Tree
Tree는 Linked list와 유사합니다. 차이점은 Tree는 계층구조에 따른 여러 자식노드를 참조하고 있다는 점입니다. 바꿔말하면, 각 노드는 한 부모노드만 가질 수 있습니다. Tree 구조의 대표적인 예로는 DOM을 들 수 있습니다. html이라는 루트노드가 있고 그 밑으로 head, body가 있고 또 그 밑에 우리에게 익숙한 여러 html 태그가 있습니다. React의 Virtual DOM역시 트리구조입니다.
Binary Search Tree는 각 노드가 두 개의 자식노드만 가질 수 있다는 점에서 특별합니다. 왼쪽의 자식노드는 부모의 값과 같거나 작은 값만을 가집니다. 반면, 오른쪽의 자식노드는 부모의 값보다 큰 값을 가집니다. 값을 탐색할 때 한 번 연산 후 전체 데이터의 반은 무시해도 되기 때문에 시간복잡도 log n으로 탐색할 수 있습니다. 데이터의 추가 및 삭제 또한 log n의 시간복잡도를 가집니다. 최소값과 최대값은 데이터의 양쪽 끝에 위치하기 때문에 더 쉽게 찾을 수 있습니다.
트리 탐색은 수평적, 수직적으로 가능합니다. 깊이우선탐색(Depth-first-traversal; DFT)에서는 재귀용법이 반복문보다 더 선호됩니다. 노드 탐색은 pre-order, in-order, post-order 방식이 있습니다. 트리의 개별 잎보다 뿌리를 우선 탐색하고 싶다면 pre-order 방식을 사용합니다. 반대로, 뿌리보다 잎을 먼저 탐색하고자 한다면 post-order 방식을 사용합니다. 트리를 순차적으로 탐색하고 싶으면 in-order 방식을 사용하며, binary search tree sorting에 적합합니다.
Breadth-First Traversal(BFT; 너비우선탐색)은 재귀용법보다 반복문을 사용하는 것이 더 선호됩니다. 매 반복문마다 자식노드를 추적하기 위해 queue를 사용해야 하며, 이것은 별도의 메모리를 소비를 발생시킵니다. 만약 트리의 넓이가 깊이보다 크다면, DFT보다 BFT가 더 좋은 선택입니다. 그리고 BFT는 두 노드 중 선택을 해야할 때 더 짧은 거리의 노드를 선택합니다.
Binary Search Tree의 예제 코드는 아래와 같습니다.
See the Pen Binary Search Tree in JavaScript by Thon Ly (@thonly) on CodePen.