[STL] 자료구조 원리와 시간 복잡도

Stack

    특징 : FILO(First Input Last Output)형식의 자료구조입니다. C++에서는 vector으로, C#에서는 stack으로 구현이 되어있습니다. DFS방식의 탐색을 할때 사용될 수 있습니다.

 

    시간복잡도 : 검색 O(n), 삽입/삭제 O(n)

Queue

    특징 : FIFO(First Input First Output)형식의 자료구조입니다. C++와 C#에서는 Queue로 구현이 되어있습니다. BFS방식의 탐색을 할때 사용될 수 있습니다.

 

    시간복잡도 : 검색 O(n), 삽입/삭제 O(n)

List

    특징 : 한 노드가 자신의 앞의노드와 뒤의 노드의 주소값을 가지고 있는 형태의 자료구조입니다. C++에서는 List으로, C#에서는 stack으로 구현이 되어있습니다. DFS방식의 탐색을 할때 사용될 수 있습니다.

 

    시간복잡도 : 검색 O(n), 삽입/삭제 O(1)

Array

    특징 : 배열은 연속된 메모리공간에 존재하는 형태입니다. 

 

    시간복잡도 : 검색 O(1), 삽입/삭제 O(n)

 

Tree

    특징 : 트리형태는 트리 구조에 따라 최대 log(n)의 시간복잡도를 보장합니다. 일반 트리 같은 경우에는 노드가 편향적으로 삽입되는 경향이 있어서 시간복잡도가 보장되지 않지만, 레드-블랙 트리는 이부분을 보완해줍니다. 또한, 데이터가 정렬된 형태로 저장되는 특징이 있습니다.

 

    시간복잡도 : 검색 O(log(n)), 삽입/삭제 O(log(n))

 

HashTable

    특징 : HashTable은 Hash Function을 이용해서 인덱스 값을 구해 접근하는 자료구조입니다. 이때, 구해진 인덱스 값은 중복될 수 있기 때문에 같은 인덱스의 값들을 리스트로 저장해주거나 Hash Function을 한번 더 사용하여 빈 인덱스를 찾는 방법이 있습니다.

 

    시간복잡도 : 검색 O(N/H), 삽입/삭제 O(N/H)