3.1   자료 구조의 분류¶

대표적인 자료 구조로는 배열, 연결 리스트, 스택, 큐, 해시 테이블, 트리, 힙, 그래프가 있다. 이들은 ‘논리적 구조’와 ‘물리적 구조’라는 두 관점에서 분류할 수 있다.

3.1.1   논리적 구조: 선형과 비선형¶

논리적 구조는 데이터 원소 사이의 논리적 관계를 드러낸다. 배열과 연결 리스트에서는 데이터가 일정한 순서로 배열되어 데이터 사이의 선형 관계를 나타낸다. 트리에서는 데이터가 위에서 아래로 계층을 이루어 ‘조상’과 ‘자손’ 사이의 파생 관계를 나타낸다. 그래프는 노드와 간선으로 이루어져 복잡한 네트워크 관계를 표현한다.

아래 그림(3-1)과 같이 논리적 구조는 크게 ‘선형’과 ‘비선형’으로 나뉜다. 선형 구조는 데이터가 논리적으로 일렬로 배열되어 있어 비교적 직관적이다. 비선형 구조는 이와 달리 일렬로 배열되지 않는다.

• 선형 자료 구조: 배열, 연결 리스트, 스택, 큐, 해시 테이블이 해당하며, 원소 사이에 일대일의 순서 관계가 있다.
• 비선형 자료 구조: 트리, 힙, 그래프, 해시 테이블이 해당한다.

비선형 자료 구조는 다시 트리 구조와 네트워크 구조로 나뉜다.

• 트리 구조: 트리, 힙, 해시 테이블이 해당하며, 원소 사이에 일대다 관계가 있다.
• 네트워크 구조: 그래프가 해당하며, 원소 사이에 다대다 관계가 있다.

그림 3-1   선형 자료 구조와 비선형 자료 구조

3.1.2   물리적 구조: 연속과 분산¶

알고리즘 프로그램이 실행될 때 처리 중인 데이터는 주로 메모리에 저장된다. 아래 그림(3-2)은 컴퓨터 메모리 모듈을 보여 주며, 검은색 칩마다 메모리 공간이 들어 있다. 메모리는 각 셀에 일정한 크기의 데이터를 저장할 수 있는 거대한 Excel 표라고 생각할 수 있다.

시스템은 메모리 주소를 통해 원하는 위치의 데이터에 접근한다. 아래 그림(3-2)과 같이 컴퓨터는 특정 규칙에 따라 표의 각 셀에 번호를 부여하여 모든 메모리 공간이 고유한 메모리 주소를 갖게 한다. 프로그램은 이 주소를 이용해 메모리의 데이터에 접근한다.

그림 3-2   메모리 모듈, 메모리 공간, 메모리 주소

메모리는 모든 프로그램이 공유하는 자원이다. 어떤 메모리 영역을 한 프로그램이 사용하면 보통 다른 프로그램은 동시에 사용할 수 없다. 따라서 자료 구조와 알고리즘을 설계할 때 메모리 자원은 중요한 고려 사항이다. 예를 들어 알고리즘의 최대 메모리 사용량은 시스템의 남은 메모리를 넘지 않아야 한다. 연속된 큰 메모리 공간이 부족하다면 분산된 메모리 공간에 저장할 수 있는 자료 구조를 선택해야 한다.

아래 그림(3-3)과 같이 물리적 구조는 데이터가 컴퓨터 메모리에 저장되는 방식을 나타내며, 연속 공간 저장(배열)과 분산 공간 저장(연결 리스트)으로 나뉜다. 물리적 구조는 데이터 접근, 갱신, 삽입, 삭제 등의 연산 방식을 근본적으로 결정한다. 두 물리적 구조는 시간 효율과 공간 효율에서 서로 보완적인 특징을 지닌다.

그림 3-3   연속 공간 저장과 분산 공간 저장

모든 자료 구조는 배열, 연결 리스트 또는 둘의 조합으로 구현된다는 점도 알아 두자. 예를 들어 스택과 큐는 배열이나 연결 리스트로 구현할 수 있으며, 해시 테이블 구현에는 배열과 연결 리스트가 함께 포함될 수 있다.

• 배열로 구현할 수 있는 것: 스택, 큐, 해시 테이블, 트리, 힙, 그래프, 행렬, 텐서(차원이 \(\geq 3\)인 배열) 등.
• 연결 리스트로 구현할 수 있는 것: 스택, 큐, 해시 테이블, 트리, 힙, 그래프 등.

연결 리스트는 초기화한 뒤에도 프로그램 실행 중에 길이를 조정할 수 있으므로 ‘동적 자료 구조’라고도 한다. 배열은 초기화한 뒤 길이를 바꿀 수 없으므로 ‘정적 자료 구조’라고도 한다. 다만 배열도 메모리를 다시 할당하면 길이를 바꿀 수 있어 어느 정도 ‘동적 특성’을 가질 수 있다.

댓글로 의견이나 질문, 제안을 남겨 주세요