[2021 정보처리기사 필기] 자료구조의 분류

 

[정보처리기사 2과목 필기 예상 키워드] 목록으로 돌아가기
과목: 2. 소프트웨어 개발 챕터: 1장 데이터 입출력 구현 키워드: 자료구조의 분류	#자료구조의 분류 #선형리스트(Linear List) #연속리스트, 연결리스트 #노드(Pointer)

 

자료구조의 분류

효율적인 프로그램을 작성할 때 가장 우선적인 고려사항은 저장 공간의 효율성과 실행시간의 신속성이다.
자료구조는 프로그램에서 사용하기 위한 자료를 기억장치의 공간 내에 저장하는 방법과 저장된 그룹 내에
존재하는 자료 간의관계, 처리 방법 등을 연구 분석하는 것을 말한다.

 

① 자료 구조의 분류

 

 

② 선형 리스트(Linear List)의 형태 

* 연속리스트(Contiquous List)
- 배열(Array)과 같이 연속되는 기억장소에 저장되는 자료구조
- 밀도가 1로서(연속적) 가장 좋다
- 데이터 삽입을 위해서 연속된 빈 공간이 있어야 하며 삽입/삭제시 자료 이동 필요



* 연결리스트(Linked List)

위 그림 에서 "연결리스트, 노드(Pointer)" 부분을 보면, 요일은 순차적이지 않은 형태로 리스트에 배치되어있다.
처음 노드 가 시작되는 시작점인 "월요일"의 위치와 관계없이 월요일에 연결된 노드(2) 를 따라
2번째 칸의 화요일로 이동하고, 그 다음은 화요일이 가리키는 노드(6)을 따라 6번째 칸의 수요일로 이동되며
월->화->수->목->금->일(^) 까지 차례대로 이동할 수 있음을 알 수 있다.


- 배열X 임의의 기억공간에 기억, 순차적이지 않음
- 연결을 위한 링크(포인터) 부분이 필요하기 때문에 기억 공간 효율 안좋음
- 접근속도 느림



* 스택(Stack)
- 한쪽 끝으로만 자료 삽입/삭제
- 가장 나중에 삽입된 자료(TOP)가 가장 먼저 삭제되는(Last in First Out) 방식으로 자료 처리
- 데이터가 꽉 채워진 상태에서 삽입(Push)되면 오버플로우(Overflow) 발생
- 데이터가 다 비워진 상태에서 삭제(Pop)되면 언더플로우(Underflow) 발생



* 큐(Queue)
- 한쪽에서는 삽입, 다른 한쪽에서는 삭제
- 가장 먼저 삽입된 자료가 가장 먼저 삭제되는(First in First Out) 방식으로 자료 처리
- 가장 먼저 삽입된 자료(Front)과 가장 마지막에 삽입된 자료(Rear)를 가리키는 두 개의 포인터 존재
- 프론트 포인터는 삭제 작업시, 리어 포인터는 삽입 작업을 할 때 사용
- 운영체제의 작업 스케쥴링에 사용

 

 

 

 

 

[2021 정보처리기사 키워드 정리] 2. 소프트웨어 개발 (상시업데이트)

참고: 시나공 정보처리기사 필기 (저자: 강윤석, 김용갑, 김우경, 김정준 | 출판사: 길벗), 유튜브 주간컴공TV