선형 자료 구조
선형 자료 구조란 요소가 일렬로 나열되어 있는 자료 구조를 말합니다.
연결 리스트(Linked List)
각 노드가 데이터와 포인터를 가지고 한 줄로 연결되어 있는 방식으로 데이터를 저장하는 자료 구조입니다.
연결 리스트는 싱글 연결 리스트, 이중 연결 리스트, 원형 이중 연결 리스트가 있습니다. 맨 앞에 있는 노드를 헤드(head)라고 하며 마지막 노드는 null을 가리킵니다.
배열(Array)
배열은 같은 타입의 변수로들로 이루어져 있고, 크기가 정해져 있으며, 인접한 메모리 위치에 있는 데이터를 모아놓은 집합입니다. 중복을 허용하고 순서가 있습니다.
인덱스에 해당하는 원소를 빠르게 접근해야 하거나 간단한 데이터를 쌓고 싶을 때 사용합니다.
벡터(Vector)
벡터는 동적으로 요소를 할당할 수 있는 동적 배열입니다. 컴파일 시점에 개수를 모른다면 벡터를 써야 합니다. 또한 중복을 허용하고, 순서가 있고 랜덤 접근이 가능합니다.
직접 접근이라고 하는 랜덤 접근은 배열과 같은 순차적인 데이터가 있을 때, 임의의 인덱스에 해당하는 데이터에 접근할 수 있는 기능입니다. 이는 데이터를 저장된 순서대로 검색해야 하는 순차적 접근과는 반대입니다.
스택(Stack)
먼저 넣은 데이터가 나중에 꺼내진다는 개념으로, First-In Last-Out(FILO) 구조입니다. 브라우저에서 '이전' 키를 통해 이전 페이지로 이동하는 것도 스택을 이용한 접근이라 할 수 있습니다.
큐(Queue)
스택과 비슷하지만 데이터의 입력과 출력의 방향이 다른 자료구조입니다. 스택은 먼저 들어간 데이터가 나중에 나오는 구조지만, 큐는 먼저 들어간 데이터가 먼저 나오는 First In First Out(FIFO) 구조입니다.
비선형 자료 구조
그래프(Graph)
그래프는 정점과 간선으로 이루어진 자료 구조를 말합니다.
어떠한 곳에서 어떠한 곳으로 무언가를 통해 간다고 했을 때, '어떠한 곳'은 정점(vertex)이 되고, '무언가'는 간선(edge)이 됩니다.
트리(Tree)
정점과 간선을 이용해 사이클을 이루지 않도록 구성한 그래프의 특수한 형태로, 계층이 있는 데이터를 표현하기에 적합합니다.
루트 노드, 내부 노드, 리프노드 등으로 구성됩니다.
아래는 트리와 트리가 아닌 구조의 차이를 나타낸 이미지입니다.
힙(Heap)
힙은 완전 이진 트리 기반의 자료 구조이며, 최댓값 및 최솟값을 찾아내는 연산을 빠르게 하기 위한 자료구조입니다.
우선순위 큐(Priority Queue)
큐는 먼저 들어오는 데이터가 먼저 나가는 형식이지만, 우선순위 큐는 먼저 들어오는 데이터가 아니라 우선 순위가 높은 데이터가 낮은 데이터보다 먼저 나가는 형태의 자료구조입니다. 우선순위 대기열이라고도 부릅니다.
우선순위 큐는 힙을 기반으로 구현됩니다.
맵(Map)
특정 순서에 따라 키와 매핑된 값의 조합으로 형성된 자료 구조입니다.
레드 블랙 트리 자료 구조를 기반으로 형성되고, 삽입하면 자동으로 정렬됩니다.
셋(Set)
셋은 특정 순서에 따라 고유한 요소를 저장하는 컨테이너이며, 중복되는 요소는 없고 오로지 희소한(unique) 값만 저장하는 자료 구조입니다.
해시 테이블(Hash Table)
해시 테이블은 무한에 가까운 데이터들을 유한한 개수의 해시 값으로 매핑한 테이블입니다. 이를 통해 작은 크기의 캐시 메모리로도 프로세스를 관리하도록 할 수 있습니다.
삽입, 삭제, 탐색 시 평균적으로 O(1)의 시간 복잡도를 가지며 unordered_map으로 구현합니다.
출처
면접을 위한 CS 전공지식 노트
https://suyeon96.tistory.com/31
