STL :: list

동적 배열에 사용되는 자료구조이다.

출처 : Geeks for Geeks

 

Doubly Linked LIst 형태로 구현되어 있어 앞뒤로 요소 삽입이 가능하다는 특징이 있다.

 

자 지금까지 array나 vector 같은 배열들의 경우는 연속된 메모리 공간에 할당되어 Random Access가 가능했다.

(A[3] 이런 접근)

 

하지만 List가 linked list 형태로 제작되었다는 건?

⇒ 메모리 상에서 연속된 공간이 아니라는 것

⇒ 인접 Node에 저장된 pointer로만 접근이 가능하다는 것

 

때문에 list는 Random Access가 불가능하다.

오직 Iterator를 이용한 접근 만이 가능하다.

 

그래서 이런 구조가 유용하지 않은가?

그건 아니다.

 

이런 Linked List 형태는 중간에 요소를 삽입하거나 삭제하는 과정이 매우 간단하다.

출처 : Geeks for Geeks

 

Vector나 Array가 요소 삽입을 위해 나머지 요소들의 위치를 바꿔야 한다면,

list는 그저 pointer가 가리키는 주소만 바꿔주면 된다.

 

이는 삽입과 삭제가 많은 작업에서 큰 이점으로 작용할 수 있다.

 

기본 사용법

#include <iostream>
#include <list>

int main() {
    // std::list 선언 및 초기화
    std::list<int> myList = {1, 2, 3, 4, 5};

    // 리스트 크기
    std::cout << "리스트 크기: " << myList.size() << std::endl;

    // 리스트의 끝에 요소 추가
    myList.push_back(6);

    // 리스트의 시작에 요소 추가
    myList.push_front(0);

    // 리스트 순회
    for (const auto& element : myList) {
        std::cout << element << " ";
    }
    std::cout << std::endl;

    return 0;
}

 

 

요소 중간 삽입/삭제

std::list<int> myList = {1, 2, 3, 4, 5};
auto it = std::next(myList.begin(), 2);  // 세 번째 요소 위
myList.insert(it, 99);  // 중간에 99를 삽입
myList.erase(std::next(myList.begin(), 3));  // 네 번째 요소 삭제

for (auto& a : myList) {
	std::cout << a << ' ';
}

next를 통해 원하는 위치를 지정할 수 있다.

 

위 코드 출력은 아래와 같다.