탑싯_1_소프트웨어 개발_3_자료구조

종류

1. 데이터의 관계에 따라

선형 구조: 자료가 일렬로 연결되어 있는 형태다. 1:1 구조

 주의) 물리적 메모리가 연결된 것이 아니다

 ex) 리스트, 스택, 큐

비선형 구조: 한 자료 뒤에 여러 개의 자료들이 존재하는 구조로 1:다 또는 다:다 구조

ex) 트리, 그래프

 

2. 데이터 저장 방식에 따라

순차자료구조:

 메모리저장이 빈자리가 없이 순서대로 저장한다.

 물리적 주소 순서 = 논리적 순서

 삽입, 삭제를 하면 순서대로 저장해야 한다. 데이터가 이동되는 양이 많다 

연결자료구조:

 물리적인 순서가 불규칙적이다. 링크드 리스트 생각하면 편하다.

 물리적 주소 != 논리적 순서 

 삽입, 삭제를 하면 연결 링크 정보만 수정해주면 된다.

 

스택과 큐

스택

가장 나중에 쌓인 데이터가 가장 먼저 출력하게 되는 자료구조이다 (선입후출)

연산 종류: top(), push(), pop()

사용 예시, 인터럽트 처리, 재귀 프로그램의 순서 제어, 후위 표기법

큐

뒤(rear)에서만 삽입되고 앞(front)에서는 삭제만 할 수 있다(선입선출)

연산 종류: enQueue(), deQueue()\

사용 예시: 운영체제의 작업 스케쥴링, 비동기 데이터 교환, 대기 행렬 등 선입선출을 사용할 때

 

 

트리와 그래프

트리

원소들 간에 계층 관계를 가진다. 최상위 원소(루트 노드)로 부터 1대다 구조로 연결되어 있다.

사용 예시: 탐색, 정렬과 같은 구조, 문법의 파싱

그래프

원소들 간에 관계를 다대다 구조로 연결한다.

사용 예시: 이항 관계, 연립 방정식

 

자료 구조 선택 기준

1. 처리 시간

2. 자료의 크기

3. 활용 빈도

4. 갱신 빈도(update)