자료구조의 궁극적인 목적은 어떤 종류의 자료구조를 언제 쓰는게 제일 좋은지 알기 위함이다.
필요한 경우 자신이 구현해야 할 수도 있기 때문에, 기본적인 자료구조의 원리와 장단점을 잘 알아두어야 한다.
그리고 주변 개발자들은 다 이해하고 술술 말하는데 나만 까먹어서 어버버하면 머쓱하기 때문에 잘 알아두어야 한다.
Array
- 처음 변수를 선언할 때 명시한 변수 타입의 크기만큼 큰 메모리 영역 (chunk) 이 통째로 생긴다.
- 즉, 해당 변수에 대한 값은 실제로 서로 붙어있는 형태로 메모리에 저장된다.
- 얼마나 큰 영역이 생기는지는 C++ 기준
sizeof(type)으로 확인할 수 있다.
- Array의 가장 큰 장점은 n번째 index에 O(1)의 시간복잡도로 접근이 가능하다는 점이다.
- 그 어떤 부가적인 확인을 할 필요 없이,
Arr[4]인 경우 바로 알파벳 E가 나온다. - 또, 실제로 해당 주소 바로 옆에 D와 F가 존재하기 때문에 주변 값을 가져오기 쉽다.
- 실제로 Array는 한 주소에 접근할 시 그 주변 주소에 대한 값을 캐싱하는 성질 때문에, 주변 요소 접근이 굉장히 가볍고 빠르다.
- 이런 성질로, for문으로 구조에 접근하는 것이 부담스럽지 않은 형태라고 할 수 있다.
- 그 어떤 부가적인 확인을 할 필요 없이,
- 처음 Array를 공부할 때, 가장 헷갈렸던 점이 '주소가 바로 옆에 인접해 있다' 라는 성질이었는데, 이게 추상적인 의미라고 생각해 Linked List와 헷갈렸다. 애초에 메모리 자체가 상상으로 접근해야 하는 영역이었기 때문이다.
- 헷갈릴 필요 없이, Array로 넣은 요소들은 실제로 메모리에 물리적으로 붙어있다!
Linked List
- Array와는 다르게 head (요소의 정보) + pointer (다음 요소의 주소 정보) 로 이루어져 있다. 이를 합쳐서 노드 (node) 라고 부른다.
- 이 노드들은 메모리가 멀리 떨어져있다. head인 A는 다음 요소인 B 가 어느 은하계에 떨어져있는지 전혀 알지 못 한다.
- B 가 어디에서 살고 있는지 알려주기 위해 pointer가 존재한다. 마지막 요소의 pointer는 NULL.
- 그런 이유로, Linked List는 실제 정보(head, A)뿐만 아니라 주소값(pointer)이라는 정보를 하나 더 들고 있어야 한다.
- 그리고 Array와 다르게 n번째 index에 접근할 때, A의 pointer에 들려서 다음 주소 찾아가고.. B의 pointer에 들려서 다음 주소 찾아가고.. 를 반복해야 하기 때문에 O(N)의 시간복잡도를 가지게 된다.
- 요소들끼리 붙어있지 않기 때문에, Array와 달리 캐시가 불가능하다.
- 이런걸 왜 쓰는가?
- 요소의 삽입과 삭제가 매우 빠르다.
- B 다음에 Z라는 요소를 추가하고 싶을 때,
- Array는 C, D, E의 주소를 각각 하나씩 밀고 B 다음에 Z를 넣어야 한다. 뒤에 있는 요소가 많으면 많을수록 슬퍼진다.
- Linked List는 B의 pointer 값을 수정하고, Z에 새로운 pointer 값을 넣기만 하면 된다. 뒤에 아무리 많은 요소가 있더라도 동일하다.
Tip
- 인덱스에 접근하며 요소를 검사하거나 확인해야 하는 구조의 경우 Array, 데이터를 추가하고 삭제하는 작업이 자주 일어나는 구조의 경우 Linked List를 활용하는 것이 좋다.
- Linked List의 경우 삽입과 삭제를 제외하고는 장점이 없어 보일 수 있는데, 실제 데이터를 다룰 때는 index 검색보다는 데이터의 삽입 삭제가 훨씬 중요하고 자주 일어나는 경우가 많기 때문에 자주 사용한다.
Stack
- Last In First Out 마지막에 들어간 요소가 제일 먼저 나오는 자료구조이다.
#include <stack>
int main() {
stack<int> s;
for(int i = 0; i < 4; i++) {
s.push(i); // [0, 1, 2, 3]
}
s.pop(); // Stack에 제일 마지막에 들어간 값을 삭제하였으므로 [0, 1, 2]
}- 아래와 같은 상황들에 사용할 수 있다.
- 계속해서 추가되는 데이터 중 정상적인 것은 쌓고, 불량인 것은 빼야 하는 경우.
- 홈페이지 뒤로가기의 정보 저장, 최근 닫은 탭 정보 불러오기.
- 최근에 사용한 프리셋 불러오기 등.
Queue
- First In First Out 처음에 들어간 요소가 제일 먼저 나오는 자료구조이다.
#include<queue>
int main() {
queue<int> q;
for(int i = 0; i < 4; i++) {
q.push(i); // [0, 1, 2, 3]
}
q.pop(); // Queue에 제일 처음 들어간 값을 삭제하였으므로 [1, 2, 3]
}- 아래와 같은 상황들에 사용할 수 있다.
- 대기열과 같이 제일 먼저 진입한 사람을 넣어주어야 하는 경우.
- 컴퓨터의 태스크 처리 형식. 제일 먼저 요청받은 태스크를 진행해야 한다.