[자료구조] std::list

<본 카테고리는 "코딩 테스트를 위한 자료 구조와 알고리즘 with C++을 기반으로 작성하였습니다>

---

std::forward_list

개요

　앞선 자료구조 포스트의 std::forward_list는 아주 기본적인 형태로 구현된 연결리스트다. 따라서 리스트 끝에 원소를 추가하거나, 역방향으로 이동하는 기초 기능 외에는 지원하지 않는다. 따라서 C++에서는 이러한 단점을 보완하기 위해 양방향 연결 리스트(doubly-linked list) std::list를 제공한다. 이를 사용하기 위해선 <list> 헤더파일을 임포트 해야 한다.

---

구조

　연속된 자료 구조와 연결된 자료구조 (2) with C++에서 그림을 하나 가져와보자.

 

 

　보면 알겠지만, 노드끼리 서로 연결되어 있기 때문에 이전 노드를 가리키는 포인터, 다음 노드를 가리키는 포인터, 해당 노드에 있는 데이터를 갖고 있다. 간략하게 형태를 코드로 파악하자면 다음과 같다.

 

struct Node
{
	int _data;
	Node* _prev;
	Node* _next; 
};

---

특징

　std::list는 구조적으로 서로 연결되어 있기 때문에, 포인터를 이용하여 역방향으로 이동할 수 있다 (O(n)). 하지만 컨테이너가 연속되어 있지 않기 때문에 임의 접근([] 연산자를 이용한 접근, at() 함수를 이용한 접근 등)은 불가능하다는 단점과, std::forward_list에 비해 포인터가 하나 더 있기 때문에 메모리를 조금 더 사용한다는 단점이 있다. 예제를 하나 살펴보자. 

 

#include <iostream>
#include <list>

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

	for (int i = 0; i < 5; i++)
	{
		li.push_back(i); // 0 1 2 3 4 5
	}

	for (int i = 6; i < 10; i++)
	{
		li.push_front(i); // 9 8 7 6 0 1 2 3 4 5
	}

　다음과 같이 std::list<int> li를 {9, 8, 7, 6, 0, 1, 2, 3, 4, 5}의 원소를 갖는 리스트로 초기화하였다. 여기서 순방향/역방향으로 순회하는 코드를 짜면 다음과 같다.

 

	for (auto it = li.rbegin(); it != li.rend(); it++)
	{
		std::cout << *it << ' '; // 5 4 3 2 1 0 6 7 8 9
	}

	for (auto it = li.begin(); it != li.end(); it++)
	{
		std::cout << *it << ' '; // 9 8 7 6 0 1 2 3 4 5
	}

　하지만 벡터처럼 반복자에 + 연산자를 이용해 임의 접근하는 것은 불가능하다.

 

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

int main()
{
	std::list<int> li;
	std::vector<int> v;

	for (int i = 0; i <= 5; i++)
	{
		li.push_back(i); // 0 1 2 3 4 5
		v.push_back(i); // 0 1 2 3 4 5
	}

	auto liIt = li.begin() + 2; // 에러
	auto vIt = v.begin() + 2;
}

　또한, 반복자 무효화(Iterator invalidation)를 무시한다는 특징이 있다. 이때 반복자 무효화란 컨테이너가 변경되어 특정 노드 또는 원소의 메모리 주소가 바뀌어 사용하던 반복자가 무효화되는, 즉, 컨테이너의 변경 작업에 의해 반복자가 더 이상 유효하지 않은 상태가 되는 것을 말한다. 이 경우 예측할 수 없는 동작이 발생할 수 있다. 다음 예제를 보자.

 

#include <iostream>
#include <vector>

int main()
{
	std::vector<int> v;

	for (int i = 0; i <= 5; i++)
	{
		v.push_back(i); // 0 1 2 3 4 5
	}

	auto it = v.begin() + 4; // v[4] = 4
	v.insert(v.begin() + 2, 7); // Iteration Invalidation
}

　Iteratio it이 v[4]를 가리키고 있지만, 그다음 라인에서 insert() 함수를 통해 원소를 삽입하고 있다. vector의 insert() 함수의 경우, 함수를 수행할 때 메모리 재할당이 필요한 경우에 기존의 모든 반복자와 포인터, 참조를 무효화시킨다. 따라서 메모리를 재할당하는 과정 없이 원소를 삽입하는 경우라면, 원소 삽입 위치 이후에 있는 원소를 모두 이동해야 된다는 것이다. 

 

#include <iostream>
#include <list>

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

	for (int i = 0; i < 5; i++)
	{
		li.push_back(i); // 0 1 2 3 4 
	}

	auto it = next(li.begin(), 4);
	li.insert(next(li.begin(), 2), 0);
}

　하지만 벡터와 달리 std::list의 경우, 삽입 또는 삭제 동작에서 원소를 이동할 필요가 없으므로 반복자가 무효화되지 않는다. 위의 예제를 std::list에 적용해서 해보면 에러가 생기지 않는다는 것을 확인할 수 있다. 

---

요약

std::list
1. 정의: 전 노드를 가리키는 포인터, 다음 노드를 가리키는 포인터, 해당 노드에 있는 데이터를 갖고 있는 양방향 연결 리스트
2. 특징
　a. 포인터를 이용해 역방향/순방향 이동 가능
　b. 임의 접근 불가능
　c. 반복자 무효화 X