C++ 자료구조 정리

1. LIST

- 더블 링크드 리스트로 구현되어 있다.

- 더블 링크드 리스트의 장점을 그대로 가져오며 중간에 삽입/삭제가 빠르다.

- 하지만 특정 원소에 접근하려면 선형탐색을 해야한다. 상호 포인터 정보를 가지고 있기 때문에 메모리 사용비율이 높다.

2. Stack

3. Queue

4. Vector

- 배열인데, 동적으로 크기를 확장 또는 축소가 가능하게 되어있는 자료구조(크기조절 시 오버헤드 큼)

- 역시 배열의 특징을 그대로 가져온다. 데이터의 위치를 알고 있으면 랜덤 엑세스가 가능하다.

- 하지만 중간에 데이터를 삽입 또는 제거하려면 땡기거나 밀어야 되는 단점도 그대로 가지고 온다.

- 하지만 끝부분에 삽입할 땐 빠름

5. Deque(덱)

- LIFO, FIFO 두 가지 방식을 다 사용할 수 있는 스택큐 짬뽕.

- VECTOR는 끝부분에 삽입할 때만 빠르지만 덱은 앞뒤로 다 빠름. 하지만 중간에 삽입 삭제 시 벡터처럼 밀거나 땡겨야되는 단점을 가진다.

6. Set

- Map과 동일하나 Key 값만 이용한다. 완전 이진트리. 우리가 알고 있는 그 이진탐색트리랑 작동구조 똑같다.

- Key 값은 데이터를 뜻함.

- 이진탐색트리의 장점을 그대로 가지고 오므로, 정렬해야할때, 빨리 데이터를 찾아야 할때 좋다.

7. Multset

- Set과 동일하나 중복된 Key 값을 허용한다.

 

8. Map

- 완전이진트리. 구조로는 레드블랙트리를 사용한다. 키와 값을 이용한다. 정렬대상은 Key를 기준으로 오름차순으로 정렬한다.

- 선언방법 : map<key 자료형, value 자료형> 변수이름

9. Multimap

- Map과 동일하나 중복된 Key값을 허용한다.

 

10. Hashmap(표준아님)

- 해쉬테이블을 이용하여 Key에 해쉬함수를 적용시켜 테이블에 분산하여 저장. O(1)의 속도에 가깝다.

- 정렬할 필요가 없을경우 사용한다.(단일검색용)

- 만약 키가 같은 경우에는 링크드리스트의 형태로 자료가 이어져 붙어있고 만양 이런자료의 개수가 n이라면 O(n)의 선형시간 탐색이 나온다.

- Null을 허용하지 않는다.

 

11. Hashset

- Hashmap과 동일하나 Key값 하나만을 사용하고 중복을 허용하지 않는다.

- Null을 허용한다.

 

자료구조 정리가 한눈에 보기 좋게 정리되어 있다.

출처

https://enderbridge.tistory.com/160

https://blockdmask.tistory.com/