C++ 에서의 자료구조 list를 쓰는 이유

 

우선

forward_list가 기름기를 뺀 리스트라면

이건 건강한 음식인 list이다.

 

이 list는 이중 연결 리스트, doubly-linked list 구조로 되어 있다.

때문에 prev를 가리키는 포인터가 있기에 더 메모리를 먹는다는 점부터 알고 시작하자.

 

다시 말해서

데이터, 다음 노드를 가리키는 포인터, 이전 노드를 가리키는 포인터

3가지를 가지고 있다는 것이다.

 

forward_list와 list의 차이점은

list에서 _after로 끝나는 함수들이 이제는 after가 없어진다.

insert_after -> insert

emplace_after -> emplace

 

왜냐하면 원소 이동을 역방향으로도 가능하니까

원소 삽입이나 삭제를 위해 특정 원소의 이전 원소 반복자를 제공하지 않아도 되니까..?

 

즉, 해당 위치의 이전 원소의 iterator가 필요한 것이 아니라

정확한 해당 위치의 iterator가 필요해진 것이다.

 

이외에도 forward_list에서는 지원하지 않는

push_back(), emplace_back(), pop_back()을 지원한다.

 

---

[컴퓨터(Computer Science)/CS Interview] - C++ 에서의 자료구조 forward_list를 쓰는 이유

 

와 구현이 비슷하기 때문에

삽입, 삭제에 대해서 구현에 대한 설명은 없다.

 

다만 원소 삽입 시 그림으로 갈음하겠다.

 

---

또한 기타함수로는

remove, remove_if, sort, unique, reverse도 제공한다.

 

역시 iterator 종류가 다르기 때문에 구현되는 방식도 다름을 참고하자

[컴퓨터(Computer Science)/CS Interview] - C++에서 반복자, iterator의 차이

 

 

여기서는 forward iterator가 아닌 bidirectional iterator이다.

이 반복자도 어느 방향으로 이동은 가능하지만 임의의 위치에 한 번에 이동은 불가능하다.

때문에 선형 시간 복잡도 O(N)을 가진다.

 

---

 

List는 forward_list에서 조금 더 편의성을 추가한 연결리스트라고 보면 된다.

 

임의의 위치에서 삽입 삭제가 자유롭고

또한 it가 더 자유롭게 이동할 수 있다.

다만 forward_list보다 메모리는 더 먹는다 이전 원소를 가리키는 포인터를 가지고 있기 때문이다.