초보자를 위한 STL list 정리

1)list란 무엇인가

1-1.list의 존재 이유

초보자를 위한 C++ STL forward_list 정리

앞서 설명한 forward_list는 아주 기본적인 형태로 구성된 단일 연결 리스트이기 때문에
리스트 끝에 원소 추가, 역방향 이동, 리스트 크기 반환 등의 기능은 제공하지 않습니다.
이는 메모리를 적게 쓰고 빠른 성능을 유지하기 위함입니다. 그러므로 forward_list는
빠른 원소 삽입이 필요한 모든 경우에 어울리는 컨테이너는 아닙니다.

이러한 단점을 해결하기 위해 c++는 list를 지원합니다. list는 이중 연결 리스트 구조이기
때문에 메모리를 조금 더 사용하는 대신 forward_list보다 더 많은 기능을 제공합니다.
아래 코드를 통해 이중 연결 리스트를 설명을 좀 더 하도록 하겠습니다.

 

1-2.단일 연결 리스트와 이중 연결 리스트의 차이

	struct singly_list_node { //단일 연결 리스트
		int data;
		singly_list_node* next;
	};	
    struct linked_list_node { //이중 연결 리스트
		int data;
		linked_list_node* next;
		linked_list_node* prev;
	};

위 코드에서 볼 수 있듯이 이중 연결 리스트는 이전 노드를 가리키는 포인터가 추가로 있습니다.
이 포인터를 이용하여 역방향으로 이동할 수 있으며, 맨 마지막 원소와 리스트 크기를 따로
저장하여 빠른 push_back()과 size() 함수를 지원합니다.

 

1-3.양방향 반복자

초보자를 위한 c++ STL 반복자(iterator) 정리

앞서 반복자에 대해 설명할 때, 배열 기반의 임의 접근 반복자와 forward_list 기반의
순방향 반복자의 유연성 차이를 알아봤습니다. list의 반복자는 이 두 반복자 중간 정도의
유연성을 가지고 있습니다.list의 반복자는 역방향으로 이동할 수 있기 때문에 forward_list보다
제약이 적습니다.

즉, list는 역방향으로의 연산이 필요한 경우에는 역방향 반복자를 사용할 수 있습니다.
하지만 list 반복자는 임의 접근 반복자보다는 유연하지 않기 때문에 list 반복자를 이용하여
어느 방향으로든 원하는 만큼 이동할 수 있지만, 임의 접근 반복자의 경우처럼 특정 위치로
한 번에 이동하는 것은 불가능합니다. 그러므로 list 반복자를 이용하여 특정 위치로 이동하는
작업은 선형 시간 복잡도를 가집니다. list의 반복자는 어느 방향으로 이동이 가능하기 때문에
양방향 반복자라고 부릅니다

---

2)list 원소 삽입과 삭제

	list<float> list1 = { 1,2,3 };

	//list의 삽입
	list1.push_front(0); // {0, 1, 2, 3}
	list1.push_back(4); // {0, 1, 2, 3, 4}
	list1.insert(next(list1.begin()), 0.5f); // {0, 0.5, 1, 2, 3, 4}
	list1.insert(list1.end(), 5); // {0, 0.5, 1, 2, 3, 4, 5}

	//list의 삭제
	list1.pop_front(); // {0.5, 1, 2, 3, 4, 5}
	list1.pop_back(); //  {0.5, 1, 2, 3, 4}

list는 forward_list의 원소 삽입과 삭제때 사용하는 push_front()와 insert_front()(insert로 대응)를

사용하여 원소를 삽입, 삭제를 할 수 있으며, 역방향 반복자가 포함된 양방향 반복자이기 때문에

push_back()과 pop_back() 사용을 하여 리스트 맨 뒤에 원소를 삽입하거나 삭제할 수 있습니다.

여기서 forward_list의 push_front()와 list의 push_front()와 또는 둘 다 사용할 수 있는 함수의

시간 복잡도는 같은지 궁금할 것입니다. 정답은 시간 복잡도는 서로 같습니다. 다만 실제로는

list에서 좀 더 많은 연산이 필요합니다. 왜냐하면 list는 각각의 노드에 두 개의 포인터를 가지고 있고

삽입 또는 삭제 연산 시 두 개의 포인터를 관리해야 하기 때문입니다. 그러므로 이중 연결 리스트에서

포인터를 관리하기 위해서는 단일 연결 리스트보다 대략 두 배의 연산을 수행합니다.

 

이중 연결 리스트에서 원소 삽입

원소 삽입은 위 이미지와 같이 forward_list와 같은 과정을 따르지만, prev, next 두 개의 포인터의 값을
적절하게 수정해야 하기 때문에 forward_list와 비교하면 두 배의 연산량이 필요합니다.
이와 같은 개념이 다른 기능에도 유사하게 적용이 됩니다.

---

3)list의 원소 접근

	list<int> list1 = { 1,2,3,4,5 };

	//cout << list1[1] << ' '; //에러 발생

	list<int>::iterator iter = list1.begin();
	advance(iter, 2);

	cout << *iter << endl;

list는 양방향 반복자이기 때문에 임의 접근 반복자처럼 배열처럼 접근하면 에러가 발생합니다.
따라서 iterator을 통해 원소를 접근하여 출력해야 합니다.

---

4)반복자 무효화

	vector<int> vec = { 1,2,3,4,5 };
	list<int> list1 = { 1,2,3,4,5 };

	vector<int>::iterator v_it4 = vec.begin() + 4; //v_it4는 vec[4] 원소를 가리킴
	vec.insert(vec.begin() + 2, 0); //v_it4 반복자는 무효
	
	list<int>::iterator l_it4 = next(list1.begin(), 4);
	list1.insert(next(list1.begin(), 2), 0); //l_it4 반복자는 여전히 유호

vector::insert() 함수에서 메모리 재할당 없이 원소를 삽입하는 경우라면, 원소 삽입 위치 이후에 있는
원소를 모두 이동해야 하므로 이 위치를 가리키는 반복자는 모두 무효화됩니다. 다만 벡터와 달리
연결 리스트에서는 삽입 또는 삭제 동작에서 원소를 이동할 필요가 없으므로 반복자가 무효화되지
않습니다. 다만 특정 원소를 삭제하는 경우, 삭제되는 원소를 가리키던 반복자는 당연히 무효화되지만
나머지 원소를 가리키는 반복자는 그래로 사용할 수 있습니다.

---

위 블로그의 내용은 코딩 테스트를 위한 자료 구조와 알고리즘 with C++를 참고하여 작성하였습니다.

https://product.kyobobook.co.kr/detail/S000001834528

코딩 테스트를 위한 자료 구조와 알고리즘 with C++ | 존 캐리 - 교보문고