[C++ STL] 리스트 (List)

개요

양방향 연결 구조를 가진 자료형

양방향 연결 리스트와 같은 구조

 

벡터와 달리 임의의 위치에 있는 원소에 접근할 수 없음

리스트는 시작 원소와 마지막 원소의 위치만 기억하고 있기 때문

시작 또는 마지막 위치에서 반복자가 한 칸씩 움직이는 방식으로만 접근할 수 있다.

 

양방향 연결 리스트와 같이 각각의 원소들이 링크로 이어져 있기 때문에 실제 메모리 상에서 연속적으로 존재하지 않을 수 있다.

시간 복잡도

• 중간에 원소 삽입 / 제거:O(1)
  • 연결 관계만 바꿔주면 되기 때문에 매우 빠름

주요 기능 및 특징

반복자

리스트의 반복자의 타입은 BidirectionalIterator 타입이다.

이 반복자는 양방향으로 이동할 수 있되, 한 칸씩만 이동 가능하다.

++ / -- 연산

리스트의 반복자에 ++, --를 사용해 반복자를 왼쪽 / 오른쪽으로 한 칸씩 움직일 수 있다.

원소 삽입 / 제거

원소 삽입에 insert(), 원소 제거에 erase() 함수를 사용한다.

벡터와는 다르게 원소를 지워도 반복자가 무효화 되지 않는다.

std::list<int> lst;

// 리스트를 순회하면서 처음으로 20인 원소를 찾으면 그 앞에 50을 삽입
for (auto iter = lst.begin(); iter != lst.end(); ++iter)
{
    if (*iter == 20)
    {
    	iter.insert(iter, 50);
        break;
    }
}

// 리스트를 순회하면서 처음으로 30인 원소를 찾으면 제거
for (auto iter = lst.begin(); iter != lst.end(); ++iter)
{
    if (*iter == 30)
    {
    	lst.erase(iter);
        break;
    }
}

참고 및 이미지 출처

모두의 코드 - 씹어먹는 C++ PDF [https://modoocode.com/312]