자료 구조

1. 자료 구조

자료를 기억장치 공간 내에 저장하는 방법과 자료 간의 관계, 처리 방법 등을 연구 분석하는 것

 

* 자료 구조의 분류

출처 : https://www.geeksforgeeks.org/what-is-data-structure-types-classifications-and-applications/

 

2. 배열(Array)

(1) 크기와 형이 동일한 자료들이 순서대로 나열된 자료의 집합

(2) 반복적인 데이터 처리 작업에 적합한 구조

(3) 정적인 자료 구조, 기억장소의 추가가 어려움

(4) 데이터 삭제 시 기억장소가 빈 공간으로 남아 있어 메모리 낭비 발생

 

3. 연속 리스트(Contiguous List)

(1) 연속되는 기억장소에 저장되는 자료 구조

(2) 중간에 데이터 삽입을 위해서는 연속된 빈 공간이 있어야 함

(3) 삽입, 삭제 시 자료 이동이 필요

 

4. 연결 리스트(Linked List)

(1) 자료들을 임의의 기억공간에 기억시키되 노드의 포인터 부분을 이용하여 서로 연결시킨 자료구조

(2) 기억 공간 이용 효율이 좋지 않다

(3) 접근 속도가 느리고, 연결이 끈헝지면 다음 노드를 찾기 어려움

 

5. 스택(Stack)

(1) 리스트 한쪽 끝으로만 자료의 삽입, 삭제 작업이 이루어지는 자료 구조

(2) 후입선출(Last In First Out)

(3) 저장 공간이 없는 상태에서 데이터가 삽입되면 오버플로우(Overflow) 발생

(4) 삭제할 데이터가 없는 상태에서 데이터가 삭제되면 언더플로우(Underflow) 발생

 

 

6. 큐(Queue)

(1) 리스트 한쪽에서 삽입, 다른 한쪽에서 삭제 작업이 이루어지는 자료구조

(2) 선입선출(First In First Out)

(3) 시작을 표시하는 프런트(Front) 포인터와 끝을 표시하는 리어(Rear) 포인터가 있음

 

7. 그래프(Graph)

(1) 정점과 간선의 두 집합으로 이루어지는 자료 구조

(2) 사이클이 없는 그래프를 트리라고 함

(3) 간선의 방향성 유무에 따라 방향 그래프와 무방향 그래프로 구분

 

 

* 방향/무바향 그래프의 최대 간선 수

- 방향 그래프 : n(n-1)

- 무방향 그래프 : n(n-1)/2 

 

출처 :  정보처리기사 실기 2024 기본서 / 저자 : 길벗알앤디(김정준, 강윤석, 김용갑, 김우경)  / 출판사 : 길벗