CPP STL LIST편

List(연결 리스트) 종류

1. 단일: 노드의 순서가 한 방향이다.
2. 이중: 노드의 순서가 양 방향이다.
3. 원형: 이중 + 첫 노드와 마지막 노드가 연결되어 있다.

이중노드를 기준으로 list의 동작 원리를 알아보자.

 

 

List

STL의 vector와는 달리 list는 노드 단위로 비연속적인 메모리 공간에 존재한다. vector 때 배운 내용을 생각해보면 동작 원리를 유추할 수 있다.

노드의 구조를 잠시 살펴보면,

template<typename T>
class Node
{
public:
	Node* _next;	// 다음 노드의 주소
	Node* _prev;	// 이전 노드의 주소
	T _data;
};

하나의 노드는 다음, 이전 노드의 주소와 데이터를 가지고 있다.

 

 

list의 중간 삽입/삭제, 처음/끝 삽입/삭제

노드가 가리키는 주소를 수정해주면 중간/처음/끝 삽입/삭제를 간단히 할 수 있다.

임의 접근

해당 기능을 제공하지 않는다.

비연속적인 메모리 공간을 가지고 있기 때문에 처음 노드부터 끝 노드까지 탐색하면서 접근해야 한다.

 

 

#include <list>

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

int first = li.front();
int last = li.back();

list는 vector와는 다르게 push_front() 기능을 지원한다. 삽입/삭제가 간단하기 때문이다. 

첫, 끝 데이터를 추출하는 기능도 제공한다.

 

int size = li.size();

vector와 같은 기능이지만, capacity() 기능은 제공하지 않는다. vector는 동적 배열이기 때문에 용량과 관련된 capacity가 필요했지만 list는 필요할 때마다 실시간으로 연결할 수 있기 때문에 필요 없는 기능이다.

 

 

List의 Iterator

vector의 iterator와 조금 다르게 동작한다.

list<int>::iterator itBegin = li.begin();
list<int>::iterator itEnd = li.end();

사용법은 vector와 같지만 뜯어보면 뭔가 다른 점이 있다.

우선 list의 첫 노드와 마지막 노드는 dummy node를 가리키고 있다. dummy node란 아무런 의미 없는 값을 가진 node인데, 개발자의 실수를 막는 용도로 존재한다고 한다.

list1: [dummy node]
list2: [1] <-> [2] <-> [3] <-> [4] <-> [5] <-> [dummy node] <->

 

첫 노드와 마지막 노드가 dummy node를 가리킨다고 해서 --itBegin, ++itEnd 연산을 사용해보면 에러가 발생할 것이다. dummy node는 쓰레기 값을 가졌기 때문에 메모리와 관련된 연산을 하면 안되기 때문이다. 또한 vector와는 다르게 itBegin + 10처럼 10칸 이동 기능을 지원하지 않는다. 임의 접근 기능을 제공하지 않기 때문이다.

 

for (list<int>::iterator it = li.begin(); it != li.end(); ++it)
{
	cout << *it << endl;
}

li.insert(itBegin, 100);
li.erase(li.begin());

li.pop_front();
li.remove(10);

vector와 비슷한 기능을 가진 것도 있지만, pop_front(), remove()처럼 차별된 기능을 제공한다.

특히 remove(data)는 특정 데이터를 삭제하는 기능인데, 삽입/삭제가 간단하기 때문에 지원하는 기능이다.

 

 

임의 접근이 안되는데 중간 삽입/삭제가 빠른 이유?

임의 접근이 안되기 때문에 특정 노드를 찾기 위해서는 처음 노드부터 마지막 노드까지 탐색할 필요가 있다. 그런데 왜 중간 삽입/삭제가 빠르다고 하는 걸까? 이는 면접 때 나올 수 있는 질문이다!!

 

먼저 10번 째 인덱스에 있는 데이터를 삭제하는 방법을 보자.

list<int>::iterator it = li.begin();
for (int i = 0; i < 10; i++)
	++it;
li.erase(it);

처음 노드에서 10번 째 노드까지 탐색한 뒤에 해당 노드를 삭제하는 것을 볼 수 있다. 위 과정을 보면 전혀 빠르지 않다.

 

list<int>::iterator itRemember;
for (int i = 0; i < 100; i++)
{
	if (i == 10)
		itRemember = li.insert(li.end(), i);
	else
		li.push_back(i);
}
li.erase(itRemember);

하지만 위 코드를 보면 다르다. 총 100개의 노드를 만드는 도중에 10번째 인덱스를 기억한다. 그 후에 10번째 노드를 삭제할 때 기억했던 위치를 가져와서 삭제한다.

즉, 중간 삽입/삭제를 하는 과정만 보면 굉장히 빠르다 -> li.erase(itRemember);

하지만 이전 과정까지 같이보면 그렇지 않다는 것을 알 수 있다.

 

나중에 좀 더 보충해서 정리하자.

 

 

 

출처

https://www.inflearn.com/course/%EC%96%B8%EB%A6%AC%EC%96%BC-3d-mmorpg-1/dashboard

[C++과 언리얼로 만드는 MMORPG 게임 개발 시리즈] Part1: C++ 프로그래밍 입문 - 인프런 | 강의