std::list

insertion과 deletion이 O(1)의 시간복잡도를 가진다고 써보려하지만
std::list는 거의 쓰지않는다

#include <list>

int main(int argc, char const *argv[]) {
	std::list<int> nums{1,2,3,4,5};
    
    for (auto num : nums) {
    	std::cout << nums << " ";
    }
    std::cout << std::endl;
}

를 출력하면 1,2,3,4,5가 출력된다.

메모리를 살펴보면

스택의 list 객체는 힙에 저장되는 원소들의 첫번째와 마지막 포인터 및 총 원소 개수를 가지고있고
힙에는 각 원소들이 포인터로 이전 원소의 포인터와 다음 원소의 포인터를 나타낸다.

insertion은

포인터의 값만 바꾸면 되므로 O(1)이 소모된다.
하지만 find는 first 포인터부터 iterate를 진행하면서 값을 찾는 방식이므로
random access가 되지않아 O(n)이 소모된다.