002_리스트 (std::list)

리스트 (std::list)

list 는 노드 기반 컨테이너이며 이중 연결 리스트 구조를 가지고 있다. 데이터들이 메모리상에 붙어있지 않아 캐시 적중률(Cache Hit Rate) 이 낮지만 할당이 다소 쉽다.

Untitled

list 에 대한 일반적인 연산의 복잡도는 다음과 같다.

순차 접근 = O(N)
임의의 위치에서 원소의 삽입/삭제 = O(1)

<aside> 💡

장점

</aside>

동적으로 크기를 변경할 수 있다.
데이터 삽입/삭제 시 효율적이다. (해당 위치의 바로 앞, 뒤 노드의 연결고리만 바꾸면 됨)

<aside> 💡

단점

</aside>

임의 접근(Random Access)이 불가능하고 순차접근만 가능하다. (노드 기반 컨테이너) 따라서 원소 탐색 시 임의 접근 반복자 at(), [] 은 사용이 불가하고, 양방향 반복자 ++, -- 를 이용해서 탐색한다.

list 의 사용

list 헤더파일

#incldue <list>

list 선언

std::list<Type> ListName;

list 생성자 (편의상 int)

std::list<int> li;	비어있는 리스트 li를 생성
std::list<int> li(n);	기본값으로 초기화된 n 개의 원소를 갖는 리스트 li를 생성
std::list<int> li(n, m);	m으로 초기화된 n 개의 원소를 갖는 리스트 li를 생성
std::list<int> li2(li1);	리스트 li1를 복사하여 리스트 li2를 생성

list 의 멤버 함수

std::list<int> li;

li.push_front(n)	리스트 맨 앞에 원소 n 삽입
li.push_back(n)	리스트 맨 뒤에 원소 n 삽입
li.insert(iter, m)	iter가 가리키는 위치에 원소 m을 삽입한 후 해당 위치를 가리키는 `iterator` 를 반환
li.pop_front()	리스트 맨 앞의 원소 삭제
li.pop_back()	리스트 맨 뒤의 원소 삭제
li.erase(iter)	iter가 가리키는 원소를 삭제한 후 삭제된 원소의 다음 원소를 가리키는 `iterator` 를 반환
li.clear()	리스트의 모든 원소를 삭제 한다.
li.assign(n, m)	m의 값으로 초기화된 n 개의 원소를 할당
li.front()	맨 앞 원소의 참조를 반환
li.back()	맨 뒤 원소의 참조를 반환
li.begin()	맨 앞 원소를 가리키는 `iterator` 를 반환
li.end()	맨 마지막 원소의 다음을 가리키는 `iterator` 를 반환
li.rbegin()	맨 마지막 원소를 가리키는 `reverse_iterator` 를 반환
li.rend()	맨 앞 원소의 앞을 가리키는 `reverse_iterator` 를 반환
li.size()	리스트의 `size` (원소의 개수)를 반환
li.empty()	리스트가 비어있으면 `true` 를 반환
li.remove(m)	m 의 값과 같은 원소를 모두 제거
li.remove_if(predicate)	단항 조건자 `predicate` 에 해당하는 원소를 모두 제거함
li.reverse()	원소들의 순서를 뒤집음
li2.swap(li1)	리스트 li1 과 li2 를 서로 바꿈
li.sort()	모든 원소를 오름차순(기본값)으로 정렬. `sort()` 의 파라미터로
이항 조건자가 올 수 있으며, 그때는 그 기준으로 정렬.
li2.splice(iter2, li1)	리스트 li2 에서 iter2가 가리키는 곳에 리스트 li1의 모든 원소를 잘라 붙임
li2.splice(iter2, li1, iter1)	리스트 li2 의 iter2가 가리키는 곳에 리스트 li1의 iter1이 가리키는 원소를
잘라 붙임
li2.splice(iter2, li1, iter1_1, iter1_2)	리스트 li2 의 iter2가 가리키는 곳에 리스트 li1의 [liter1_1, iter1_2) 까지의
원소를 잘라 붙임
li.unique()	양 옆의 원소가 같으면 하나만 빼고 삭제함
li2.merge(li1)	리스트 li1을 리스트 li2 내부로 합병(잘라붙임) 및 오름차순(기본값) 정렬함. 두 번째 인자값으로 이항 조건자가 올 수 잇으며, 그때는 그 기준으로 정렬.

list 의 원소 삽입/삭제

list 의 원소 삽입/삭제 과정을 간략히 하면 다음과 같이 진행된다.

Untitled

위의 그림처럼 list 원소 삽입/삭제 시 해당 위치의 바로 앞, 뒤 노드의 연결 고리만 바꿔 주면 된다.

순차 접근 (Sequential Access)

list 는 앞, 뒤 원소의 주소값을 이용해 (노드 기반) 순서를 유지할 뿐 메모리 상으로는 연속적으로 저장되어 있지 않아 임의 접근 (Random Access) 이 불가능하며 list 의 원소를 탐색하기 위해서는 순차 접근 (Sequential Access) 를 이용해야 한다.

따라서 임의 접근 반복자 at[], [] 는 사용이 불가능 하고, 양방향 반복자 ++, -- 을 이용해 탐색한다.

#include <iostream>
#include <list>

