자료 구조
자료를 효율적으로 저장, 조직, 관리, 처리하기 위한 구조적 방법
- 데이터를 어떻게 저장하고, 어떻게 꺼내 쓸지를 정의하는 체계
- 자료를 기억장치 내에 저장하고, 자료 간의 관계를 표현하는 방법을 연구·분석하는 것
- 저장 공간의 효율성, 실행 시간의 단축, 데이터 접근의 용이성
- 데이터의 논리적 관계 구조에 따라 선형 구조와 비선형 구조로 구분
자료 구조의 분류
- 선형 구조(Linear Structure)
- 배열(Array)
- 선형 리스트(Linear List)
- 연속 리스트(Contiguous List)
- 연결 리스트(Linked List)
- 스택(Stack)
- 큐(Queue)
- 데크(Deque)
- 비선형 구조(Non-Linear Structure)
배열(Array)
- 동일한 타입의 데이터를 순서대로 저장한 집합
- 인데스로 접근 가능
- 데이터가 연속된 메모리 공간에 저장
- 정적 구조로 크기 변경 불가
- 인덱스 접근 속도 빠름
- 삽입·삭제가 비효율적
- 메모리 낭비 발생
연속 리스트(Contiguous List)
- 배열처럼 연속된 메모리 공간에 데이터 저장
- 삽입·삭제 시 데이터 이동 필요
- 중간 삽입 시 연속된 빈 공간 필요
- 구현이 단순, 접근이 빠름
- 삽입/삭제 시 오버헤드 큼
연결 리스트(Linked List)
- 각 데이터(노드)가 데이터 필드 + 포인터(링크)로 구성되어 연결된 구조
- 메모리의 어느 위치든 데이터 저장 가능
- 포인터를 통해 순서 유지
- 삽입·삭제가 용이
- 포인터 저장 공간 필요
- 접근 속도 느림
- 링크 끊기면 탐색 불가
스택(Stack)
- 데이터의 삽입과 삭제가 한쪽 끝에서만 일어나는 구조
- LIFO(Last In, First Out, 후입선출)
- 저장 공간이 꽉 찬 상태에서 삽입 시 오버플로 발생
- 삭제할 데이터가 없을 때 삭제 시도 시 언더플로 발생
큐(Queue)
- 한쪽(Rear)에서는 삽입, 반대쪽(Front)에서는 삭제하는 구조
- FIFO(First In, First Out, 선입선출)
- Front(삭제 위치), Rear(삽입 위치)
데크(Deque; Double-Ended Queue)
- 양쪽 끝에서 삽입과 삭제가 모두 가능한 자료 구조
- 양방향 큐
트리(Tree)
- 계층적 자료 구조
- 노드(Node)와 간선(Edge)으로 구성
- 루트에서 시작해 자식 노드로 확장
- 순환 없음
그래프(Graph)
- 정점(Vertex)과 간선(Edge)의 집합으로 구성된 자료 구조
- 비계층적 구조
- 순환 가능
- 방향성 여부에 따라 구분됨
- 종류
방향/무방향 그래프의 최대 간선 수
