[IT 개념 정리] 자료구조

1. 자료구조란?

사전적인 의미 - 자료의 집합으로 각 원소들이 논리적으로 정의된 규칙에 의해 나열되며 자료에 대한 처리를 효율적으로 수행할 수 있도록 자료를 구분하여 표현한 것.

목적 - 자료를 저장, 관리를 더 효율적으로 하기 위함으로 실행시간의 단축(시간복잡도)와 메모리 용량의 절약(공간복잡도)을 목적으로 자료구조를 선택한다.

즉, 컴퓨터에서 사용항 자료를 효율적으로 관리하고 구조화 하기 위한 작업이다.

2. 자료구조의 종류

자료구조는 자료의 구성에 따라 순차적으로 나열하는 선형구조, 비 순차적으로 나열하는 비선형구조로 나뉜다.

선형구조 - 선형리스트, 연결리스트, 스택, 큐, 데크

비선형구조 - 트리, 그래프

3. 선형구조

선형리스트 : 연속되는 기억장소에 저장되는 리스트 ≒ 배열(Array)
- 접근이 빠름, 삽입/삭제가 느림, 기억공간 효율이 좋음
연결리스트 : 노드의 포인터 부분을 연결 시킨 리스트
- 접근이 느림, 삽입/삭제가 빠름, 기억공간 효율이 좋지 않음
- 단순 연결 리스트, 이중 연결 리스트 등
- 가용 디스크 블럭, B-Tree 노드간 연결
스택 : 삽입/삭제가 한 방향으로 이뤄지는 자료구조
- FILO(First In Last Out) 선입 후출 : 먼저 들어온 자료는 가장 나중에 처리된다.
- 함수 호출 스택, , 프로그램 호출 복귀주소 등
큐 : 한 방향에서는 삽입, 다른 방향에서는 삭제가 이뤄지는 자료구조
- FIFO(First In First Out) 선입 선출 : 먼저 들어온 자료가 가장 먼저 처리된다.
- 메시지 큐, 작업 스케쥴링, 대기 행렬 처리 등
데크 : 양방향에서 삽입/삭제가 모두 이뤄지는 자료구조
- 스택과 큐의 기능이 합쳐진 형태

4. 비선형 구조

트리 : 노드와 간선으로 이뤄져 사이클이 없는 자료구조 - 트리처럼 생겨서 이름도 트리
- 노드, Root, Degree(노드의 차수), leaf(단말 노드), level(노드의 깊이)
- 이진트리 : 자식노드를 최대 2개를 가지는 트리구조
  - 완전 이진트리 : 왼쪽 자식노드부터 채워져 마지막 레벨을 제외하고는 모든 자식노드가 채워져있는 트리
  - 포화 이진트리 : 모든 노드가 0 or 2개의 자식 노드를 가지며 모든 리프노드의 레벨이 같은 트리
  - 꼭정 이진트리 : 모든 노드가 0 or 2개의 자식 노드를 가진 트리, 포화 이진트리의 하위 종류
  - 편향 이진트리 : 모든 노드가 한 방향으로만 편향된 트리
- 힙 : 우선순위 큐를 위해 만들어진 자료구조 : 트리 형태 ※추후 포스팅
  - 최소 힙 : 부모 노드의 키 값이 자식 노드의 키 값보다 작거나 같은 완전 이진 트리
  - 최대 힙 : 부모 노드의 키 값이 자식 노드의 키 값보다 크거나 같은 완전 이진 트리
그래프 : 노드와 간선으로 이뤄지며 사이클이 있는 자료구조
- 꼭지점(Vertex), 변(Edge)
- 변의 방향 유무에 따른 무향, 유향 그래프로 나눠짐
그래프와 트리의 차이

자료구조에 대해서 찾아보면 다양한 종류의 자료를 효율적으로 처리하기 위해 자연스럽게 알고리즘과 각 자료구조의 특징을 확인 하기 위한 시간 복잡도, 공간 복잡도에 대한 개념을 많이 볼 수 있을 것이다.

다음 포스팅은 자료 처리의 기본 삽입, 탐색 알고리즘과 시간 복잡도, 공간 복잡도 대해서 정리하려고 한다.

※ 참고 블로그

Han's 1ife