Intrusive Linked List vs Extrusive Linked List

Intrusive Linked List

- 원소 자체가 노드의 역할을 겸한다. 아래 이미지처럼 원소가 되는 구조체 타입 자체가 다음 노드에 대한 포인터를 멤버로 가지고 있다.

- Extrusive Linked List보다 추가/삭제에 성능적 이점이 있다.

https://www.data-structures-in-practice.com/intrusive-linked-lists/

- 언리얼 엔진에서는 TIntrusiveLinkedList, TIntrusiveDoubleLinkedList로 구현되어 있다. TIntrusiveLinkedList를 상속받은 구조체/클래스를 작성하여 사용할 수 있다. TIntrusiveDoubleLinkedList는 TIntrusiveDoubleLinkedListNode를 상속받은 구조체/클래스 작성 후, TIntrusiveDoubleLinkedList<FMyClass> List; 처럼 선언하여 사용한다. TInstrusiveLinkedList는 FOpenGLView, FMetalResourceViewBase 등에서 사용되고 있다.

Extrusive Linked List

- 원소 외부에 이전/다음 노드에 대한 포인터를 저장하는 방식이다. Instrusive Linked List와 달리 데이터 구조를 변경하지 않고, TLinkedList<FMyClass> List; 와 같이 바로 사용할 수 있다.

- Intrusive Linked List보다 사용이 편리하고 별도 구조체/클래스를 정의하지 않아도 되는 장점이 있으나, 원소를 감싸는 노드에 대한 추가 메모리를 할당해야 하고, 다음 노드에 대한 포인터가 원소가 위치한 메모리 영역과 떨어져 있는 노드 메모리 영역에 존재하므로 캐시 지역성이 떨어진다.