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

STL 은 C++ 표준 템플릿 라이브러리이고, 일반적으로 가장 많이 사용되는 라이브러리는 컨테이너 라이브러리 입니다. 컨테이너는 말 그대로 자료 형들을 담는 역할을 하고 STL 컨테이너는 list, vector, deque, map, set 이 있습니다. 이 포스트에서는 list 에 대해서 다뤄보겠습니다.

 

List 의 자료구조는 연결 리스트로 되어 있다.

List 는 앞뒤로 모두 이동이 가능한 이중연결 리스트로 이루어져 있습니다. 연결 리스트는 일반적인 배열과는 다르게 조금 복잡한 모양과 구현 과정을 가지는데요, 이러한 자료구조를 사용함으로써 얻는 몇 가지 이득이 있습니다.

1. 길이가 가변적이다.
   
   • 배열은 처음 설정할 때 그 크기를 정해줘야 하고, 이 크기를 넘어서는 데이터가 들어가면 컴파일 오류를 일으키는 반면, 연결 리스트는 동적으로 크기를 변경할 수 있습니다.
2. 데이터의 삽입, 삭제가 용이하다.
   • 배열의 중간에 데이터를 삽입하거나 삭제하려면 해당 위치의 앞뒤 데이터들의 배치를 변경해주어야 하는 반면, 연결 리스트에서의 데이터의 삽입, 삭제는 해당 위치의 바로 앞, 뒤 노드의 연결 고리만 바꾸어 주면 되므로 비교적 용이합니다.

위와 같은 장점도 있지만 단점도 분명히 존재하는데요, 연결 리스트는 그 구조의 특성상 중간의 데이터에 접근할 때 랜덤 접근이 불가하고 순차 접근만 가능합니다. 연결 리스트의 head 에서부터 시작하여 해당 노드를 찾아주어야 하기 때문에 검색 및 접근 속도는 배열에 비해 느려집니다. 그렇기 때문에 List 를 사용하기 전에 사용하고자 하는 프로그램의 특성을 잘 따져보아야 합니다. 저장할 데이터의 개수가 가변적이고, 데이터의 삽입과 삭제가 자주 일어나며, 데이터에 랜덤하게 접근하는 경우가 많지 않은 경우에 사용하기에 적합합니다.

 

List 의 사용방법

List 를 사용하기 위해서는 list 헤더파일을 포함해주어야 합니다.

#include <list>

 

또한,  namespace 를 선언해주거나, STL 라이브러리 앞에 namespace 를 적어주어야 합니다.

 

using namespace std; // namespace 선언

std::list<int> myList; // namespace 선언 없이 사용할 경우

 

또 한 가지 특징으로 List 에는 반복자(iterator) 라는 개념이 있습니다. 연결 리스트를 탐색할 때 사용하는 포인터와 비슷한 개념으로 List 에 저장된 데이터에 접근하기 위하여 사용되며 컨테이너에서 특정 위치를 가리키며 포인터와 비슷하게 ++ 와 -- 와 이동합니다. 반복자는 아래와 같이 사용합니다.

list<int>::iterator firstIterator = myList.begin();

여기서 begin() 멤버함수는 해당 List 의 첫번째 요소를 가리키는 반복자를 반환합니다. 이와 비슷하게 end() 는 List 의 맨 마지막의 다음 요소를 가리키고, 역 방향으로 rbegin(), rend() 도 있습니다.

// 반복자의 사용을 보여주는 예시
list<int> myList;
for(list<int>::iterator iterPos = myList.begin(); iterPos != myList.end(); iterPos++){
    cout<<*iterPos<<endl;
}

 

List 의 주요 멤버들

 

멤버	설명
begin	컨테이너의 첫 번째 요소
end	컨테이너의 마지막의 다음 요소
rbegin	역순으로 첫 번째 요소
rend	역순으로 마지막의 다음 요소
push_front	맨 앞에 데이터 추가
push_back	맨 뒤에 데이터 추가
pop_front	맨 앞에서 데이터 하나 삭제
pop_back	맨 뒤에서 데이터 하나 삭제
front	맨 앞의 데이터의 참조 반환
back	마지막 데이터의 참조 반환
clear	컨테이너의 모든 데이터 삭제
empty	컨테이너가 저장하고 있는 데이터가 없으면 true, 아니면 false 반환
size	컨테이너가 저장하고 있는 요소의 개수 반환
insert	특정 위치에 데이터 삽입
erase	지정한 범위의 데이터 삭제
remove	지정한 값과 일치하는 모든 데이터 삭제
remove_if	조건을 만족하는 모든 데이터 삭제
sort	데이터들을 정렬

 

위의 멤버들의 사용 방법은 아래 코드를 확인하기 바란다.

#include <iostream>
#include <list>
using namespace std;

int main(){
    list<int> myList;

    myList.push_front(3); // 맨 앞에 3 추가
    myList.push_front(2); // 맨 앞에 2 추가
    myList.push_front(1); // 맨 앞에 1 추가
    myList.push_back(10); // 맨 뒤에 10 추가
    myList.push_back(11); // 맨 뒤에 11 추가
    myList.push_back(12); // 맨 뒤에 12 추가

	// iterator 사용하여 list 의 데이터 전체 출력
    for(list<int>::iterator iter = myList.begin(); iter != myList.end(); iter++){
        cout<<"List 의 데이터 : "<<*iter<<endl;
    }

    cout<<"첫 번째 데이터 : "<<myList.front()<<endl;
    cout<<"마지막 데이터 : "<<myList.back()<<endl;
    cout<<"데이터의 개수 : "<<myList.size()<<endl;

    myList.pop_front(); // 맨 앞 데이터 하나 삭제
    myList.pop_back(); // 맨 뒤 데이터 하나 삭제
    cout<<"데이터의 개수 : "<<myList.size()<<endl;

    myList.insert(myList.begin(), 2); // myList 의 첫번째 위치에 2 삽입
    myList.insert(myList.end(), 2, 100); // myList 의 마지막 위치에 100을 2개 삽입

    list<int>::iterator frontIter = myList.begin();
    for(int i = 0; i < 3; i++) frontIter++; // 4번째 요소를 가리키는 iterator 를 생성

    cout<<"4번쨰부터 마지막 데이터 삭제"<<endl;
    myList.erase(frontIter, myList.end());

    myList.remove(3); // list 에서 값이 3 인 요소 모두 삭제

    myList.clear(); // list 의 요소 전체 삭제
    cout<<myList.size()<<endl;
    cout<<myList.empty()<<endl;

    return 0;
}