- Array
- Linked list
- Stack
- Queue
- Priority Queue - Hash
- Sparse, Dense
자료구조란?
자료구조란 여러 데이터들의 묶음을 어떻게 저장할 것이고, 사용할 것인지 정의한 것이다.
잘 정리된 이미지여서 가져와 보았다.
대부분의 자료구조는 특정한 상황에 문제를 해결하는 데에 특화되어 있다.
자료구조를 활용할 때, 자바스크립트 배열과 같은 미리 정의된 데이터 타입을 이용하여 자료구조를 유사하게 구현할 수 있다.
자료구조/알고리즘을 시각화 한 사이트
Array
특징
- 연속된 메모리 공간에 할당된다. (101번지, 102번지 ...)
- 배열의 배열은 matrix 라고 부르며 (2차원 배열) 이것 또한 메모리에 순차적으로 할당된다.
- 배열은 크기가 고정된 상태로 할당되며 크기를 바꿀 수 없다. (바꾸려면 아예 새롭게 만들어야 한다.)
- 요소를 순차적으로 저장하기 때문에 새로운 요소를 중간에 넣기 어렵다.
- 인덱스의 주소값을 이미 알고 있으므로 인덱스 접근으로 한번에 원하는 주소로 갈 수 있다.
시간 복잡도
- 탐색 :
- 맨 끝에 삽입, 삭제 :
- 맨 처음에 삽입, 삭제 : (삽입시 새 배열에 복사, 삭제시 한칸씩 땡기기)
- 중간에 삽입, 삭제 : (삽입시 새 배열에 복사, 삭제시 한칸씩 땡기기)
장단점
| 장점 | 단점 |
|---|---|
| - 탐색이 빠르다. | - 처음 및 중간 삽입/삭제가 느리다. - 메모리 낭비가 발생할 수 있다.(중간을 삭제하거나, 빈 공간이 많을 경우) |
사용
- 삽입/삭제가 일어나지 않을 때
- 탐색이 자주 필요할 때
- 크기가 정해져 있을 때
Linked List
특징
- 정해진 공간을 한번에 할당해야 하는 배열의 문제점을 해결하기 위해 탄생했다.
- 데이터를 하나 추가할 때마다 메모리 공간에 랜덤으로 할당된다. (101번지, 704번지, 506번지 ...)
- 데이터는 노드에 저장되고, 노드를 연결하여 만들어진다. 각 노드는 데이터와 다음 데이터의 주소를 가지고 있다.
- 데이터가 랜덤하게 할당되기 때문에 인덱스가 어떤 주소값을 가지고 있는지 모른다. 따라서 탐색 시 첫 노드부터 타고 들어가야 한다.
시간 복잡도
- 탐색 :
- 맨 끝에 삽입, 삭제 :
- 맨 처음에 삽입, 삭제 :
- 중간에 삽입, 삭제 : (탐색하는 시간에 따라. 대신 재할당이나 복사가 일어나지 않는다.)
장단점
| 장점 | 단점 |
|---|---|
| - 삽입과 삭제가 용이하다. - 메모리를 효율적으로 사용할 수 있다. | - 탐색이 느리다. |
사용
- 삽입/삭제가 자주 일어날 때
- 탐색이 자주 일어나지 않을 때
- 크기가 정해져 있지 않을 때
Stack
자료(data) 를 쌓는 자료구조. 가장 최근에 들어온 자료가 먼저 나간다.
First in Last Out, Last in First Out
사용
- 재귀를 사용하고자 할 때 (DFS)
- 브라우저의 뒤로 가기 & 앞으로 가기, 실행취소 등
Queue
가장 먼저 들어간 자료가 먼저 나오는 자료구조.
First in First Out, Last in Last Out
사용
- 자료가 입력된 순서대로 처리해야 할 필요가 있는 상황에서 사용한다. (BFS)
- Buffering
컴퓨터 장치들 사이에서 자료를 주고 받을 때 각 장치들 사이에 존재하는 속도의 차이나 시간 차이를 극복하기 위한 임시 기억 장치로 Queue 가 사용된다. 이것을 buffer 라고 하며 buffering 은 buffer queue 에 자료를 쌓는 것을 말한다. 예를 들어 유튜브에서 buffer queue 에 자료가 충분히 쌓인 후 (버퍼링 후) 자료(영상)를 출력한다.
Priority Queue
우선순위 큐 - 우선순위의 개념을 큐에 도입한 자료 구조.
데이터들이 우선순위를 가지고 있고 우선순위가 높은 데이터가 먼저 나간다.
Heap - 완전 이진 트리의 일종으로 우선순위 큐를 위하여 만들어진 자료구조이다.
Hash
Hash function
Hash table (= hash map)
Hash 의 사전적인 뜻 : chop and mix, 감자와 고기를 으깬 요리.
해시 함수 혹은 해시 알고리즘은 임의의 길이를 갖는 임의의 데이터를 고정된 길이의 데이터로 매핑하는 함수를 말한다. 이러한 해시 함수를 적용하여 나온 고정된 길이의 값을 해시값(해시 코드, 해시섬(sum), 체크섬)이라고 한다.
이미지 : Hash table | wikipedia
해시 테이블은 (Key, Value)로 데이터를 저장하는 자료구조 중 하나로 빠르게 데이터를 검색할 수 있는 자료구조이다.
해시 테이블이 빠른 검색속도를 제공하는 이유는 내부적으로 배열(버킷)을 사용하여 데이터를 저장하기 때문이다.
해시 테이블은 각각의 Key값에 해시함수를 적용해 배열의 고유한 index를 생성하고, 이 index를 활용해 값을 저장하거나 검색하게 된다. 여기서 실제 값이 저장되는 장소를 버킷 또는 슬롯이라고 한다.
Sparse, Dense
Sparse/Dense array 또는 Sparse/Dense matrix 라고 한다.
Sparse array 는 배열의 대부분의 요소가 0 일때를 말한다.
Dense array 는 반대로 배열의 대부분의 요소가 0이 아닌 value 일때를 말한다.
0의 비율과 value 의 비율을 각각 sparsity, density 라고 한다.
