[일반] 자료구조 정리

array(배열) vs list(리스트)

배열 : 메모리상의 공간에 데이터가 연속적으로 모여있는 것
리스트 : 포인터를 이용하여 데이터가 서로 소시지처럼 연결되어 있는 것

배열의 장점
index를 이용한 검색이 쉽다.

배열의 단점
정해져있는 배열의 크기 + 삭제시 삭제된 공간 낭비 때문에 메모리 낭비가 발생한다.
빈공간을 허용하지 않을 시 N개의 데이터를 이동시켜야 하므로 삽입과 삭제가 어렵다.

리스트의 장점
메모리 낭비가 적다.
이미 삽입, 삭제를 수행할 node까지 이동한 경우 삽입, 삭제가 빠르다.

리스트의 단점
처음 node를 시작하여 포인터를 따라 검색해야 하므로 검색이 어렵다

이처럼 배열과 리스트는 각자의 단점과 장점을 상호 보완한다

하지만, 자동으로 메모리를 관리해주는 vector 배열이 등장하면서 배열의 장점은 그대로 가지고 있으면서 단점을 보안한 vector을 많이 사용한다.

map

key와 value가 쌍으로 존재하는 자료구조로 key의 중복을 허용 x

set

map처럼 쌍으로 존재하지 않고 중복을 허용하지 않는 자료구조 (집합과 비슷)

set의 가장 큰 장점은 검색이 빠르다는 것이다.

hash

hash : hash function과 hash table을 이용하여 데이터를 저장하는 자료구조

hash는 map vs set와는 다른 차원의 개념이다.

map에 hash를 적용하면 hashmap, set에 hash를 적용하면 hashset인 것이다.
hash function을 적용하는 데이터 구조가 map인지 set인지에 따라 구별되는 것이다.