자료구조 개념 및 시간 복잡도 소개

 

※  자료구조란?

- 자료를 구조화해 둔 것(즉, 자료에 대한 효율적인 탐색, 삽입, 삭제 등이 가능하도록 만들어 둔 것)

(+ 자료가 많을 때 구조화를 해두지 않으면 다루기 힘들다.)

- 저장(삽입), 사용(삭제), 확인(탐색)의 의미를 가지고 있으며 어디에 초점을 두고 구조화할 것인지에 따라 종류가 다르다.

- 구조화를 해두면 저장할 때는 시간이 조금은 걸리더라도 원하는 자료를 사용하거나 확인할 때 빠르게 찾을 수 있다.

 

 

※ 추상자료형(ADT : Abstract Data Type)

- 추상화된(구체화되지 않은) 자료를 정의

- 자료에 대해 가능한 연산(삽입, 삭제, 탐색)에 대한 정의

- 자료의 표현 및 구현 방법에 대해서는 명시하지 않는다.

 

 

추상 자료형	표현하는 자료	구현 자료구조
리스트(list)	- 순서가 부여된 자료의 모음	- 배열(array) - 연결리스트(linked list)
스택(stack)	- 후입 선출(last-in first-out)방식의 자료모음 - 한 쪽 끝에서만 삽입과 삭제가 가능한 리스트
큐(queue)	- 선입 선출(first-in first-out)방식의 자료 모음 - 한 쪽 끝에서는 삽입, 다른 쪽 끝에서는 삭제가 가능한 리스트
데크(deque)	- 리스트의 양 끝에서 삽입과 삭제가 모두 가능한 리스트
집합(set)	- 중복이 없는 자료 모음	- 트리(tree) - 해쉬 테이블(hash table)
트리(tree)	- 계층적 관계를 갖는 자료 모음	- 트리(tree)
그래프(graph)	- 관계를 갖는 자료 모음	- 인접 행렬(adjacency matrix) - 인접 리스트(adjacency list)
사전(dictionary) & 맵(map)	- 키(key), 값(value)의 쌍으로 구성된 자료 모음	- 트리(tree) - 해쉬 테이블(hash table)
우선순위 큐(priority queue)	- 우선 순위에 따라 삭제가 발생하는 자료 모음	- 힙(heep)

 

 

 

※ 자료구조 시간 복잡도

 

연산	해쉬테이블		균형탐색트리
	평균	최악	평균	최악
탐색 / 삽입 / 삭제	O(1)	O(n)	O(log n)	O(log n)

 

연산	단방향연결리스트	양방향연결리스트	선형배열리스트	원형배열리스트
특정 위치 접근	O(n)	O(n)	O(1)	O(1)
첫 위치 삽입 / 삭제	O(1)	O(1)	O(n)	O(1)
끝 위치 삽입 / 삭제	O(1) / O(n)	O(1)	O(1)	O(1)
특정 값 자료 탐색	O(n)	O(n)	O(n)	O(n)