자료 구조 - 선형 리스트, 스택, 큐, 데크, 그리고 그래프

🎶 자료 구조에 대해 알아보자!

 

지난 포스트에서는 정렬 알고리즘에 대해 살펴보았다.

정렬(SORT) - 퀵 정렬, 힙 정렬, 합병 정렬, 기수 정렬

정렬(SORT) - 퀵 정렬, 힙 정렬, 합병 정렬, 기수 정렬

 

이번 포스트에서는 정보처리기사에서 다루는 자료 구조에 대해 살펴보도록 하겠다.

 

1. 선형 리스트(LINEAR LIST)

선형 리스트는 일정한 순서에 의해 나열된 자료구조로써, '배열'을 이용하는 연속 리스트와 '포인터'를 이용한 연결 리스트로 구분한다.

(a) 연속 리스트(Contiguous List)

• 연속 리스트는 배열과 같이 연속되는 기억장소에 저장되는 자료구조로, 기억장소를 연속적으로 배정받기 때문에 기억장소 이용 효율은 밀도가 1로서 가장 좋다.
• 연속 리스트는 중간에 데이터 삽입을 하기 위해 연속된 빈 공간이 있어야 하며, 삽입과 삭제 시 자료의 이동이 필요하다.

[그림 1] 연속 리스트

 

(b) 연결 리스트(Linked List)

• 연결 리스트는 자료들을 반드시 연속적으로 배열시키지 않고 임의의 기억공간에 기억시키되, 자료 항목 순서에 따라 노드의 포인터 부분을 활용해 서로 연결시킨 자료구조이다.
• 연결 리스트는 노드의 삽입과 삭제 작업이 용이하다.
• 순차 리스트에 비해 기억 공간의 이용 효율이 좋지 않고, 연결을 위한 포인터를 찾는 시간이 필요하기 때문에 순차 리스트에 비해 기억 공간의 이용 효율이 좋지 않다.

[그림 2] 연결 리스트

 

2. 스택(STACK)

• 스택은 리스트의 한쪽 끝으로만 자료의 삽입, 삭제 작업이 이루어지는 자료 구조로써, 나중에 삽입된 자료가 가장 먼저 삭제되는 후입선출 이하 LIFO(Last In First Out) 방식으로 자료를 처리한다.
• 응용 분야 : 함수 호출, 인터럽트 처리, 수식 계산
• 스택의 모든 기억 공간이 꽉 채워져 있는 상태에서 데이터가 삽입되면 '오버플로우(overflow)'가 발생하고, 더 이상 삭제할 데이터가 없는 상태에서 데이터를 삭제하면 '언더플로우(underflow)'가 발생한다.

[그림 3] 스택

 

3. 큐(QUEUE)

• 큐는 리스트의 한쪽에서는 삽입 작업이 이루어지고 다른 한쪽에서는 삭제 작업이 이루어지도록 구성한 자료구조로써, 가장 먼저 삽입된 자료가 가장 먼저 삭제되는 선입선출 이하 FIFO(First In First Out) 방식으로 자료를 처리한다.
• 큐는 시작과 끝을 표시하는 두 개의 포인터가 있다.

[그림 4] 큐

 

4. 데크(DEQUE)

• 데크는 삽입과 삭제가 리스트 양쪽 끝에서 모두 발생할 수 있는 자료구조로써, stack과 queue의 장점을 따서 구성한 것이다.
• 입력 제한 데크인 'Scroll' 과 출력 제한 데크인 'Shelf' 가 있다.

 

[그림 5] 데크

 

5. 그래프(GRAPH)

• 그래프는 정점 vertex와 간선 edge의 두 집합으로 이루어진 자료구조로써, 간선의 방향성 유무에 따라 방향 그래프와 무방향 그래프로 구분된다.
• 통신망, 교통망, 연립방정식 등에 응용된다.

[그림 6] 그래프

 

(🎃 n개의 정점으로 구성된 무방향 그래프에서 최대 간선 수는 n(n-1)/2 이고, 방향  그래프에서 최대 간선 수는 n(n-1) 이다!)