[C++ STL] std::list (시퀀스 컨테이너)

std::list

std::list는 이중 연결 리스트로 선형 구조를 가지는 시퀀스 컨테이너이며 노드 기반으로 데이터를 저장한다.

std::vector 컨테이너와는 달리 임의접근 연산자는 지원하지 않지만 push_front, push_pop 같은 기능을 지원한다.

이중 연결 리스트 자료구조를 이해했다면 전혀 어렵지 않다.

 

먼저 std::list를 사용하기 위해서는 list 헤더파일을 추가해야 한다.

기본적인 생성방법

// 비어있는 상태의 list 컨테이너를 생성
std::list<int> li;
// 0으로 초기화 된 요소 10개를 가진 list 컨테이너를 생성
std::list<int> li2(10);
// 5로 초기화 된 요소 10개를 가진 list 컨테이너를 생성
std::list<int> li3(10, 5);
// li4는 li3 list를 복사
std::list<int> li4(li3);

 

std::list 컨테이너의 멤버 함수를 하나씩 보자. (자주 사용하는 것 위주)

 

1. push_front, push_back, insert 함수 ★

// 비어있는 상태의 list 컨테이너를 생성
std::list<int> li;
li.push_front(10); // 제일 처음에 요소를 삽입한다.
li.push_back(20); // 제일 마지막에 요소를 삽입한다.
auto iter = (++li.begin());
li.insert(iter,15); // iterator가 가리키는 위치에 요소를 삽입한다.

결과

std::vector에도 존재하는 push_back함수. 제일 마지막에 요소를 삽입한다. std::list는 노드 기반으로 데이터를 저장하는 연결 리스트이기에 제일 처음에 요소를 삽입하는 게 비용이 많이 들지 않아 push_front함수도 존재한다.

 -> 둘 다 상수 시간 복잡도.

연결 리스트는 중간 삽입도 빠르다. 중간에 데이터가 들어가도 해당 자리의 노드의 포인터 연결고리를 수정하고 중간에 들어가는 새 노드의 포인터도 수정만 하면 끝이기에.

 

다만 중간 삽입의 연산은 빠르지만, std::list는 노드 기반으로 데이터를 저장하기에 당연히 임의 접근 연산이 안된다.

 -> vector는 메모리가 이어진 형태.  list는 노드의 형태로 저장된 데이터가 떨어져 있고 포인터로 연결된 형태

 -> 즉 삽입해야 할 위치를 모른다면 선형 탐색을 하면서 삽입할 위치를 찾아야 한다는 의미.

 -> 이럴 경우 std::vector의 중간 삽입에서 데이터를 한 칸씩 뒤로 물리고 데이터를 삽입하는 시간 복잡도와 std::list에서 위치를 찾고 삽입하는 시간 복잡도는 크게 다르지 않다.

 

2. pop_front, pop_back, erase, remove, remove_if 함수 ★

std::list<Test*> li2;
li2.push_back(new Test());
li2.push_back(new Test());
li2.push_back(new Test());
 
li2.pop_front();       // 제일 처음 노드를   제거한다.
li2.pop_back();        // 제일 마지막 노드를 제거한다.
li2.erase(li2.begin());// 반복자가 가리키는 위치의 노드를 제거한다.

먼저 pop_front, pop_back, erase함수부터 본다.

pop_front, pop_back 함수는 각각 제일 처음과 마지막 노드를 제거하는 함수.

erase는 인자로 넘긴 반복자(iterator)가 가리키는 노드를 제거하는 함수다.

std::list는 연결 리스트 구조. 처음이건 중간이건 마지막이건 삽입의 속도가 빠른데(O(1)), 삭제 또한 빠르다.

 -> 해당하는 노드를 제거하기 전 노드의 앞 뒤로 붙은 포인터를 연결해주고 삭제만 해주면 끝이기에

 

다만 위에서 중간 삽입의 연산이 빠르지만 제거해야 할 대상의 위치를 모른다면 결국 선형 탐색을 하여 삭제를 진행해야 하기에 속도는 vector의 erase와 크게 다를 바 없다.

 

더욱 주의해야할 것은 위 함수들은 std::list의 노드만을 제거하는 함수다.

위에서 list가 저장하는 데이터는 Test객체를 가리키는 포인터 변수. 현재 총 3개의 노드를 지우는 함수를 호출하였는데 객체도 소멸이 되었을지 확인해보면

생성자만 호출할 뿐 전혀 delete를 호출해주지 않는다.

즉 객체의 소멸은 사용자가 직접 처리해야하는 사항인 것. 이것을 잊으면 안된다.

 -> 사실 모든 컨테이너가 동일하다.

 

이제 remove와 remove_if함수를 본다. 먼저 remove함수

::srand(::time(nullptr));
std::list<int> li;
for (int i = 0; i < 100; ++i)
{
    int randValue = ::rand() % 100 + 1;
    li.push_back(randValue);
}
li.remove(30);

remove함수는 인자로 넘겨준 값이 list에 저장된 요소와 같은 노드가 있다면 모두 제거한다.

 -> 모두 제거한다는 의미는 처음부터 끝까지 선형 탐색을 하며 제거를 진행한다는 의미.

어렵지 않다. 예를들면 30 40 50 30 20 10 에서 remove(30)을 호출하면 list는 40 50 20 10 요소를 가지게 된다.

 

remove_if함수

::srand(::time(nullptr));
std::list<int> li;
for (int i = 0; i < 100; ++i)
{
    int randValue = ::rand() % 100 + 1;
    li.push_back(randValue);
}
li.remove_if
(
    [](int num) -> bool
    {
        return num >= 50;
    }
);

remove_if는 조건자(predicate)라는 bool값을 반환하는 함수를 넣어줘야 한다.

위 코드에서는 노드에 저장된 정수 데이터가 50을 넘으면 제거하는 코드를 넣었다. 결과는

100개의 데이터가 48개로. 52개가 없어졌다. 실제로 확인해보면 50이상의 데이터를 가진 모든 노드는 삭제되었음.

 

 

list 컨테이너의 장점

 - 어느 위치든 삽입과 제거에 걸리는 시간이 상수 시간 복잡도를 가진다(O(1))

 - vector와 달리 메모리 재할당의 비용이 들지 않는다.

list 컨테이너의 단점

 - vector와 달리 임의접근 연산이 불가능하다.

 - 메모리가 연속적으로 저장되는 vector와 달리 노드로 메모리가 떨어진 형태로 포인터를 이은것이기에 메모리가 불연속적.

 - 탐색이 느리다. 같은 선형 시간 복잡도(O(N))을 가진다하더라도 연속적인 메모리의 선형탐색과 불연속적인 메모리의 선형탐색은 시간차이가 존재 한다. (캐시효과)