[정보처리기사] 2-1. 자료구조

1. 자료구조의 분류

1-1) 선형 구조 (Linear Structure)

• 배열 (Array)
• 스택 (Stack)
• 큐 (Queue)
• 데크 (Deque)
• 선형 리스트 (Linear List) = 연속 리스트 (순차적임), 연결 리스트 (순차적이지 않음)

1-2) 바선형 구조 (Non-Linear Structure)

• 트리 (Tree)
• 그래프 (Graph)

2. 배열 (Array)

• 정적인 자료구조로 기억장소의 추가가 어렵고 메모리 낭비 발생
• 첨자를 이용
• 반복적인 데이터 처리작업에 적합
• 데이터마다 동일한 이름의 변수를 사용해 처리 간편

3. 스택 (Stack)

• 리스트의 한쪽 끝으로만 자료의 삽입, 삭제가 이루어짐
• 후입선출 (LIFO : Last In First Out)

4. 큐 (Queue)

• 리스트 한쪽에서는 삽입, 다른쪽에서는 삭제 작업이 이루어짐
• 선입선출 (FIFO : First In First Out)
• 시작(F, Front)과 끝(R, Rear)을 표시하는 두개이 포인터가 있음
• 운영체제 작업 스케줄링에 사용함

5. 데크 (Deque)

• 리스트의 양쪽 끝에서 삽입과 삭제 작업을 할 수 있는 자료구조

6. 선형 리스트 (Linear List)

▶ 연속 리스트 (Contiguous List)

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

▶ 연결 리스트 (Linked List)

• 자료들을 반드시 연속적으로 배열시키지 않고 임이의 기억공간을 기억시키되, 자료 항목의 순서에 따라 노드의 포인터 부분을 이용해 서로 연결시킨 구조
• 노드의 삽입, 삭제 작업이 용이
• 기억 공간이 연속적으로 놓여있지 않아도 저장 가능
• 연결을 위한 포인터가 필요하기 때문에 순차 리스트에 비해 기억 공간의 효율이 좋지 않음
• 연결을 위한 포이너를 찾는 시간이 필요하기 때문에 접근 속도가 느림
• 중간 노드 연결이 끊어지면 그 다음 노드를 찾기 힘듦

7. 트리 (Tree)

• 정점 (Node, 노드)와 선분 (Branch, 가지)을 이용해 사이클을 이루지 않도록 구성한 그래프의 특수한 형태
• 노드 (Node) : 트리의 기본 요소, 자료 항목과 다른 항목에 대한 가지를 합친 것
• 근 노드 (Root Node) : 트리의 맨 위에 있는 노드
• 디그리 (Degree, 차수) :각 노드에서 뻗어나온 가지의 수 
• 단말노드 (Terminal Node) : 자식이 하나도 없는 노드, Dgree =0 인 노드
• 자식노드 (Son Node) : 어떤 노드에 연결된 다음 레벨의 노드들
• 부모노드 (Parent Node) : 동일한 부모를 갖는 노드들
• 형제노드 (Brother Node, Sibling) : 동일한 부모를 갖는 노드들
• 트리의 디그리(차수) : 노드들의 디그리(차수) 중 가장 많은 수

8. 그래프 (Graph)

▶ 방향 그래프 

• 정점을 연결하는 선에 방향이 있는 그래프
• n개의 정점으로 구성된 방향 그래프의 최대 간선 수 = n(n-1)

▶ 무방향 그래프 

• 정점을 연결하는 선에 방향이 없는 그래프
• n개의 정점으로 구성된 무방향 그래프의 최대 간선수 = n(n-1)/2