자료구조의 분류

프로그램에서 사용하는 자료를 기억장치내에 저장하는 방법, 저장된 그룹 내에 존재하는 자료들간의 관계, 자료를 처리하는 방법을 연구 분석하는 것을 의미한다.
자료구조에 따라 프로그램의 성능(실행 시간)이 달라질 수 있다.

선형 구조

stack

• 삽입과 삭제가 한 곳에서 이루어짐
• 후입선출(Last-In-First-Out:LIFO)방식
• 응용분야 - 인터럽트 처리, 서브 프로그램 분기, 수식계산에 사용

QUEUE

• 한 쪽 끝에서 입력, 다른 한 쪽 끝에서 출력이 이루어짐
• First-In-First-Out:FIFO
• 운영체제의 스케줄링기법, 일괄처리에 사용
• 입력 -> REAR 또는 TAIL, 출력 -> HEAD 또는 FRONT

DEQUEUE

• 양쪽으로 삽입과 삭제
• stack 과 QUEUE 의 복합체
• 입력제한 DEQUEUE-SCROLL, 출력제한 DEQUEUE - SHELF

ARRAY

• 동일한 자료형태를 갖는 데이터들이 같은 크기로 나열되어 순서를 갖는 집합
• 반복적인 데이터 처리 작업에 적한한 구조
• 정적인 자료구조 형태를 가지므로 도중에 기억장소의 추가가 어려움
• 데이터 삭제 시 데이터가 저장되어 있던 공간이 빈 공간으로 남아 메모리 낭비

연속(configuous) list

• ARRAY 구조처럼 연속되는 기억장소에 자료 저장되는 구조
• 기억장소를 연속적으로 배정받으므로 기억장소 이용밀도 가장 좋음(이용밀도1)
• 데이터 삽입 삭제 작업 시 자료 이동 필요

LINKED LIST

• 자료를 임의의 기억공간에 기억시키고 자료의 항목 순서에 따라 노드의 포인터 부분을 이용하여 자료를 연결시킨 형태
• 노드의 삽입, 삭제 작업 용이
• 연속적으로 기억 공간이 없어도 저장 가능
• 연결을 위한 포인터(링크)부분이 필요하기에 선형 리스트에 비해 기억공간 효율 안좋음.
• 접근 속도 느림

LINKED LIST 종류

linked list
다음 노드를 가리키는 링크 부분이 한 개만 사용

simply circular linked list
마지막 노드 링크 부분이 첫번째 노드를 가리킴

doubly linked list
이전 노드와 다음 노드를 가리키는 두 개의 링크 부분을 사용

doubly circular linked list
마지막 노드의 오른쪽 링크가 첫 번째 노드를 가리키고,
첫 번째 노드의 왼쪽 링크가 마지막 노드를 가리키는 구조