[C++] STL - List

vector랑 양대산맥중 하나. vector와 list는 매우 유사해서 list를 자주 사용하기보다는 다른 자료구조를 이해하는 발판으로써 포스팅을 한다.

List 동작 원리

vector는 동적 배열로 이루어진 컨테이너였다. 연속적인 메모리를 할당받아 증설하는 형식이었다.

list는 이중 연결리스트이다. 즉, 데이터가 저장된 메모리가 연속적인 메모리가 아니라는 것이다. 다음 노드가 어디에 있는지를 각자 저장한 형태이다.

노드의 포인터로 서로를 가리키고 있는 것이다. 

vector에서 데이터를 중간에 추가하고자 하면 데이터가 연속적으로 존재해야하기 때문에 결국 값을 전부 복사해야한다.

하지만 list의 경우 중간에 낄 노드 양 옆에 포인터를 조작하면 바로 가능하다. 이는 데이터가 연속적으로 존재하지 않기 때문에 얻는 이점인 것이다.

 

중간 삽입 / 삭제

위에서 동작원리를 보듯이 중간에 데이터를 삽입하거나 삭제, 처음이나 끝 역시 매우 좋은 알고리즘으로 할 수 있다. 즉 걸리는 시간 자체가 vector랑 다르게 훨씬 빠르다.

다만 임의 접근 (i번째 데이터는 어디 있습니까?) 는 연속적으로 데이터가 존재하지 않기 때문에 처음부터 쭉 찾아야한다. 그렇기 때문에 자체적인 함수로 지원하지 않는다.

 

자 근데 의문이 들 수 있다. 

임의 접근은 안되는데 중간 삽입 삭제가 빠르다???? 말이 모순되는 것 같다.

50번 인덱스에 있는 데이터를 삭제한다고 해보자.

list<int> li;
	
list<int>::iterator it = li.begin();

li.erase(it + 50);

다음과 같이 코딩하면 동작하지 않는다. list에서 + 연산자 오버로딩이 되어있지 않기 때문이다. 그러면 다음과 같이 해야할 것이다.

list<int> li;

list<int>::iterator it = li.begin();

for (int i = 0; i < 50; i++)
{
    ++it;
}
li.erase(it);

그런데 결국 for문을 도는게 임의 접근을 의미한다. 

한마디로 임의 접근은 느린게 맞지만 erase는 빠르다 라는 사실이다.

그렇기 때문에 중간 삽입 삭제가 빠르다고 하는건 어떤 데이터를 찾아서 삭제나 삽입하는게 빠른걸 의미하는것이 아니다. 삭제할 데이터를 미리 알고 있을 때 빠르다고 하는 것이다.