📌 list

이중 연결 리스트 기반의 자료구조이다.

💿 연결 리스트?

각 데이터들이 노드 (Node)로 연결되어 있는 자료구조로, 각 노드는 데이터를 저장하는 변수와 다음 노드를 가리키는 포인터 변수로 구성된다.

💿 선언 방법

1. 비어있는 list를 생성하는 경우 : list <데이터 타입> 이름;
2. list의 초기값을 지정하는 경우 : list <데이터 타입> 이름 ({초기값});
   ex)
   list <int> list_test({0, 1, 2, 3, 4});
   위 예시의 경우 해당 list의 front가 가리키는 값은 0

💿 시간 복잡도

1. 임의의 원소에 접근하는 경우 : O(n)
2. 특정 원소를 검색하는 경우 : O(n)
3. 임의의 위치에 원소를 삽입 / 삭제하는 경우 : O(1)

💿 장 / 단점

• 장점

1. 연속적인 메모리 공간을 필요로 하지 않는다.
2. 양방향 반복자를 제공하므로 양쪽 방향으로 순회가 가능하다.

• 단점

1. 노드에 대한 포인터를 포함하고 있기 때문에 추가적인 메모리 비용이 발생한다.
2. 원소의 삽입 / 삭제의 시간 복잡도가 O(1) 이지만, 실제로는 메모리의 할당 / 해제가 빈번하게 일어나기 때문에 실제 동작 속도는 느릴 수 있다.

💿 list vs vector

	vector	list
내부 구조	동적 배열 (Dynamic Array)	이중 연결 리스트 (Doubly Linked List)
메모리 구조	연속된 메모리 블록 사용	비연속적인 메모리 블록 사용, 블록끼리 포인터로 연결
임의 접근 (Random Access)	가능	불가능
삽입 / 삭제 성능	push_back, pop_back의 성능은 빠름 (O(1)) 중간 삽입 / 삭제 성능은 좋지 않음 (O(n))	어느 위치든 삽입 / 삭제가 빠름 (O(1))(iterator 기준)
메모리 재할당	크기가 커질 때 재할당이 일어날 수 있음	노드 단위로 동적 할당하기 때문에 메모리 재할당이 없음
캐시 효율성	높음 (연속 메모리)	낮음 (포인터 기반 구조)
사용 용도	데이터가 자주 변경되지 않고, 빠른 접근이 필요한 경우	빈번한 삽입 / 삭제가 있는 경우

---

이미지 출처

모든 이미지 출처