자료 구조의 정의
자료를 기억장치의 공간 내에 저장하는 방법과 저장된 그룹 내에 존재하는 자료 간의 관계, 처리 방법 등을 연구 분석하는 것
❗ 선형 구조와 비선형 구조 구분
배열(Array)
동일한 자료형의 데이터들이 같은 크기로 나열되어 순서를 갖고 있는 집합
- 정적인 자료 구조로 기억장소의 추가가 어려움
- 데이터 삭제 시 빈 공간으로 남게 되어 메모리의 낭비 발생
- 첨자 이용하여 데이터 접근
- 반복적인 데이터 처리 작업에 적합한 구조
- 데이터마다 동일한 이름의 변수 사용하여 처리 간편
- 첨자의 개수에 따라 n차원 배열이라고 부름
선형 리스트(Linear List)
일정한 순서에 의해 나열된 자료 구조
연속 리스트(Contiguous List)
- 배열 이용
- 배열과 같이 연속되는 기억장소에 저장
- 기억장소를 연속적으로 배정받아 기억장소 이용 효율은 밀도가 1로서 가장 좋음
- 중간에 데이터 삽입하려면 연속된 빈 공간이 있어야 함
- 삽입/삭제 시 자료 이동이 필요함
연결 리스트(Linked List)
- 포인터 이용
- 임의의 기억공간에 기억시키고 노드의 포인터부분을 이용하여 서로 연결시킨 자료 구조
- 노드의 삽입/삭제 작업 용이
- 기억 공간이 연속적으로 놓여 있지 않아도 저장 가능
- 포인터 부분이 필요하기 때문에 순차 리스트에 비해 기억 공간의 이용 효율이 좋지 않음
- 접근 속도가 느림
- 중간 노드 연결이 끊어지면 다음 노드 찾기 힘듦
스택(Stack)
리스트의 한쪽 끝으로만 자료의 압입, 삭제 작업이 이루어지는 자료 구조
- 후입선출(LIFO) 방식으로 자료 처리
- 꽉 채워져 있는 상태에서 삽입되면 오버플로(Overflow) 발생
- 삭제할 데이터가 없는 상태에서 삭제하면 언더플로(Underflow) 발생
큐(Queue)
한쪽에서는 삽입 작업, 한쪽에서는 삭제 작업이 이루어지도록 구성한 자료 구조
- 선입선출(FIFO) 방식으로 처리
- 시작과 끝을 표시하는 두 개의 포인터
- 운영체제의 작업 스케줄링에 사용
데크(Deque)
삽입과 삭제가 리스트의 양쪽 끝에서 모두 발생할 수 있는 자료 구조
- Double Ended Queue의 약자
트리(Tree)
사이클이 없는 그래프
그래프(Graph)
정점과 간선의 두 집합으로 이루어짐
❗ 간선 수 구하기(n개의 정점)
무방향 그래프 : n(n-1)/2
방향 그래프 : n(n-1)
노력형 인간