정의
- 데이터를 기억장치에 저장하는 것
- 자료의 구조화 및 처리 방법등을 연구분석 하는 것
- 자료 구조에 따라 프로그램 실행시간이 달라짐
분류
단순 구조
선형 구조
- 자료 간 관계가 1:1인 것
- 데이터가 일렬로 저장됨
순차 리스트 (배열 Array)
- 동일한 자료형이 같은 크기로 나열되어 있는 집합
- 크기가 정적이므로 새로운 배열 추가 불가
- 삭제 시 기억장소가 빈공간으로 남아있어 메모리 낭비 발생
연결 리스트 (선형 리스트 Linear List)
단순 연결 리스트
- 단방향
- 시작부분에 head 존재
- 노드에 값과 다음 노드를 가리키고 있는 주소값이 있음
이중 연결 리스트
- 양방향
- 시작부분에 head 존재
- 노드에 값과 이전/다음 노드를 가리키고 있는 주소값 두개 있음
- 단순 연결 리스트보다 메모리를 더 사용
단순-이중 연결 리스트 차이
- 두번째 데이터 B 삭제 시
- B 삭제 위해 B까지 탐색 후 삭제->B 이전 노드 A 탐색->A와 C 연결
- B 삭제 위해 B까지 탐색 후 삭제->B 이전 노드 A로 이동->A와 C 연결
원형 연결 리스트
- 단방향이지만 마지막 노드가 첫번째 노드를 가리킴
스택 (Stack)
- 한쪽 끝으로만 자료의 삽입, 삭제가 이루어지는 자료구조
- LIFO(후입선출)방식으로 자료 처리
큐 (Que)
- 한쪽에서는 삽입만, 다른쪽에서는 삭제만 이루어지는 자료구조
- 선입선출(FIFO)방식으로 자료 처리
- 시작과 끝을 표시하는 두개의 포인터 존재
덱 (Deque)
- 양방향 큐
- 앞과 뒤 양 방향에서 삽입/삭제 가능
비선형 구조
- 자료 간 관계가 1:n 혹은 n:m인 것
- 데이터가 트리 형태로 저장됨
그래프
- 정점과 간선의 집합으로 이루어진 자료구조
- 간선의 방향성 유무에 따라 방향그래프와 무방향그래프로 구분됨
- 루트, 노드, 부모-자식 개념이 존재하지 않음
트리
- 노드와 선분으로 이루어진 자료구조
- 사이클이 이루어지지 않음(순환하지 않음)
- 계층모델
파일 구조
순차파일
- 파일의 내용이 순서대로 나열되어 있어 순차적인 접근만 가능한 구조
- 순서대로 파일을 읽을 때 용이하나 검색효율이 낮음
색인파일
- 인덱스를 이용해 순차적으로 접근
- 인덱스를 위한 메모리 별도로 필요
직접파일