list

list :

시퀀스 컨테이너이므로 원소의 저장 위치(순서)가 정해지며 노드 기반 컨테이너이므로 원소가 각각의 노드에 저장된다.

 

각 노드는 앞쪽, 뒤쪽 노드와 연결된 형태로 이중 연결 리스트이다.

 

list의 구조

 

컨테이너 앞쪽에 추가하는 push_front(), 제거하는 pop_front(), 뒤쪽에 추가하는 push_back(), 제거하는 pop_back()을 가진다.

 

첫 원소를 참조하는 front()와 마지막 원소를 참조하는 back()을 갖는다.

또 지정한 위치에 원소를 삽입하는 insert()와 제거하는 erase()를 갖는다.

 

노드 기반 컨테이너이므로 at()과 [] 연산자가 없으며 임의 접근 반복자가 아닌 양방향 반복자를  제공한다.

 

#include <iostream>
#include <list>

using namespace std;

int main()
{
	list<int> lt;

	lt.push_back(10);
	lt.push_back(20);
	lt.push_back(30);
	lt.push_back(40);
	lt.push_back(50);

	list<int>::iterator	iter;
	list<int>::iterator	iterEnd = lt.end();

	for (iter = lt.begin(); iter != iterEnd; ++iter)
		cout << *iter << ' ';
	cout << endl;

	lt.push_front(100);
	lt.push_front(200);

	for (iter = lt.begin(); iter != iterEnd; ++iter)
		cout << *iter << ' ';

	cout << endl;

	return 0;
}

출력 결과

가장 큰 특징 중 하나는 순차열 중간에 원소를 삽입(insert), 제거(erase)하더라도 상수시간 복잡도의 수행 성능을 보인다는 것이다.

 

배열 기반 컨테이너인 vector나 deque처럼 원소를 밀어내지 않고 노드를 서로 연결하기만 하면 되기 때문이다.

 

노드 기반 컨테이너의 삽입(insert)과 제거(erase) 동작은 반복자를 무효화시키지 않는다.

 

원소 자체가 제거되지 않는 한 반복자가 가리키는 원소는 그대로 존재한다.

 

하지만 배열 기반 컨테이너(vector, deque)의 반복자는 원소의 삽입과 제거 동작이 발생하면 메모리가 재할당되거나 원소가 이동할 수 있으므로 반복자가 무효화된다.

 

#include <iostream>
#include <list>

using namespace std;

int main()
{
	list<int> lt;

	lt.push_back(10);
	lt.push_back(20);
	lt.push_back(30);
	lt.push_back(40);
	lt.push_back(50);

	list<int>::iterator	iter = lt.begin();
	list<int>::iterator	iter2;
	++iter;
	++iter;

	iter2 = lt.erase(iter);

	for (iter = lt.begin(); iter != lt.end(); ++iter)
		cout << *iter << ' ';
	cout << endl;

	cout << "iter2 : " << *iter2 << endl;

	iter = iter2;
	iter2 = lt.insert(iter, 300);
	for (iter = lt.begin(); iter != lt.end(); ++iter)
		cout << *iter << ' ';
	cout << endl;

	cout << "iter2 : " << *iter2 << endl;

	return 0;
}

출력 결과

 

list와 vector에 각각 삽입해보자

#include <iostream>
#include <list>
#include <vector>

using namespace std;

int main()
{
	vector<int> v;
	list<int> lt;

	v.push_back(10);
	v.push_back(20);
	v.push_back(30);
	v.push_back(40);
	v.push_back(50);

	lt.push_back(10);
	lt.push_back(20);
	lt.push_back(30);
	lt.push_back(40);
	lt.push_back(50);

	vector<int>::iterator	viter = v.begin();
	++viter;
	list<int>::iterator	liter = lt.begin();
	++liter;

	viter = v.insert(viter, 600);
	liter = lt.insert(liter, 600);

	cout << "vector: " << *viter << endl;
	cout << "list: " << *liter << endl;

	cout << "vector: ";
	for (viter = v.begin(); viter != v.end(); ++viter)
		cout << *viter << ' ';
	cout << endl;

	cout << "list: ";
	for (liter = lt.begin(); liter != lt.end(); ++liter)
		cout << *liter << ' ';
	cout << endl;

	return 0;
}

출력 결과

둘의 결과는 같지만 내부 동작은 다르다.

 

v에 600을 삽입하면 다음 원소부터 모두 뒤로 밀려나며 할당된 메모리 공간이 부족하면 메모리 재할당이 발생한다.

하지만 lt는 원소(노드) 하나만을 삽입하므로 속도가 빠르며 반복자들이 무효화되지 않는다.

 

erase() 함수의 동작도 같은 특징을 보인다.