자료구조(Data Structure)

자료구조(Data Structure)란?

자료 구조(Data Structure) 는 메모리를 효율적으로 사용하며 빠르고 안정적으로 데이터를 처리하는 것이 궁극적인 목표로 상황에 따라 유용하게 사용될 수 있도록 특정 구조를 이루고 있다.

자료구조는 '일차원인 컴퓨터 메모리를 현실에 대응되도록 구조를 만든 것'이라고 볼 수 있다.

자료구조는 크게 선형과 비선형으로 나눌 수 있고, 그 안에 해당되는 자료구조는 다음과 같다.

선형 구조

선형 구조 는 한 원소 뒤에 하나의 원소 만이 존재하는 형태로 자료들이 선형으로 나열되어 있는 구조를 가진다. 선형 구조에 해당되는 자료구조는 배열, 연결 리스트, 스택, 큐, 해시테이블 등이 있다.

Array

• 한 가지 데이터 타입의 데이터를 순차적으로 저장 및 정렬하는 자료구조다.
• 각 데이터마다 index를 부여하여 데이터 검색이 용이하다.

Linked List

• 각 요소를 포인터로 연결하여 관리하는 자료 구조다.
• 각 요소는 노드라고 부르며 데이터 영역과 포인터 영역으로 구성된다.

[예시]
데이터의 추가/삭제가 많은 학생정보리스트를 입력할 때 사용한다.

Stack

• 데이터를 일시적으로 저장하기 위해 사용하는 자료구조다.
• 데이터의 입출력은 후입선출(LIFO: Last In First Out) 방식을 사용하고, 한 쪽 끝에서만 자료를 넣고 빼는 작업이 이루어진다.

[예시]
웹 브라우저 뒤로가기

Queue

• 스택과 마찬가지로 데이터를 일시적으로 저장하기 위해 사용하는 자료구조다.
• Queue는 선입선출(FIFO: First In First Out) 방식으로 양쪽 끝에서 데이터의 삽입과 삭제가 각각 이루어진다.

[예시]
영화관에서 영화를 예매하기 위해 줄을 기다릴 때 사용한다.

Hash Table

• 키와 값을 받아 해싱(Hashing)하여 나온 index에 값을 저장하는 자료구조다.
• 데이터의 크기에 관계없이 삽입 및 검색에 매우 효율적이다.
• 해시 함수를 사용하여 색인(index)을 버킷(bucket)이나 슬롯(slot)의 배열로 계산한다.
• 기본적으로 선형 구조로 구현되지만, 충돌과 같은 문제를 해결하기 위해 비선형 구조로 구현되기도 한다.

[예시]
주소록 저장형태의 경우 이름-전화번호의 매칭을 이용하여 데이터를 처리한다.

비선형 구조

비선형 구조 는 원소 간 다대다 관계를 가지는 구조로 계층적 구조나 망형 구조를 표현하기 적절하다. 비선형 구조에 해당되는 자료구조는 그래프 와 트리, 힙 등이 있다.

Graph

• 정점과 정점 사이를 연결하는 간선으로 이루어진 비선형 자료구조다.
• 정점 집합과 간선 집합으로 표현할 수 있다.
• 정점은 여러 개의 간선을 가질 수 있다.
• 크게 방향 그래프와 무방향 그래프로 나눌 수 있다.
• 간선은 가중치를 가질 수 있다.
• 사이클이 발생할 수 있다.

[예시]
① 지하철 노선도
② 페이지 랭크 알고리즘

Tree

• 방향 그래프의 일종으로 정점을 가리키는 간선이 하나밖에 없는 구조다.
• 하나의 루트에서 하위로 뻗어나가는 구조로 이루어져있다.
• 루트 정점을 제외한 모든 정점은 반드시 하나의 부모 정점을 가진다.
• 정점이 N개인 트리는 반드시 N−1개의 간선을 가진다.
• 루트에서 특정 정점으로 가는 경로는 유일하다.

[예시]
① 조직도
② 디렉터리 구조

Heap

• 이진 트리 형태를 가지며 우선순위가 높은 요소가 먼저 나가기 위해 요소가 삽입, 삭제 될 때 바로 정렬되는 특징이 있다.
• 우선순위를 구현하기 가장 적합한 방법이다.
• 루트가 가장 큰 값이 되는 최대 힙(Max Heap) 과 루트가 가장 작은 값이 되는 최소 힙(Min Heap) 이 있다.
• 힙의 동작은 추가/삭제 요소가 핵심이다.