int main()
{
	std::list<int> li = { 1, 2, 3, 4, 5 };
	std::list<int>::iterator it;

	std::cout << "li 리스트 : ";
	for (it = li.begin(); it != li.end(); ++it)
	{
		std::cout << (*it) << " ";
	}

	// 3번째 원소 탐색
	it = li.begin();
	++it;
	++it;

	std::cout << "\\nli의 3번째 원소 : " << (*it) << std::endl;
	//std::cout << "\\nli의 3번째 원소 : " << li[2] << std::endl; // 오류!

	return 0;
}

li 리스트 : 1 2 3 4 5
li의 3번째 원소 : 3

삽입/삭제 와 순차 접근

위에서 list 원소의 삽입/삭제는 빠르게 동작한다고 했다. 그러나 이는 삽입/삭제 과정 그 자체만 빠른 것을 의미한다.

만약 list 에서 n 번째 위치에 원소를 삽입/삭제 하고 싶다면 그 위치를 미리 저장해놓지 않은 이상 순차 접근을 통해 해당 위치에 가서 원소 삽입/삭제 과정을 진행해야 한다.

따라서 list 원소의 삽입/삭제 와 순차 접근은 따로 분리하여 생각해야한다.

#include <iostream>
#include <list>

int main()
{
	// 10000개의 원소를 가진 li 리스트
	std::list<int> li(10000, 1);
	std::list<int>::iterator it;

	// 5000번째 원소 제거
	// (1) 5000번째 위치를 저장한것이 아니라면 순차 접근
	it = li.begin();
	for (int i = 1; i < 5000; i++)
	{
		++it;
	}

	// (2) 순차 접근한 iterator를 통해 5000번째 원소 삭제
	li.erase(it);

	return 0;
}

list 사용 예시

`insert`

#include <iostream>
#include <list>

int main()
{
	std::list<int> li = { 1, 2, 4, 5 };
	std::list<int>::iterator it;

	std::cout << "li 리스트 : ";
	for (it = li.begin(); it != li.end(); ++it)
	{
		std::cout << (*it) << " ";
	}

	// 원소 삽입
	it = li.begin();
	++(++it);
	std::cout << "\\n\\n원소 삽입" << std::endl;

	// insert 는 삽입한 원소의 iterator를 반환
	std::list<int>::iterator insert_it = li.insert(it, 3);
	std::cout << "삽입한 원소 : " << (*insert_it);

	std::cout << "\\n\\nli 리스트 : ";
	for (it = li.begin(); it != li.end(); ++it)
	{
		std::cout << (*it) << " ";
	}

	return 0;
}

li 리스트 : 1 2 4 5

원소 삽입
삽입한 원소 : 3

li 리스트 : 1 2 3 4 5

`erase`

#include <iostream>
#include <list>

int main()
{
	std::list<int> li = { 1, 2, 3, 4, 5 };
	std::list<int>::iterator it;

	std::cout << "li 리스트 : ";
	for (it = li.begin(); it != li.end(); ++it)
	{
		std::cout << (*it) << " ";
	}

	// 원소 삭제
	it = li.begin();
	++(++it);
	std::cout << "\\n삭제할 원소 : " << (*it);
	
	// 삭제 후 다음을 가르키는 iterator 를 반환
	std::cout << "\\n\\n원소 삭제" << std::endl;
	std::list<int>::iterator erase_it = li.erase(it);

	std::cout << "삭제 후 (*iterator) : " << (*erase_it);

	std::cout << "\\n\\nli 리스트 : ";
	for (it = li.begin(); it != li.end(); ++it)
	{
		std::cout << (*it) << " ";
	}

	return 0;
}

li 리스트 : 1 2 3 4 5
삭제할 원소 : 3

원소 삭제
삭제 후 (*iterator) : 4

li 리스트 : 1 2 4 5

`remove`, `remove_if`

#include <iostream>
#include <list>

// 4 이상 6 이하의 원소일 때 true 반환
bool pred(int num)
{
	return num >= 4 && num <= 6;
}

int main()
{
	std::list<int> li;
	std::list<int>::iterator it;

	for (int i = 0; i < 10; i++)
	{
		li.push_back(i);
		li.push_back(i);
	}

	std::cout << "원본 리스트" << std::endl;
	for (it = li.begin(); it != li.end(); ++it)
	{
		std::cout << (*it) << " ";
	}

	// 원본 리스트 복사
	std::list<int> li1(li);
	std::list<int> li2(li);

	// 2의 값과 같은 원소 모두 제거
	li1.remove(2);

	std::cout << "\\n\\n원소 2 제거" << std::endl;
	for (it = li1.begin(); it != li1.end(); ++it)
	{
		std::cout << (*it) << " ";
	}

	// 4이상 6이하 원소 제거
	li2.remove_if(pred);

	std::cout << "\\n\\n4이상 6이하 원소 제거" << std::endl;
	for (it = li2.begin(); it != li2.end(); ++it)
	{
		std::cout << (*it) << " ";
	}

	return 0;
}

원본 리스트
0 0 1 1 2 2 3 3 4 4 5 5 6 6 7 7 8 8 9 9

원소 2 제거
0 0 1 1 3 3 4 4 5 5 6 6 7 7 8 8 9 9

4이상 6이하 원소 제거
0 0 1 1 2 2 3 3 7 7 8 8 9 9