36. 자료 구조(A)

자료 구조의 분류

• 선형 구조 : 배열, 선형 리스트(연속 리스트, 연결 리스트), 스택, 큐, 데크
• 비선형 구조 : 트리, 그래프

 

배열

• 동일한 자료형의 데이터들이 같은 크기로 나열되어 순서를 갖고 있는 집합
• 첨자를 이용하여 데이터에 접근
• 반복적인 데이터 처리 작업에 적합한 구조
• 사용한 첨자의 개수에 따라 n차원 배열 

 

선형 리스트

• 일정한 순서에 의해 나열된 자료 구조
• 연속 리스트 : 배열, 연결 리스트 : 포인터
• 연속 리스트 : 기억 장소 효율 밀도 1, 데이터 삽입 시 연속된 빈 공간이 있어야 함, 삽입 삭제 시 자료의 이동이 필요하다
• 연결 리스트 : 순차 리스트에 비해 효율 좋지 않음, 접근 속도가 느림, 노드 삽입 삭제가 용이

 

스택

• 리스트의 한쪽 끝으로만 자료의 삽입, 삭제 
• 후입선출(LIFO)
• 함수 호출의 순서 제어, 인터럽트 처리, 수식 계산 및 수식 표기법, 컴파일러 언어 번역, 서브루틴 호출 및 복귀 주소 저장

 

큐

• 리스트의 한쪽에서는 삽입 작업이 이루어지고 다른 한쪽에서는 삭제 작업이 이루어지도록 구성한 자료 구조 
• 선입선출(FIFO)
• 운영체제의 작업 스케줄링에 사용

 

그래프

• 정점 V, 간선 E 집합으로 구성됨
• 방향 그래프(간선 수 : n(n-1)) , 무방향 그래프(간선 수 : n(n-1)/2)
• 트리는 사이클 없는 그래프