자료 구조
💡 자료 구조의 분류
💡 선형 리스트 특징
💡 스택 개념, 오버플로, 언더플로
💡 큐 특징
💡 그래프 최대 간선 수
¹ 자료 구조의 정의
- 자료 구조는 자료의 표현과 그것과 관련된 연산
- 일련의 자료들을 조직하고 구조화하는 것
- 어떠한 자료 구조에서도 필요한 모든 연산들을 처리할 수 있음
- 자료 구조에 따라 프로그램 실행시간이 달라짐
² 자료 구조의 분류
선형구조
- 배열
- 선형 리스트
- 연속리스트
- 연결리스트
- 스택
- 큐
- 덱
비선형 구조
- 트리
- 그래프
³ 배열
동일한 자료형의 데이터들이 같은 크기로 나열되어 순서를 갖고 있는 집합
- 정적인 자료구조
- 기억장소의 추가가 어려움
- 데이터 삭제시 삭제된 공간이 빈 공간으로 남아있어 메모리 낭비 발생
- 첨자(index)를 이용하여 데이터 접근
- 반복적인 데이터 처리 작업에 적합
- 데이터마다 동일한 이름의 변수를 사용하여 처리 간편
- n차원 배열
⁴ 선형 리스트
일정한 순서에 의해 나열된 자료 구조
빈공간 없이 차례 차례 데이터가 저장됨
연속 리스트(Contiguous List)
- 배열과 같이 연속되는 기억장소에 저장되는 자료구조
- 기억장소를 연속적으로 배정받기 때문에 기억장소 이용 효율은 밀도가 1로 가장 좋음(빈공간 없이 꽉 차게 사용)
- 중간에 데이터를 삽입하기 위해서는 연속된 빈 공간이 있어야함
- 삽입, 삭제 시 자료의 이동이 필요 -> 불편
연결 리스트(Linked List)
- 반드시 연속적으로 배열시키지는 않고 임의의 기억공간에 기억시킴
- 자료 항목의 순서에 따라 노드의 포인터 부분을 이용하여 서로 연결 시킨 것
- 노드의 삽입/삭제 작업이 용이함
- 기억 공간이 연속적이지 않아도 됨
- 포인터 부분이 필요하기 때문에 순차 리스트에 비해 공간 효율이 좋지 않음
- 연결을 위한 포인터를 찾는 시간이 필요하기 때문에 접근 속도가 느림
- 중간 노드 연결이 끊어지면 그 다음 노드를 찾기 힘듦
⁵ 스택 ⭐️
리스트의 한쪽 끝으로만 자료의 삽입, 삭제 작업이 이루어지는 자료구조
- 후입선출(LIFO) 방식
- 응용 분야: 함수 호출 순서 제어, 인터럽트 처리, 수식 계산 및 수식 표기법, 컴파일러를 이용한 언어 번역, 복귀 주소 저장
- 오버플로우, 언더플로우 발생
⁶ 큐
한쪽에서는 삽입, 다른 한쪽에서는 삭제 작업이 이루어지는 자료구조
- 선입선출(FIFO) 방식
- 시작과 끝을 표시하는 두 개의 포인터가 있음
- front, rear 포인터
- 운영체제의 작업 스케줄링에 사용
⁷ 그래프
정점(vertex)와 간선(Edge)의 두 집합으로 이루어짐
- 간선의 방향성 유무에 따라 방향그래프, 무방향 그래프로 나뉨
- 통신망, 교통망, 이항관계, 연립방정식, 유기화학 구조식 등
- 트리는 사이클이 없는 그래프
방향/무방향 그래프의 최대 간선 수
N개의 정점으로 구성된 무방향 그래프: N(N-1)/2
N개의 정점으로 구성된 방향 그래프: N(N-1)
왕왕