C++ STL의 list(리스트)는 비연속적인(non-contiguous) 메모리 할당을 허용하는 시퀀스 컨테이너입니다. vector와 달리 내부적으로 이중 연결 리스트(doubly linked list) 방식으로 동작하기 때문에 임의 접근(random access)은 지원하지 않지만, 위치(iterator)를 찾은 이후에는 삽입과 삭제가 O(1)의 매우 빠른 속도로 처리된다는 장점이 있습니다.
반면 요소들이 메모리상에 연속되어 있지 않아 처음부터 끝까지 순회(traversal)할 때는 vector보다 느릴 수 있습니다. 따라서 데이터의 빈번한 삽입·삭제가 많고 순차 탐색 위주로 사용하는 상황에서 list가 적합합니다.
list 컨테이너의 주요 함수
이번 예제 프로그램의 main() 함수에서는 아래와 같은 멤버 함수들을 호출하여 리스트를 조작합니다.
fl.resize() = 리스트의 크기를 새로 조정합니다. fl.push_front() = 리스트의 맨 앞에 새 요소를 추가합니다. fl.remove() = 특정 값과 일치하는 모든 요소를 삭제합니다. fl.unique() = 인접한 중복 요소를 제거합니다. fl.reverse() = 리스트 전체의 순서를 역순으로 뒤집습니다. fl.front() = 리스트의 첫 번째(맨 앞) 요소를 반환합니다.
참고: unique()는 서로 인접해 있는 중복 요소만 제거합니다. 위 실행 결과에서 4 5 7 6 5처럼 중복값이 떨어져 있는 경우에는 unique()를 호출해도 그대로 유지되는데, 이는 정상 동작입니다. 정렬 후 sort()와 함께 사용하면 모든 중복을 제거할 수 있습니다.
전체 예제 코드
아래 프로그램은 메뉴 기반으로 리스트에 요소를 삽입·삭제하고, 크기 확인, 크기 변경, 특정 값 삭제, 중복 제거, 역순 변환, 전체 출력 등 다양한 연산을 테스트할 수 있도록 작성되었습니다.
#include<iostream>
#include <list>
#include <string>
#include <cstdlib>
using namespace std;
int main() {
list<int> l;
list<int>::iterator it;
int c, i;
while (1) {
cout<<"1.Insert Element at the Front"<<endl;
cout<<"2.Insert Element at the End"<<endl;
cout<<"3.Delete Element at the Front"<<endl;
cout<<"4.Delete Element at the End"<<endl;
cout<<"5.Front Element of List"<<endl;
cout<<"6.Last Element of the List"<<endl;
cout<<"7.Size of the List"<<endl;
cout<<"8.Resize List"<<endl;
cout<<"9.Remove Elements with Specific Values"<<endl;
cout<<"10.Remove Duplicate Values"<<endl;
cout<<"11.Reverse the order of elements"<<endl;
cout<<"12.Display the List"<<endl;
cout<<"13.Exit"<<endl;
cout<<"Enter your Choice: ";
cin>>c;
switch(c) {
case 1:
cout<<"Enter value to be inserted at the front: ";
cin>>i;
l.push_front(i);
break;
case 2:
cout<<"Enter value to be inserted at the end: ";
cin>>i;
l.push_back(i);
break;
case 3:
i= l.front();
l.pop_front();
cout<<"Element "<<i<<" deleted"<<endl;
break;
case 4:
i= l.back();
l.pop_back();
cout<<"Element "<<i<<" deleted"<<endl;
break;
case 5:
cout<<"Front Element of the List: ";
cout<<l.front()<<endl;
break;
case 6:
cout<<"Last Element of the List: ";
cout<<l.back()<<endl;
break;
case 7:
cout<<"Size of the List: "<<l.size()<<endl;
break;
case 8:
cout<<"Enter new size of the List: ";
cin>>i;
if (i <= l.size())
l.resize(i);
else
l.resize(i, 0);
break;
case 9:
cout<<"Enter element to be deleted: ";
cin>>i;
l.remove(i);
break;
case 10:
l.unique();
cout<<"Duplicate Items Deleted"<<endl;
break;
case 11:
l.reverse();
cout<<"List reversed"<<endl;
break;
case 12:
cout<<"Elements of the List: ";
for (it = l.begin(); it != l.end(); it++)
cout<<*it<<" ";
cout<<endl;
break;
case 13:
exit(1);
break;
default:
cout<<"Wrong Choice"<<endl;
}
}
return 0;
}
실행 결과
1.Insert Element at the Front 2.Insert Element at the End 3.Delete Element at the Front 4.Delete Element at the End 5.Front Element of List 6.Last Element of the List 7.Size of the List 8.Resize List 9.Remove Elements with Specific Values 10.Remove Duplicate Values 11.Reverse the order of elements 12.Display the List 13.Exit Enter your Choice: 1 Enter value to be inserted at the front: 1 ... Enter your Choice: 12 Elements of the List: 7 6 5 ... Enter your Choice: 12 Elements of the List: 4 5 7 6 5 ... Enter your Choice: 10 Duplicate Items Deleted ... Enter your Choice: 5 Front Element of the List: 4 ... Enter your Choice: 11 List reversed ... Enter your Choice: 12 Elements of the List: 5 6 7 5 4 ... Enter your Choice: 13
핵심 정리
- push_front / pop_front: 맨 앞 요소의 삽입·삭제를 상수 시간(O(1))에 처리합니다.
- remove(v): 값 v와 같은 모든 요소를 한 번에 제거합니다.
- unique(): 인접한 중복 요소만 제거하므로, 완전한 중복 제거가 필요하다면 먼저 sort()를 수행하세요.
- reverse(): 포인터 연결 방향만 바꾸기 때문에 매우 효율적으로 리스트를 뒤집습니다.
- resize(n): 현재 크기보다 작게 줄이면 초과분이 삭제되고, 크게 늘리면 나머지는 지정한 값(기본 0)으로 채워집니다.