list

전체 코드

📌 1. STL과 std::list 개요

STL (Standard Template Library)

• C++에서 제공하는 자료구조 및 알고리즘 라이브러리
• vector, list, map, set 등 다양한 컨테이너(Container) 포함
• 반복자(Iterator)와 알고리즘(Algorithm) 기능 제공

---

std::list란?

• 연결 리스트 (Linked List) 로 구현된 STL 컨테이너
• 배열(vector)과 다른 점
  • 동적 크기 변경 가능
  • 연속적인 메모리를 사용하지 않음
  • 중간 삽입/삭제가 빠름 (O(1))
  • 임의 접근(Random Access)이 불가능 (O(n))

---

📂 2. std::list 기본 사용법

리스트 선언 및 사용

#include <iostream>
#include <list>

using namespace std;

int main()
{
    list<int> li; // 정수형 리스트 선언

    // 리스트에 값 추가
    li.push_back(1);  // 끝에 추가
    li.push_front(0); // 앞에 추가

    cout << "First Element: " << li.front() << endl;
    cout << "Last Element: " << li.back() << endl;

    return 0;
}

✅ push_back(value): 리스트 뒤에 요소 추가
✅ push_front(value): 리스트 앞에 요소 추가
✅ front(): 리스트 첫 번째 요소 반환
✅ back(): 리스트 마지막 요소 반환

---

🔥 3. std::list의 삽입과 삭제

기본적인 요소 삽입과 삭제

list<int> li;

li.push_back(10);  // 끝에 추가
li.push_front(20); // 앞에 추가

li.pop_back();  // 마지막 요소 삭제
li.pop_front(); // 첫 번째 요소 삭제

✅ push_back() / push_front() → 요소 추가
✅ pop_back() / pop_front() → 요소 삭제

---

중간 삽입 및 삭제

list<int> li = {1, 2, 3, 4, 5};
list<int>::iterator it = li.begin();
advance(it, 2); // 반복자를 2칸 이동 (3을 가리킴)

// 중간 삽입
li.insert(it, 100); // 3 앞에 100 삽입

// 중간 삭제
li.erase(it); // 3 삭제

✅ insert(it, value): 특정 위치에 요소 삽입
✅ erase(it): 특정 위치의 요소 삭제
✅ advance(it, n): it를 n칸 이동

---

🔄 4. std::list와 반복자(Iterator)

기본적인 반복자 사용법

list<int> li = {10, 20, 30, 40, 50};

for (list<int>::iterator it = li.begin(); it != li.end(); ++it) {
    cout << *it << " ";
}

✅ begin(): 리스트의 첫 번째 요소를 가리키는 반복자 반환
✅ end(): 리스트의 마지막 요소 다음을 가리키는 반복자 반환

---

역방향 반복자 (reverse_iterator)

list<int>::reverse_iterator rit;

for (rit = li.rbegin(); rit != li.rend(); ++rit) {
    cout << *rit << " ";  // 50 40 30 20 10
}

✅ rbegin() → 마지막 요소부터 시작
✅ rend() → 첫 번째 요소 이전까지

---

🚀 5. std::list의 특정 값 삭제

list<int> li = {1, 2, 3, 4, 2, 5};

li.remove(2); // 값이 2인 모든 요소 삭제

✅ remove(value): 리스트에서 특정 값과 일치하는 모든 요소 삭제

---

🚀 6. 사용자 정의 List 클래스 구현

이중 연결 리스트 (Doubly Linked List) 직접 구현

#include <iostream>

using namespace std;

// 노드 클래스
template<typename T>
class Node {
public:
    Node* _next;
    Node* _prev;
    T _data;

    Node(const T& value) : _next(nullptr), _prev(nullptr), _data(value) {}
};

// 반복자 클래스
template<typename T>
class Iterator {
public:
    Node<T>* _node;

    Iterator(Node<T>* node) : _node(node) {}

    Iterator& operator++() {
        _node = _node->_next;
        return *this;
    }

    T& operator*() { return _node->_data; }
    bool operator==(const Iterator& right) { return _node == right._node; }
    bool operator!=(const Iterator& right) { return _node != right._node; }
};

// 리스트 클래스
template<typename T>
class List {
private:
    Node<T>* _header;
    int _size;

public:
    List() : _size(0) {
        _header = new Node<T>(T());
        _header->_next = _header;
        _header->_prev = _header;
    }

    ~List() {
        while (_size > 0)
            pop_back();
        delete _header;
    }

    void push_back(const T& value) {
        AddNode(_header, value);
    }

    void pop_back() {
        RemoveNode(_header->_prev);
    }

    Node<T>* AddNode(Node<T>* before, const T& value) {
        Node<T>* node = new Node<T>(value);
        Node<T>* prevNode = before->_prev;
        prevNode->_next = node;
        node->_prev = prevNode;
        node->_next = before;
        before->_prev = node;
        _size++;
        return node;
    }

    Node<T>* RemoveNode(Node<T>* node) {
        Node<T>* prevNode = node->_prev;
        Node<T>* nextNode = node->_next;
        prevNode->_next = nextNode;
        nextNode->_prev = prevNode;
        delete node;
        _size--;
        return nextNode;
    }

    typedef Iterator<T> iterator;
    iterator begin() { return iterator(_header->_next); }
    iterator end() { return iterator(_header); }
};

// 메인 함수
int main() {
    List<int> li;

    li.push_back(10);
    li.push_back(20);
    li.push_back(30);

    for (List<int>::iterator it = li.begin(); it != li.end(); ++it)
        cout << *it << " ";

    return 0;
}

✅ List<T> 클래스: 사용자 정의 연결 리스트 구현
✅ push_back() / pop_back(): 리스트 요소 추가 및 삭제
✅ begin() / end(): 반복자를 반환하여 리스트 순회

---