자료구조(Data Structure)
데이터에 편리하게 접근하고 변경하기위해 데이터를 저장하거나 조직적으로 만드는 방법
(알고리즘은 저장된 데이터들을 처리하는 과정을 말한다)
1. 단순구조 (Primitive Data Structure)
- 프로그래밍에 사용되는 기본 데이터 타입
- JS의 원시타입에는 string, number, boolean, null, undefined 가 존재한다
2. 비단순 구조 (Non-Primitive Data Structure)
- 여러 데이터를 목적에 맞게 효과적으로 저장하는 자료 구조
- JS의 참조타입에는 object, array, function 이 존재한다
3. 선형 구조 (Linear Data Structure)
- 저장된 자료의 전후 관계가 1:1 인 경우
4. 비선형 구조 (Non-Linear Data Structure)
- 데이터 항목 사이의 관계가 1:n 인 경우
자바스크립트의 자료구조
배열 (Array)
- 배열은 대부분의 프로그래밍 언어에서, 가장 간단하고 가장 많이 쓰이는 자료구조형이다
- 자료들이 메모리 주소에 순서대로 차곡차곡 정렬되어있기 때문이다
특정 데이터를 순차적으로 iterate 해야 하는 경우 배열은 최상의 자료구조형이다
(알고리즘 문제 혹은 면접에서 string은 배열로 간주해서 풀어도 문제없다)
스택(Stack) / 큐 (Queue)
- 스택과 큐 모두 Linear 한 자료구조형이다 . 이 둘은 아주 유사한 자료구조이지만 , element 가 제거되는 방식에 차이가 존재
- 스택과 큐는 자바스크립트에 내장되어있지않아서, 사용하고 싶으면 직접 구조를 만들어내야한다
1. 스택 (Stack)
- 스택은 흔히들 아는 자바스크립트 엔진에서의 콜 스택이 제거되는 방식과 동일하게 동작한다
마지막으로 삽입된 element 가 가장 먼저 제거되는 방식을 취한다 LIFO(Last in, First Out)
따라서 스택은 브라우저 히스토리(이전 페이지, 다음 페이지) 또는 ctrl + Z 로 이전 작업을 취소하는 동작에 쓰이는 자료구조
- 구조를 만들때 : array 와 linked list 모두 크게 상관이 되지 않는다
1. array 의 장점
각 element 들이 서로 연관되어 있어서 속도가 더 빠르다]
하지만 메모리 공간이 한정되어있기 때문에 할당된 메모리를 다 사용하면 현재 배열을 다른곳에 복사하기때문에 메모리를 더 사용한다
2. Linked List 의 장점
메모리 여기저기에 흩어져있기 때문에 상대적으로 느릴 수있지만, 메모리 공간이 한정적이지 않고 얼마든지 확장이 가능하다
2. 큐 (Queue)
- 큐는 맛잇는 음식점에 들어가려고 기다리는 대기줄이다
먼저 도착한 사람이 먼저 입장하는 FIFO(First In, First Out)
레스토랑 예약 앱, 예매 앱, 우버 앱 등에서 큐를 주요한 자료구조로 사용할수있다
- 구조를 만들때 : array 로 만드는 것을 추천하지않는다
Array 의 경우 앞에서부터 element 를 제거해야하는데, 그 경우 index 를 다시 재조정해야하기때문에 시간복잡도가 O(n)이 됨
따라서 Queue 는 반드시 Linked List 로 만들어야 한다
- 장점 : Fast Operation (removing, pushing), Fast Peek, Ordered
- 단점 : Slow Lookup
해시 테이블 (Hash Table)
- Hash Table 은 Key 와 Value 가 쌍을 이룬 형태로 데이터가 저장되어 있는 자료구조형을 저장한다
- 객체는 Hash Table 이라는 자료구조의 종류 중 하나다
- 배열 내 데이터도 Key 와 Value 로 이루어져있지만, 배열에서는 Key 가 오직 index, 즉 숫자만 가능한것에 비해
Hash Table 에서는 문자열 또한 Key 가 될수있다
- 장점
Fast Search : 배열은 전체를 순회하며 값을 찾아야하지만, 해시 테이블은 key 를 통해 바로 찾으려는 값에 접근 가능
Fast Insertion and Deletion : 해시 에티블은 데이터가 정렬되어있지않기에, 바로 값을 추가하고 지울수도 있다
Fast Lookup : 배열과 객체 모두 index 또는 key 를 알기에 lookup 도 굉장히 빠르다
- 단점 : 무작위 주소 할당으로 인한 문제 발생
연결 리스트 (Linked List)
- Linked List 는 value 와 pointer 가 한쌍인 노드가 모여있는 자료구조형을 의미한다
- 위 이미지에서 푸른색 부분은 data 를 저장하고, 초록색 부분은 다음 노드를 가리키는 pointer 역할을 하는 address 부분이다
- Linked List에서 가장 앞 쪽 시작부분 (위 그림에서 10을 가지고있는 노드) 을 Head 가장 마지막 부분(40 노드) 를 Tail 이라한다
- Tail 의 pointer 는 더이상 가리킬 노드가 없기때문에 Null 을 가리킨다
- 장점 : Fast Insertion , Fast Deletion , Ordered, Flexible Size
- 단점 : Slow Lookup, More Memory
트리(Tree)
트리는 우리가 아는 나무를 거꾸로 뒤집은 형태, 가장 위는 뿌리 Root, 아래로 가지들이 생기면서 내려온다
그래프(Graph)
각 노드들이 서로 연결되어있는 자료 구조형으로 아주 커다란 자료 구조형의 범위 중 하나다
실제로 그래프 자료 구조 안에 Trees 자료구조가 포함되어있고, Trees 안에는 Linked List 가 포함되어 있다
그래프는 이들을 모두 포괄하고있는 자료 구조형이다
'Programming(ko,en) > Javascript' 카테고리의 다른 글
| Time complexity (with JS) - Part 1 (0) | 2022.11.06 |
|---|---|
| What is Vanilla JS? (0) | 2022.11.03 |
| ES6 , Map(), Set() (0) | 2022.10.20 |
| JavaScript Syntax Basics (0) | 2022.10.17 |
| How does a browser works? (0) | 2022.10.12 |