자료구조란?

개념

자료구조란 데이터의 집합을 이야기한다.

각 데이터 간의 관계가 일정한 규칙에 의거하여 나열되고 자료를 처리하기 위해 체계적으로 구분하여 표현한 것이다.

 

 

자료 구조를 알아야하는 이유

- 데이터를 체계적이고 효율적으로 사용하기 위함

- 특정한 상황의 문제를 처리하는데 특화

 

 

 

기본적인 자료구조 7개

- Array

- Stack

- Queue

- Linked list

- Hash Table, Hash map

- Graph

- Tree

이미지 출처 : https://velog.io/@neity16/%EC%9E%90%EB%A3%8C-%EA%B5%AC%EC%A1%B0Data-Structure

 

자료구조마다 시간 복잡도가 존재하며 효율적인 문제 해결을 위해서는 상황에 맞는 자료구조를 선택할 수 있는 능력이 필요하다.

각 자료 별로 특징을 이해한다면 문제해결 능력은 한층 좋아질 것이다.

 

 

 

Array (배열)

Array는 기본적인 데이터 구조이다. Array는 생성 시 크기를 선언하며 크기에 맞게 셀이 생성이 된다.

각 셀은 index가 순차적으로 부여되며 index는 0부터 시작된다.

배열을 사용할 때는 index로 위치한 셀에 접근하여 데이터를 수정 및 삭제할 수 있다.

 

특징

- 다른 자료구조의 기초이다.

- 정렬이 쉽다.

- 사용이 간편하고 빠르다.

 

- 데이터 저장공간을 초기에 선언하기에 확장이 불가능하다.

- 데이터 삽입, 삭제의 효율이 좋지 않다.

 

 

시간 복잡도

get	create	delete
O(n)	O(n)	O(n)

 

Array Data 형태

 

 

 

Stack (스택)

Stack은 데이터의 순서가 보장이 되는 자료구조이다.

Last In First Out (LIFO) 매커니즘을 가지고 있어 마지막에 들어온 데이터가 제일 먼저 나가는 선입후출 구조이다.

 

특징

- 데이터의 크기가 동적이다.

- 빠르다.

- 데이터가 들어온 순서대로 정렬된다.

 

- 가장 최근의 데이터만을 가져온다.

- 데이터를 하나씩만 처리할 수 있다.

 

시간 복잡도

get	create	delete
O(n)	O(1)	O(1)

 

 

 

 

 

Queue (큐)

Queu는 Stack과 비슷한 자료구조이다.

Stack과는 다르게 First In First Out (FIFO) 매커니즘으로 선입선출 구조이다.

 

특징

- 데이터의 크기가 동적이다.

- 빠르다.

- 데이터가 들어온 순서대로 정렬된다.

 

- 가장 오래된 데이터만을 가져온다.

- 데이터를 하나씩만 처리할 수 있다.

 

- web에서 사용되는 캐시가 Queue와 같은 구조로 되어 있다.

 

 

시간 복잡도

get	create	delete
O(n)	O(1)	O(1)

 

 

 

 

 

Linked list (링크드 리스트)

Linked list는 메모리에 데이터를 물리적으로 배치하는 것이 아닌 참조시스템을 이용한 자료구조이다.

각 요소는 노드라고 하는 것에 저장이 되며 다음 위치에 있는 노드의 포인터나 주소 값을 가지고 데이터를 저장하게 된다.

 

특징

- 새로운 값을 저장과 기존 값의 삭제가 쉽고 효율적이다.

- 배열과 달리 메모리에 연속해서 저장되지 않는다.

- 메모리의 크기가 동적이다.

- 메모리를 효율적으로 사용할 수 있어 대용량 데이터를 처리하기에 적합하다.

 

- Array보다 많은 메모리를 사용한다.

- 1번 데이터부터 마지막 n번의 데이터를 순회하기에 데이터를 get 하는게 비효율적이다.

 

시간 복잡도

get	create	delete
O(n)	O(1)	O(1)

 

 

 

 

 

 

Hash table / Hash map (해시테이블)

Hash table은 대량의 데이터를 저장하고 검색을 효율적으로 할 수 있는 자료구조이다.

Hash table은 데이터를 저장할 때 Bucket에 key/value 형태로 데이터를 저장한다.

메모리 공간을 효율적으로 사용하기 위해 key를 해시함수를 통해 hsah라는 특정 숫자로 변환하여 데이터를 저장한다.

Hash table은 사용하는 데이터의 양만큼 메모리 사용량을 동적으로 변화시킨다. 

 

key는 검색에 사용되는 특정 값이며 value는 저장한 데이터의 값이다.

 

 

 

특징

- 데이터 생성, 삭제, 검색이 쉽고 빠르다.

- 동적으로 메모리가 할당된다.

 

- 중복된 키 값으로 저장하게 될 경우 충돌이 발생할 수 있다.

 

시간 복잡도

get	create	delete
O(1)	O(1)	O(1)

 

 

 

 

 

 

Graph (그래프)

Graph는 노드 사이에 엣지가 있는 자료구조이다.

그래프는 단방향(directed)과 양방향(undirected)가 기본이며 외에 다양한 그래프가 있다.

 

그래프의 구조는 설계에 따라 시간 복잡도가 달라진다.

 

 

특징

- 데이터 생성, 삭제가 쉽고 빠르다.

- 구조 응용이 다양하게 가능하다.

 

- 충돌이 발생할 수도 있다.

시간 복잡도

get	노드 엣지 create	노드 delete	엣지 delete
O(|N| + |E|)	O(1)	O(|N| + |E|)	O(|E|)

 

 

 

 

 

 

Tree (트리)

트리는 노드가 계층적으로 이루어진 구조이다.

최상위 노드로 부터 하위 노드가 추가되며 하위 노드에 또 하위 노드가 추가되는 방식이다.

 

트리의 종류는 굉장히 다양하며 트리 구조와 관련하여 알아야 하는 개념들이 있다.

 

개념

- 각 트리를 구성하는 값들을 노드라고 한다.

- 아래 그림과 같이 트리의 최상위 노드를 root라고 한다.

- root를 기준으로 다른 노드로의 접근 거리를 depth라고 한다.

- 동일한 부모 노드를 가지고 같은 depth에 존재하는 노드들은 sibling 관계에 있다.

- 노드와 노드를 연결하는 선을 edge라고 한다.

- 하위 노드가 없는 노드는 leaf라고 한다.

 

 

 

 

 

 

참고 게시글 : 

[Data structure] 개발자라면 꼭 알아야 할 7가지 자료구조

[CS 정리] 자료 구조(Data Structure)