선형 자료 구조

배열

• 같은 타입의 변수들로 이뤄졌으며, 크기가 정해져 있고, 인접한 메모리 위치에 있는 데이터를 모아놓은 집합
• 중복을 허용하고 순서가 있음
• 삽입 / 삭제 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) 구현