📚 List

List 정리

---

📚 List란?

• C++에서 연결 리스트를 다루는 STL 컨테이너중 하나이다.
• List는 양방향 연결 리스트로 구현되어있으며 리스트는 각요소가 두개의 포인트를 가진다(이전노드와 다음노드)

---

🔎 주요특징

1. 양방향 연결 리스트
   • 각 요소는 이전노드와 다음노드의 포인터를 가진다.
   • 이러한 구조로 앞 뒤 양방향으로 리스트를 순회할 수 있다.
2. 동적 크기를 갖는다.
   • 즉, 리스트는 프로그램 실행 중에 변경될 수 있어 배열과 달리 삽입, 삭제할 때 크기 변경이 빠르다는 장점이 있다.
3. 비연속 메모리 할당
   • 리스트는 각 요소가 동적으로 할당된 메모리를 갖는다. 따라서 연속적인 메모리 블록을 요구하는 배열과는 다르게, 리스트의 요소들은 메모리상에 흩어져 있을 수 있다.

---

💻 기본 연산

1. 헤더

   #include <list>
   

2. 생성

   list<타입> 변수명;
   

3. 삽입

   list.push_back(10); //리스트 뒤에 10 삽입
   list.push_front(20); // 리스트 앞에 20 삽입
   

4. 삭제

   list.pop_front(); // 리스트 첫번째 요소 제거
   list.pop_back(); // 리스트 마지막 요소 제거
   

5. 순회
   • 리스트는 iterator(반복자)를 사용하여 순회

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

• list에서 end()는 리스트의 마지막 요소 다음을 가리키는 특수한 위치 를 나타낸다.
• 실제 데이터가 아니며 리스트의 끝을 나타내는 iterator(반복자)이다.

1. 크기가 비어있는지 확인

   list.empty(); //리스트가 비어있는지 확인 true와 false 값을 출력함
   list.size(); // 리스트 크기 확인
   

2. 다양한 멤버 함수

   list.clear(); // 모든 요소 제거
   list.insert(); // 특정 위치에 요소 삽입
   list.erase(); // 특정 위치의 요소 삭제
   list.resize(); // 리스트의 크기를 변경
   list.sort(); // 리스트 정렬
   

---

💻 예시

#include <iostream>
#include <list>

using namespace std;

int main()
{
    list<int> myList = {10, 20, 30};


    //요소 추가
    myList.push_back(40); // 리스트 뒤에 40 삽입
    myList.push_front(1); // 리스트 앞에 1 삽입

    //순회
    for(auto it = myList.begin(); it != myList.end(); ++it)
    {
        cout << *it << endl;
    }
    // it 은 포인터가 아닌데 어떻게 역참조를 바로할 수 있을까?
    // 이유는 list의 iterator(반복자)가 포인터처럼 동작하기 때문이다.
    //반복자는 포인터처럼 동작하도록 설계되었기 때문에 역참조, 증가, 비교 연산자를 사용 가능하다

    // ++it VS it++
    // 둘이 마지막 결과에 대한 차이는 없음
    // 하지만 최적화에서 극명한 차이가 있음
    // it++ 은 임시 객체를 생성해 원래 값을 저장한 후, 이동연산을 함
    // ++it 은 바로 반복자를 다음 위치로 이동한 후, 이동된 반복자를 반환해서 메모리를 사용하지 않음
    //it++ 은 임시 객체를 생성해야 하기 때문에 약간의 오버헤드 발생! 
    //그래서 반복문내에서 반복자를 이동시키는 경우에는 항상 '++변수'를 사용한다.

    //사이즈의 크기
    myList.size();

    //리스트에서 요소 삭제
    myList.pop_front(); // 리스트 첫번째 요소 삭제
    myList.pop_back(); // 리스트 마지막 요소 삭제

    return 0;
}

---

📌 장점과 단점

장점

• 빠른 삽입과 삭제 : (O(n)) 의 시간 복잡도
• 동적 크기 : 메모리 크기를 미리 알지 못하는 경우에도 유동적으로 리스트의 크기를 조정 가능함

단점

• 느린 접근 : 배열보다 느림, 요소를 순차적으로 접근해야하기 때문 (O(n)) 의 시간복잡도
• 메모리 사용 : 앞, 뒤 노드의 포인터를 가지기 때문에 배열에 비해 더 많은 메모리를 사용

• stl
• c
• list