자료 구조

자료 구조란?

자료 구조는 컴퓨터 과학에서 효율적인 접근 및 수정을 가능케 하는 자료의 조직, 관리, 저장을 의미한다.

여러 종류가 있으며, 이러한 각각의 자료구조는 각자의 연산 및 목적에 맞추어져 있다.

(예를 들어 B-트리는 데이터베이스에 효율적이며, 라우팅 테이블은 네트워크에 일반적이다.)

 

자료 구조의 분류

구현에 따른 분류

• 배열
• 연결 리스트
• 튜플

형태에 따른 분류

 

• 선형(Linear) 자료 구조
  • 데이터 요소가 순차적으로 배열되는 자료구조
  • 단일 레벨(1:1)로 구성 → 한 번에 탐색 가능
  • 예) 배열, 스택, 큐, 연결 리스트

• 비선형 자료 구조
  • 하나의 자료 뒤에 여러개의 자료가 존재할 수 있는 자료구조
  • 멀티 레벨로 구성 → 효율적인 메모리 활용 가능
  • 예) 트리, 그래프, 힙

 

배열

정의 : 인덱스(번호)와 이에 대응하는 데이터들로 이루어진 자료구조

특징

• 메모리 상에 같은 타입의 자료가 연속적(순차적)으로 저장된다.
• 인덱스는 시작점으로부터 값이 저장되어 있는 상대적인 위치가 된다.

 

연결리스트

정의 : 각 노드가 데이터와 포인터를 가지고 한 줄로 연결되어 있는 방식으로 데이터를 저장하는 자료구조

특징

• 노드의 포인터가 다음이나 이전의 노드와의 연결을 담당한다.
• 노드의 중간 지점에서도 자료의 추가와 삭제가 O(1)의 시간에 달성 가능
• 특정 위치의 데이터를 검색하는 데 O(n)의 시간이 걸린다.

 

튜플

정의 : 셀 수 있는 수량(유한)의 순서 있는 열거

특징

• 보통 괄호 안에 쉼표로 구분되게 나열하여 표시한다. ex) (2, 4, 1, 3)
• 컴퓨터 과학에서 튜플은 어떤 요소의 집합, 혹은 테이블에서의 행(레코드)을 가리킨다.
• 순서가 있다. 즉 (1 ,2, 3)과 (3, 2, 1)을 다른 데이터 취급.

 

스택

정의 : ‘쌓여진 더미’ , 마지막에 들어온 데이터가 가장 먼저 나가는(LIFO) 구조를 가진 자료구조.

특징

• LIFO(Last In First Out)
• 아키텍처 수준에서 스택을 사용하는 것은 메모리의 할당 및 접근 수단을 의미한다.

용례

• 운영체제의 시스템 스택
  • 함수의 실행이 끝난 뒤, 자신을 호출한 함수로 돌아가는데, 이때 스택을 통해 복귀할 주소를 기억한다.
• 메모리 구조에서 지역 변수, 정적 변수 저장
  • 스택 영역은 함수의 호출과 함께 할당되며, 함수의 호출 완료 시 소멸.
• JavaScript의 Call Stack
  • 자바스크립트 엔진이 순차적으로 수행해야할 함수가 쌓이는 곳

 

큐

정의 : 먼저 집어 넣은 데이터가 먼저 나오는 FIFO(First In First Out) 구조를 가진 자료구조.

특징

• FIFO(First in First Out)
• 데이터가 입력된 시간 순서대로 처리해야 할 필요가 있는 상황에 이용된다. (ex. 프로세스 관리)

용례

• 메모리 구조에서 동적 할당
  • 사용자의 동적 할당에 기반하기 때문에 런타임에 크기가 결정된다.
• JavaScript의 Callback queue(Message Queue)(Task Queue)
  • 비동기 콜백 함수들이 대기하는 리스트

 

덱

정의 : 양쪽 끝에서 삽입과 삭제가 모두 가능한 자료 구조의 형태를 말함(스택 + 큐 : double ended queue 의 줄임말)

 

그래프

정의 : 정점(vertex)와 간선(vertex)로 구성된 자료구조

 

- 리스트 자료 구조

• 인접 리스트(Adjacency list)
  • 각 정점에 대해 인접한 정점들의 리스트를 가진다.

- 행렬 자료 구조

• 인접 행렬(Adjacency matrix)
  • 인접 행렬의 크기는 |V|⋅|V| 로 나타낸다.
  • 만약 x 정점에서 y 정점 사이 간선이 존재하면 1, 그렇지 않으면 0으로 나타낸다.

 

- 비순환 유향 그래프(DAG - Directed Acyclic Graph)

• 방향을 가진 그래프
• 비순환 그래프
• 관련 알고리즘 : 위상 정렬, SCC(강한 연결 요소; Strongly Connected Component)

 

트리

정의 : 그래프의 일종으로 순환이 없는 연결 그래프를 말한다. (비순환 무향/유향 그래프)

 

- 이진 트리

• 각각의 노드가 최대 두 개의 자식 노드를 가지는 트리 자료 구조이다.
• 용례
  • 효율적인 검색과 정렬을 위한 사용
  • 연관 분기 구조를 이용한 데이터 표현을 위한 사용
• 속성
  • 노드 개수 n은 2h+1 ≤ n ≤ 2^(h+1) - 1
• 탐색
  • 중위 순회, 전위 순회, 후위 순회, 레벨 순회
• 구현(표현 방법)
  • 1차열 배열 표현
  • 연결 리스트 표현

- 힙

• 최댓값 및 최솟값을 찾아내는 연산을 빠르게 하기 위해 고안된 완전 이진 트리 자료구조이다.
• 종류
  • 최대힙, 최소힙
  • 최대힙 : 부모 노드의 키 값이 자식 노드의 키 값보다 항상 큰 힙
  • 최소힙 : 부모 노드의 키 값이 자식 노드의 키 값보다 항상 작은 힙
• 응용
  • 우선순위 큐

- 이진 검색 트리

• 각 노드에 값이 있으며 이들은 순서가 있다.
• 왼쪽 서브트리에는 그 노드의 값보다 작은 값들을 지닌 노드들로 구성
• 오른쪽 서브트리에는 그 노드의 값보다 큰 값들을 지닌 자식 노드들로 구성