배열
- 같은 타입의 변수들로 이뤄졌으며, 크기가 정해져 있고, 인접한 메모리 위치에 있는 데이터를 모아놓은 집합
- 중복을 허용하고 순서가 있음
- 삽입 / 삭제 O(n), 탐색 O(1)
*배열은 요소의 인덱스만 알면 해당 요소를 끄집어낼 수 있지만 연결리스트는 요소들을 하나씩 탐색해가며 요소를 찾아야 함
벡터
- 동적으로 요소를 할당할 수 있는 동적 배열. 컴파일 시점에 개수를 모른다면 벡터를 사용
- 중복을 허용하고 순서가 있음. 랜덤 접근 가능
- 탐색과 맨 뒤의 요소를 삽입 / 삭제 O(1), 중간의 요소를 삽입 / 삭제 O(n)
- 크기가 고정적인 배열과 달리 러닝타임 때 배열의 크기가 변할 때 벡터를 사용
*삽입삭제가 번번히 일어나는 상황에서는 벡터던 배열이던 비효율적
연결 리스트
- 데이터를 감싼 노드를 포인터로 연결한 자료구조
- 필요할 때마다 노드를 만들어 연결하기 때문에 배열과 달리 길이가 자유로움. 배열보다 메모리를 좀 더 자유롭게 사용
- 중간에 데이터를 삭제해도 양 옆의 노드를 포인터로 새로 연결해주면 되기 때문에 시간복잡도가 낮음. 삽입/삭제가 빈번한 경우에 사용
- 삽입 / 삭제 O(1), 탐색 O(n)
스택
- 가장 마지막으로 들어간 데이터가 가장 첫 번째로 나오는 성질 후입선출 (LIFO, Last In First Out)의 성질을 가진 자료구조
- top으로 정한 곳을 통해서만 접근 가능
- top은 가장 위에 있는 요소를 가리키고, 삽입되는 새 요소는 top이 가리키는 요소 위에 쌓임
- 삭제는 top의 요소가 삭제
- top을 통해 삽입하는 연산을 push, 삭제하는 연산을 pop
- 스택에서 요소를 추출하려고 하는 것을 stack underflow, 스택의 크기를 초과하는 경우 stack overflow
- 삽입 / 삭제 O(1), 탐색 O(n)
- 활용예시
- 재귀함수
- 웹 브라우져 방문 기록
- 실행 취소 (undo)
- 후위 표기법 계산
- 수식의 괄호 검사 (연산자 우선순위 표현을 위한 괄호 검사)
큐
- 먼저 집어넣은 데이터가 먼저 나오는 후입선출 (FIFO, First In First Out)의 성질을 지닌 자료구조
- 한쪽 끝에서 삽입 작업이, 다른 쪽 끝에서 삭제 작업이 양쪽으로 이뤄짐
- 삭제 연산만 수행되는 곳을 front, 삽입연산이 수행되는 곳을 rear
- 큐의 요소는 rear 로 들어와서 front로 빠짐. 접근은 가장 첫 원소와 끝 원소로만 가능
- rear 에서 수행되는 삽입연산을 enQueue, front에서 수행되는 삭제연산을 dnQueue
- 삽입 / 삭제 O(1), 탐색 O(n)
- 활용예시
- CPU 작업을 기다리는 프로세스 관리
- 스레드 행렬 또는 네트워크 접속을 기다리는 행렬
- 너비 우선 탐색 (BFS) 구현
- 캐시 (Cache) 구현
728x90
