자료구조 정리

작성중

초안: 2019-05-12
1차 수정: 2019-06-27

개요

자료(data)는 정수, 실수, 문자, 등으로 구분할 수 있는 것들이다. 이 자료들을 효율적으로 저장하거나, 저장된 자료들을 활용하기 위해 자료구조라는 것이 등장하였다.

자료구조란 메모리에 자료를 저장하고, 메모리로부터 불러오는 방식을 의미한다. 보통 자료구조에 저장되는 자료를 원소(element)라고 부른다.

자료 구조의 기본 형태

대표적으로 배열(Array)과 연결 리스트(Linked List)가 있다.

배열

<그림 1. 배열의 논리적 구조>

<그림 2. 메모리 공간에 배치된 배열>

배열의 특징은 다음과 같다.

• 동일한 타입의 자료를 저장.
• 메모리 상에 자료가 연속적으로 저장이 되어 있음.
• Index라고 불리는 키(key)값으로 배열에 저장된 자료, 즉 원소(element)에 임의 접근이 가능함.
• 일반적으로 프로그램 실행 중에 크기를 변경할 수 없음. 즉, 정적인 특성을 지님.
• 연결리스트에 구조가 간단하고 구현이 쉽다.

연결 리스트

<그림 3. 연결 리스트의 논리적 구조>

<그림 4. 메모리 공간에 배치된 연결리스트>

연결리스트의 특징은 다음과 같다.

• 동일한 타입의 자료를 저장
• 메모리 상에 자료가 연속적으로 저장되어 있지 않으며, 하나의 원소는 다음 원소의 주소를 가지고 있음.
• 원소(element)에 접근하기 위해서 모든 원소를 순회해야 하는 순차 접근이 필요함.
• 프로그램 실행 중에 크기를 변경할 수 있음. 즉, 동적인 특성을 지님.
• 배열에 비해 구조가 복잡하고 구현하기 어렵다.

추상 자료형

한편 자료구조에서 수행되는 연산과 동작만 정의한 것을 추상 자료형(Abstract Data Type; ADT)라고 부르며, 추상 자료형은 배열 또는 연결리스트를 기반으로 구현된다.

선형 자료 구조

선형 자료구조는 자료가 선형적으로 배치되어 있다는 특징이 있다. 선형적이라는 뜻은 마치 줄줄이 엮은 곶감이나, 쌓여있는 접시와 같이 나란히 줄을 서있는 것을 의미한다. 다음과 같은 종류가 있다.

• 선형 리스트(Linear List)
• 자료를 나열한 형태다.
• 스택(Stack)
• 나중에 들어온 데이터가 먼저 나온다. (Last In First Out; LIFO)
• 큐(Queue)
• 먼저 들어온 데이터가 먼저 나온다. (First In First Out; FIFO)
• 우선순위 큐(Priority Queue)
• 입력된 데이터는 우선순위에 따라 정렬된다.
• 우선 순위가 높은 데이터가 먼저 나온다.

트리

트리는 선형 자료 구조와는 다르게 계층적인 구조를 가지고 있다. 트리에서는 자료 하나가 저장되는 단위를 노드(node)라고 부르는데, 이 노드는 하위 노드를 하나 이상 가질 수 있다. 그리고 하위 노드 또한 노드이므로 하위 노드를 가질 수 있다.
트리의 대표적인 예로는 조직도, 파일 구조, 등이 있다.

• 트리
• B트리
• 이진탐색트리
• 힙
• R트리

그래프

그래프는 자료 간의 연결 관계를 표현할 수 있는 자료 구조이다. 트리와 동일하게 그래프 또한 노드가 자료의 기본 단위인데, 이 노드는 다른 노드와 연결될 수 있다. 그래프의 대표적인 예시는 네트워크 망, 지하철 노선도, 등이 있다.

해쉬 함수와 해시 테이블

해쉬 함수는 임의의 키 값을 일정한 크기 또는 길이를 가진 값으로 매핑하는 함수이다. 그리고 해쉬 함수를 통해 변환된 값을 인덱스로 삼아 테이블에 임의로 접근하여 원소를 얻을 수 있다. 이 때 해쉬 함수를 통해 변환되기 전의 값을 키 값, 변환된 후의 값을 해쉬 값이라고 부르며, 해쉬 값을 키로 사용하는 테이블을 해쉬 테이블이라고 부른다.
해쉬 함수는 빠르다는 장점은 있지만, 해쉬 값은 길이가 고정되어 있으므로 키 값이 중복되는 경우가 발생한다. 그래서 해쉬 함수를 만들 때는 중복되는 키 값을 최대한 줄이는 것이 관건이며, 해쉬 테이블을 만들 때는 중복되는 키 값을 처리하는 기능을 마련하는 것이 중요하다.