자료구조의 분류

자료구조(data structure)는 자료를 기억장치에 어떤 모양으로 이어 둘지 정한 틀입니다. 같은 자료라도 이어 둔 모양에 따라 찾고 넣고 빼는 방법과 빠르기가 달라져, 하려는 일에 맞는 모양을 골라야 합니다. 자료구조는 한 자료 뒤에 이어지는 자료가 하나뿐인 선형 구조와, 여럿일 수 있는 비선형 구조로 나뉩니다. 아래 그림은 같은 자료 일곱 개가 한 줄, 나무, 그물 모양으로 늘어서는 모습을 보이고, 끝에서 구조 이름 일곱을 두 갈래로 직접 나눠 보게 합니다.

1선형 구조 — 다음 자료가 하나뿐인 한 줄

선형 구조(linear structure)는 한 자료의 앞과 뒤에 자료가 하나씩만 이어지는 구조입니다. 그래서 자료가 한 줄로 늘어서고, 어느 자료든 '다음'이 하나로 정해집니다. 선형 구조 다섯은 모두 한 줄이고, 어디로 넣고 어디서 빼느냐로 갈립니다.

배열은 가운데에 넣으면 뒤의 자료를 한 칸씩 밀어야 하지만, 연결 리스트는 화살표만 바꿔 끼웁니다. 데크는 양쪽 끝이 열린 큐(double-ended queue)를 줄인 이름입니다. 자료에 따라 배열과 연결 리스트를 묶어 선형 리스트(linear list)라고도 부릅니다.

2비선형 구조 — 다음 자료가 여럿

비선형 구조(non-linear structure)는 한 자료 뒤에 자료가 여럿 이어질 수 있는 구조입니다. 한 줄로 세우려면 갈림길마다 어느 쪽을 먼저 둘지 골라야 하고, 그 순간 이어진 관계 일부가 사라집니다. 비선형 구조는 트리와 그래프 둘이고, 위아래가 있는지로 갈립니다.

트리는 트리에서, 그래프는 그래프와 탐색에서 자세히 봅니다.

예제

장면마다 맞는 구조 고르기

다음 다섯 장면에 맞는 자료구조를 먼저 골라 본 뒤 아래 표를 보세요.

• (가) 웹 브라우저에서 '뒤로'를 누르면 가장 최근에 본 쪽부터 거꾸로 돌아갑니다.
• (나) 프린터가 먼저 받은 문서부터 차례로 인쇄합니다.
• (다) 컴퓨터의 폴더 안에 폴더가 여럿 있고, 폴더마다 바로 위 폴더는 하나입니다.
• (라) 항공편이 도시마다 여러 도시로 이어지고, 떠난 도시로 돌아오는 노선도 있습니다.
• (마) 학번 1번부터 30번까지 성적을 차례로 담아 두고, 17번 성적을 곧바로 꺼냅니다.

갈래를 가를 때는 자료가 몇 개인지가 아니라 '한 자료 다음에 몇 개가 이어지나'를 봅니다. (나)의 문서도 (다)의 폴더도 여럿이지만, 문서 하나 다음은 문서 하나이고 폴더 하나 아래는 폴더 여럿입니다.

시험 포인트

• 필기: 자료구조는 선형 구조(배열·연결 리스트·스택·큐·데크)와 비선형 구조(트리·그래프)로 나뉩니다. 가르는 기준은 한 자료 뒤에 이어지는 자료가 하나인가 여럿인가입니다. '선형 구조가 아닌 것'을 고르는 꼴로 자주 나오고, 이름이 낯선 데크를 비선형으로 착각하게 하는 보기가 함정입니다. 데크는 양 끝에서 넣고 빼는 한 줄이라 선형입니다.
• 실기: 갈래 이름은 선형 구조(Linear Structure)·비선형 구조(Non-Linear Structure)로 씁니다. 보기의 구조 이름을 두 갈래로 나누어 쓰는 꼴로도 나옵니다.

확인 문제

1. 다음 가운데 비선형 구조로 담아야 하는 자료를 고르세요.

• ① 은행 창구의 대기 번호
• ② 문서 편집기의 '실행 취소' 기록
• ③ 운동 대회의 토너먼트 대진표
• ④ 갈림길이 없는 버스 노선의 정류장 차례

2. 다음 (가)·(나)에 맞는 갈래 이름을 한글 이름과 영문으로 함께 쓰세요. 답을 끝까지 쓴 뒤 정답을 펼치세요.

• (가) 어느 자료에서 출발해도 갈림길을 만나지 않고, 처음부터 끝까지 한 번에 차례대로 읽힙니다.
• (나) 어떤 자료에서는 길이 세 갈래로 나뉩니다. 세 갈래를 한 줄에 이어 붙이면 어느 셋이 같은 자료에서 갈라졌는지 알 수 없게 됩니다.

3. 다음 (가)~(바)를 선형 구조와 비선형 구조로 나누고, 장면마다 맞는 구조 이름을 쓰세요. 답을 끝까지 쓴 뒤 정답을 펼치세요.

• (가) 콜센터가 걸려 온 전화를 들어온 차례대로 상담원에게 넘깁니다.
• (나) 친구 관계 — 내 친구 둘이 서로 친구일 수도 있습니다.
• (다) 계산기가 괄호 짝을 맞출 때 가장 나중에 연 괄호부터 닫습니다.
• (라) 책의 목차 — 장 아래에 절이 여럿, 절 아래에 항이 여럿 있습니다.
• (마) 열차의 앞쪽에도 뒤쪽에도 칸을 붙이고 떼어 냅니다.
• (바) 재생 목록 가운데에 노래 한 곡을 끼워 넣어도 다른 곡들은 자리를 옮기지 않습니다.