결론은 std::list를 사용하면 안된다 ❗❗❗

reference를 참고해 보면은

std::list는 doubly-linked list라고 정의되어있다.

std::vector는 array이다.

시간 복잡도 비교

종류	serch	insertion	deletion
Linked list	O(n)	O(1)	O(1)
array	O(n)	O(n)	O(n)

이렇게 된다. 이것은 ref를 참고를 해보아도 부정할 수 없는 사실이다.

---

search가 지금 random access 를 말하는게 아니라

데이터를 찾는 부분을 말하는 것이기 때문에 array의 search가 O(n)이라는 것이다.

이렇게 6이라는 데이터를 찾기 위해서는 하나하나 다 검사를 해보아야한다.

array도 마찬가지로

6이라는 데이터를 찾기 위해서는 하나하나 밟아 나가는 과정이 필요하다.

---

insertion같은 경우에도 연결형 리스트의 경우 그냥 노드를 새로 만든다음 이전 노드와 다음 노드와 연결해주기만 하면되어서 O(1)를 가지로

array의 경우 O(n)를 가진다. 삽입할 경우 뒤에 데이터들이 하나씩 다 밀려가야하기 때문

deletion의 경우도 똑같다.

O(n)은 절대 O(1)를 이길 수 없다.

그러면 누가봐도 삽입 삭제가 많이 일어난다면은 std::list가 더 우월한데

왜 std::list를 사용하면 안되는가?

Search

그 이유는 "Cache" 때문이다.

array의 경우

첫번째 메모리에 access를 하게되면은

cache memory 때문에 뒤에 있는 데이터들이 cache mem크기 만큼 데이터들이 다 딸려온다.

그래서 1 clock밖에 필요하지 않다.

반면 std::list는 cache mem이 적용되지 않는다.
(이유는 당연히 Heap 메모리에 여기저기 흩어져있기 때문)

그래서 search의 경우에도 같은 O(n)처럼 보이지만 std::vector가 더 빠르다.

즉, 컴퓨터 구조상 array가 더 빠른 search performance를 제공을 한다.

Insertion/Deletion

그러면 삽입/삭제의 경우는 무조건 std::list가 좋지 않나? 라고 생각할 수 있는데

frequent insertion/deletion의 경우 좋아보일 수 있지만

(실제로 맞는 말이기는 하지만)

그런데 std::vector도 삽입/삭제 시 O(1)가지게 만들 수 있는 방법이 있다.

이렇게 넣어주면은 std::vector도 O(1)를 가진다.

=> ???

std::list는 5랑 7사이에 2라는 데이터를 넣었고

std::vector는 9뒤에 넣었는데 뭐가 같냐?

라고 생각하는게 당연하기는 한데

나중에 2라는 데이터를 찾기 위해서는

vector는 random access를 지원을 하고

list의 경우에는 2라는 데이터를 찾기 위해서 하나하나 돌려가면서 있는지 없는지 확인을 해야한다. -> O(n)

그래서 다르게 말하면은 2라는 데이터가 5와 7사이에 있다는 것이 중요한게 아니라

하나씩 다 찾으러 가야한다는 것이다.

7이 있는지 없는지를 찾기 위해서는 어쨋든 하나하나씩 다 돌아야한다.

즉 위치가 엄청나게 중요한 경우가 없다라는 것이다.

deletion의 경우

std::list는 O(1)를 가지고

std::vector는 O(n)를 가지지만 뒤에 2라는 데이터를 3의 자리에 move를 한다고 가정을 해보자.

O(1)을 가진다.

정리

std::list에서 iterator의 순서를 지키면서 삽입/삭제가 중요한 경우가 진짜 거의 없다.

아닌 경우가 훨씬 많다.

그래서 그냥 vector를 사용을 하면서

deletion이 일어날 경우 지우고 해당 자리에 가장 뒤에 있는 데이터를 move를 한다.

그래서 순서를 생각하지 않는 다면은 std::vector도 삽입/삭제 시 O(1)를 가진다는 것이다.

순서가 중요하지 않은 경우가 거의 99.9%이다.

그래서 Cache friendly한 data Container를 사용을 하는 것을 추천한다.