반응형
안녕하세요. C++을 다루기 위한 기본 적인 자료 구조와 코딩 테스트 등에서 응용될 수 있는 알고리즘을 알아보는 시간을 가지겠습니다.
이번 게시물은 std::list를 간단히 설명해 보려 합니다.
게시물 끝에 std::list를 사용한 stack과 queue 구현 예시도 있으니까 참고 바랍니다!
1) 특징
std::list는 C++ 표준 라이브러리에서 제공하는 연결 리스트 기반 자료구조입니다. 연결 리스트는 각 데이터들이 노드로 연결되어 있는 자료구조로, 각 노드는 데이터를 저장하는 변수와 다음 노드를 가리키는 포인터 변수로 구성됩니다.
std::list는 이와같은 연결 리스트의 기능을 제공하여 데이터의 삽입, 삭제, 검색 등의 작업을 효율적으로 수행할 수 있도록 합니다.
2) 속성 (Attributes)
std::list는 <list> 헤더를 포함해서 사용할 수 있습니다.
우선 다음과 같은 std::list의 주요 속성과 멤버 함수를 통해 해당 자료 구조를 활용하는 방법을 자세하게 알아보겠습니다.
- push_back(value)
: 리스트 끝에 요소를 추가합니다. - push_front(value)
: 리스트의 시작에 요소를 추가합니다. - pop_back()
: 리스트의 마지막 요소를 제거합니다. - pop_front()
: 리스트의 첫 번째 요소를 제거합니다. - size()
: 리스트의 현재 크기를 반환합니다. - empty()
:리스트가 비어 있는지 여부를 확인합니다. - clear()
: 리스트의 모든 요소를 제거합니다. - insert(position, value)
: 지정된 위치에 요소를 삽입합니다. - erase(position)
: 지정된 위치의 요소를 제거합니다. - remove(value)
: 지정된 값과 일치하는 모든 요소를 제거합니다. - sort()
: 리스트를 오름차순으로 정렬합니다. - reverse()
: 리스트의 순서를 반대로 뒤집습니다. - begin()
: 리스트의 첫 번째 요소를 가리키는 반복자를 반환합니다. - end()
: 리스트의 끝을 나타내는 반복자를 반환합니다.
3) 속성 사용 예시
다음은 std::list의 속성 사용 예시입니다.
- push_back(value)
: 리스트 끝에 요소를 추가합니다.
std::list<int> myList;
myList.push_back(10);
myList.push_back(20);
myList.push_back(30);- push_front(value)
: 리스트의 시작에 요소를 추가합니다.
std::list<int> myList;
myList.push_front(10);
myList.push_front(20);
myList.push_front(30);- pop_back()
: 리스트의 마지막 요소를 제거합니다.
std::list<int> myList;
myList.push_back(10);
myList.push_back(20);
myList.pop_back();- pop_front()
: 리스트의 첫 번째 요소를 제거합니다.
std::list<int> myList;
myList.push_back(10);
myList.push_back(20);
myList.pop_front();- size()
: 리스트의 현재 크기를 반환합니다.
std::list<int> myList;
myList.push_back(10);
myList.push_back(20);
std::cout << "Size: " << myList.size() << std::endl;- empty()
:리스트가 비어 있는지 여부를 확인합니다.
std::list<int> myList;
if (myList.empty()) {
std::cout << "List is empty" << std::endl;
}- clear()
: 리스트의 모든 요소를 제거합니다.
std::list<int> myList;
myList.push_back(10);
myList.push_back(20);
myList.clear();- insert(position, value)
: 지정된 위치에 요소를 삽입합니다.
std::list<int> myList;
myList.push_back(10);
myList.push_back(20);
auto it = myList.begin();
it++; // 이동하여 두 번째 위치에 삽입
myList.insert(it, 15);- erase(position)
: 지정된 위치의 요소를 제거합니다.
std::list<int> myList;
myList.push_back(10);
myList.push_back(20);
auto it = myList.begin();
it++; // 두 번째 위치의 요소를 제거
myList.erase(it);- remove(value)
: 지정된 값과 일치하는 모든 요소를 제거합니다.
std::list<int> myList;
myList.push_back(10);
myList.push_back(20);
myList.push_back(10);
myList.remove(10); // 10에 해당하는 모든 요소를 제거- sort()
: 리스트를 오름차순으로 정렬합니다.
std::list<int> myList;
myList.push_back(30);
myList.push_back(10);
myList.push_back(20);
myList.sort(); // 10, 20, 30으로 정렬- reverse()
: 리스트의 순서를 반대로 뒤집습니다.
std::list<int> myList;
myList.push_back(10);
myList.push_back(20);
myList.push_back(30);
myList.reverse(); // 30, 20, 10으로 순서 뒤집기- begin()
: 리스트의 첫 번째 요소를 가리키는 반복자를 반환합니다. - end()
: 리스트의 끝을 나타내는 반복자를 반환합니다.
std::list<int> myList = {1, 2, 3, 4, 5};
// 모든 요소 출력하기
for (auto it = myList.begin(); it != myList.end(); ++it) {
std::cout << *it << " ";
}
// 출력: 1 2 3 4 5
// 리스트의 첫 번째 요소 수정하기
if (!myList.empty()) {
*myList.begin() = 10;
}
// myList: {10, 2, 3, 4, 5}
// 리스트의 마지막 요소에 접근하기
auto lastElement = std::prev(myList.end());
std::cout << "Last element: " << *lastElement << std::endl;
// 출력: Last element: 5
// 요소 검색하여 제거하기
int target = 3;
for (auto it = myList.begin(); it != myList.end(); ++it) {
if (*it == target) {
myList.erase(it);
break;
}
}
// myList: {10, 2, 4, 5}
4) std::list를 활용한 stack과 queue 구현 예시
1. Stack 구현 예시
#include <iostream>
#include <list>
template <typename T>
class Stack {
private:
std::list<T> stack;
public:
void push(const T& item) {
stack.push_back(item);
}
void pop() {
if (!stack.empty()) {
stack.pop_back();
}
}
T& top() {
return stack.back();
}
bool empty() const {
return stack.empty();
}
};
int main() {
Stack<int> stack;
stack.push(1);
stack.push(2);
stack.push(3);
while (!stack.empty()) {
std::cout << stack.top() << " ";
stack.pop();
}
// 출력: 3 2 1
return 0;
}
2. Queue 구현 예시
#include <iostream>
#include <list>
template <typename T>
class Queue {
private:
std::list<T> queue;
public:
void enqueue(const T& item) {
queue.push_back(item);
}
void dequeue() {
if (!queue.empty()) {
queue.pop_front();
}
}
T& front() {
return queue.front();
}
bool empty() const {
return queue.empty();
}
};
int main() {
Queue<int> queue;
queue.enqueue(1);
queue.enqueue(2);
queue.enqueue(3);
while (!queue.empty()) {
std::cout << queue.front() << " ";
queue.dequeue();
}
// 출력: 1 2 3
return 0;
}반응형