list

1. std::list의 기본

🌟 std::list의 정의와 특징

• 연결 리스트: 노드와 포인터로 이루어진 데이터 구조. 각 노드는 데이터를 포함하고 다음/이전 노드를 가리키는 포인터를 가지고 있습니다.
• 연속 메모리 아님: 벡터와 달리, 데이터가 메모리에 연속적으로 저장되지 않습니다.
• 양방향 연결: 각 노드가 이전 노드와 다음 노드에 대한 정보를 가집니다.

---

1-1. size와 capacity

• size:
  • 리스트의 노드 개수를 나타냅니다.
  • size() 함수로 확인합니다.
• capacity:
  • 벡터와 달리 리스트에는 존재하지 않습니다. 이는 메모리가 연속적이지 않기 때문입니다.

예제: 리스트 초기화

std::list<int> li{1, 2, 3, 4, 5};
std::cout << "Size: " << li.size() << std::endl;  // 출력: Size: 5

---

1-2. 데이터 삽입 및 추출의 시간 복잡도

• 리스트는 데이터 삽입 및 삭제가 효율적입니다.
• 시간 복잡도:
  • 앞쪽 삽입 (push_front): O(1)
  • 뒤쪽 삽입 (push_back): O(1)
  • 중간 삽입:
    • O(1): 삽입 위치가 이미 주어진 경우 (예: 반복자를 통해).
    • O(N): 삽입 위치를 찾기 위해 탐색이 필요한 경우.
  • 삭제 (erase): O(1) (삽입과 동일한 조건 하에서).

예제: 데이터 삽입 및 삭제

std::list<int> li;
li.push_front(10);  // 앞에 삽입
li.push_back(20);   // 뒤에 삽입
auto it = li.begin();
li.insert(it, 15);  // 중간 삽입
li.erase(it);       // 중간 삭제

---

1-3. 임의 접근

• 리스트는 임의 접근(예: list[3])을 지원하지 않습니다.
• 데이터를 탐색하려면 반복자(iterator)를 사용해야 합니다.

---

1-4. 순회

리스트의 요소를 순회하려면 반복자를 사용합니다.

1) 기본 순회 코드

std::list<int> li{1, 2, 3, 4, 5};
for (auto it = li.begin(); it != li.end(); ++it) {
    std::cout << *it << " ";
}
// 출력: 1 2 3 4 5

2) 값 제거하면서 순회

for (auto it = li.begin(); it != li.end();) {
    if (*it % 2 == 0) {  // 짝수인 경우
        it = li.erase(it);  // 현재 노드 삭제 후 다음 반복자로 갱신
    } else {
        ++it;  // 다음 노드로 이동
    }
}

---

1-5. insert와 erase의 활용

• insert(iterator pos, value):
  • 반복자 pos의 위치에 값을 삽입합니다.
  • 삽입 후 반환값은 삽입된 요소를 가리키는 반복자입니다.
• erase(iterator pos):
  • 반복자 pos가 가리키는 노드를 제거합니다.
  • 제거 후 반환값은 제거된 다음 노드를 가리키는 반복자입니다.

예제

std::list<int> li{1, 2, 3};
auto it = li.end();
it = li.insert(it, 4);  // 끝에 4 삽입
li.insert(it, 100);     // 4 앞에 100 삽입
li.erase(it);           // 4 삭제

---

1-6. 리스트 속도

• 리스트는 노드를 따라 이동해야 하기 때문에 순차 탐색이 필요하며, 벡터보다 임의 접근 속도가 느립니다.
• 삽입 및 삭제가 빈번한 작업에 적합합니다.

---

2. std::list의 반복자

리스트는 양방향 반복자를 제공합니다. 벡터의 반복자보다 구현 방식이 더 많고 복잡하며, 다음과 같은 특징이 있습니다:

• 양방향: 앞뒤로 이동할 수 있습니다.
• 노드 기반: 각 반복자가 노드를 직접 가리킵니다.

---

2-1. 반복자 구현

1) 생성자

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

• 반복자는 노드를 가리키는 _node 포인터를 멤버로 가집니다.
• 생성자를 통해 특정 노드를 가리키는 반복자를 생성할 수 있습니다.

---

2) 전위형 증가 연산자

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

• _node를 다음 노드로 이동시키고, 이동한 반복자를 반환합니다.

---

3) 후위형 증가 연산자

Iterator operator++(int) {
    Iterator temp = *this;
    _node = _node->next;
    return temp;
}

• 현재 반복자를 복사한 temp를 반환하고, _node를 다음 노드로 이동시킵니다.

---

4) 역참조 연산자

T& operator*() {
    return _node->data;
}

• 반복자가 가리키는 노드의 데이터를 참조합니다.

---

5) 동등/비동등 비교 연산자

bool operator==(const Iterator& other) const {
    return _node == other._node;
}
bool operator!=(const Iterator& other) const {
    return _node != other._node;
}

• 두 반복자가 같은 노드를 가리키면 true를 반환합니다.

---

2-2. 리스트와 반복자 연동

리스트는 begin()과 end() 함수를 통해 반복자를 제공합니다.

iterator begin() { return iterator(_head->next); }
iterator end() { return iterator(_tail); }

• begin(): 첫 번째 데이터 노드를 가리키는 반복자를 반환합니다.
• end(): 마지막 더미 노드를 가리키는 반복자를 반환합니다.

---

2-3. 반복자 사용 예제

List<int> myList;
auto it = myList.begin();
while (it != myList.end()) {
    std::cout << *it << " ";
    ++it;
}

• begin()부터 end()까지 반복자를 사용해 리스트를 순회합니다.

---

2-4. 반복자를 활용한 양방향 이동

양방향 리스트의 반복자는 이전 노드로 이동하는 기능도 제공합니다.

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

---

3. std::list와 std::vector의 비교

특징	std::list	std::vector
메모리 구조	비연속적	연속적
임의 접근	지원하지 않음	지원 (O(1))
삽입/삭제	O(1) (특정 위치에서)	O(N) (중간 삽입/삭제)
순회 속도	느림 (포인터 따라 이동)	빠름 (메모리 연속성)
메모리 재할당	없음	필요 (용량 초과 시)

---