[정보처리기사 실기] 내용 정리

자료 구조

• 자료 구조는 자료를 기억장치의 공간 내에 저장하는 방법과 자료 간의 관계, 처리 방법 등을 연구 분석하는 것을 말한다.
• 저장 공간의 효율성과 실행 시간의 단축을 위해 사용한다.

 

자료 구조의 분류

자료 구조의 분류

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

 

배열(Array)

• 배열은 크기와 형(Type)이 동일한 자료들이 순서대로 나열된 자료의 집합.
• 반복적인 데이터 처리 작업에 적합한 구조.
• 정적인 자료 구조. 기억장소의 추가가 어렵다. (기억장소라면?)
• 데이터 삭제 시 기억장소가 빈 공간으로 남아있어 메모리의 낭비가 발생.

연속 리스트(Contiguous List)

• 연속 리스트는 배열과 같이 연속되는 기억장소에 저장되는 자료 구조이다.
• 중간에 데이터를 삽입하기 위해서는 연속된 빈 공간이 있어야 한다.
• 삽입 & 삭제 시 자료의 이동이 필요하다.

연결 리스트(Linked List)

• 연결 리스트는 자료들을 임의의 기억공간에 기억시키되, 자료 항목의 순서에 따라 노드의 포인터 부분을 이용하여 서로 연결시킨 자료 구조이다.
• 연결을 위한 링크(포인터) 부분이 필요하기 때문에 기억 공간의 이용 효율이 좋지 않다.
• 접근 속도가 느리고, 연결이 끊어지면 다음 노드를 찾기 어렵다.

스택(Stack)

• 스택은 리스트의 한쪽 끝으로만 자료의 삽입, 삭제 작업이 이루어지는 자료 구조이다.
• 후입선출(LIFO : Last In First Out) 방식으로 자료를 처리한다.
• 저장할 기억 공간이 없는 상태에서 데이터가 삽입되면 오버플로(Overflow)가 발생한다.
• 삭제할 데이터가 없는 상태에서 데이터를 삭제하면 언더플로(Underflow)가 발생한다.
• 쇼미더머니5, 6엔 주노플로(Junoflow)가 나온다.

큐(Queue)

• 큐는 리스트의 한 쪽에서는 삽입 작업이 이루어지고 다른 한 쪽에서는 삭제 작업이 이루어지는 자료 구조이다.
• 선입선출(FIFO) 방식으로 자료를 처리한다.
• 시작을 표시하는 프런트(Front) 포인터와 끝을 표시하는 리어(Rear) 포인터가 있다.