250918 언리얼엔진 본캠프 33일차 list

list는 무엇인가?

list는 C++의 표준 템플릿 라이브러리 STL의 컨테이너에 속하는 sequence 컨테이너이다. sequence 컨테이너는 순서를 유지하는 구조를 가지고 있으며 대표적인 게 vector이다. 즉 list도 순서를 유지하고 있는 구조를 가진 컨테이너이다. 그렇기에 vector와 같이 pop_back, push_back 등을 쓸 수 있고 생성하는 방법도 비슷하지만 vector와 같았다면 굳이 list를 만들 필요가 없었겠지 않은가? 오늘은 한번 list의 특징에 대해서 알아보도록 하자

 

노드

list는 노드를 기반으로 데이터를 저장한다 이 노드에는 자신의 데이터 값과 다음 원소(자신의 앞과 뒤)를 가리키는 포인터가 같이 들어가게된다. 각 노드는 자신의 전, 후 노드의 주소를 갖고 있기에 중간에 값을 삽입, 제거는 물론 탐색에서도 매우 유리해지게 된다.

 

이중 연결 리스트

list는 이중 연결 리스트로 구성되어 있다. 앞서 우리는 노드는 데이터 값과 전 후의 위치를 가리키는 포인터가 포함되어 있고 list는 그러한 노드를 기반으로 데이터를 저장한다고 하였다. 즉 앞과 뒤 이중으로 노드들끼리 연결되어 있기에 이중 연결 리스트라 부를 수 있는 것이다. 이중 연결 리스트는 앞서 말했듯 탐색, 삽입, 제거에서 확실한 이점을 갖긴 하지만 임의 접근 연산이 불가능하기에 삽입할 위치를 모른다면 선형 탐색을 통해서 삽입할 위치를 찾아주어야 하며 vector와 비교했을 때 시간 복잡도는 크게 다르지 않게 된다. 또한 연속된 메모리를 통해서 데이터를 저장하는 vector와 다르게 list는 서로 떨어진 메모리를 포인터를 통해서 이은 것이기 때문에 메모리가 불연속적이라는 특징을 갖게 된다.