List<T>와 LinkedList<T> 의 차이점(ps. 트리 구조)

List<T>와 LinkedList<T>의 주요 차이점

내부 구조	동적 배열 (연속된 메모리 할당)	이중 연결 리스트 (노드 기반)
메모리 사용	연속된 메모리 블록 사용 (낭비 적음)	추가적인 포인터 메모리 필요
접근 속도	O(1) (인덱스를 통한 빠른 접근)	O(n) (순차 검색 필요)
삽입/삭제 속도	O(n) (중간 삽입/삭제 시 이동 필요)	O(1) (노드 추가/삭제)
인덱스 접근	가능 (배열처럼 [index])	불가능 (순차 탐색 필요)
순차 접근	빠름 (연속된 메모리로 캐시 효율적)	느림 (노드를 따라가야 함)
적합한 상황	조회와 인덱스 기반 작업이 많은 경우	빈번한 삽입/삭제 작업이 많은 경우

 

이는 C#의 List<T>는 C++의 std::vector와, C#의 LinkedList<T>는 C++의 std::list와 유사한 구조와 동작 방식을 가지기 때문이다.

 

따라서 빈번한 삽입/삭제가 있을 경우엔 LinkedList<T>를, 검색을 많이 할 경우엔 List<T>를 사용하면 된다.

 

 

 

ps. 이진 트리 구조에 대하여

- C#에는 이진 트리가 존재하지 않는다. 하지만 관련 자료구조를 직접 만들어 사용하거나 비슷한 자료구조가 존재한다.

 

[ 트리형식으로 관리되는 자료구조 ]

- C#의 SortedDictionary<TKey, TValue>는 내부적으로 레드-블랙 트리(Red-Black Tree) 를 사용하여 키-값 쌍을 정렬된 상태로 유지한다.

- SortedSet<T>는 중복을 허용하지 않으며, 균형 이진 탐색 트리(Balanced Binary Search Tree) 기반으로 요소를 자동 정렬하고 관리한다.

 

레드-블랙 트리(RBT)와 균형 이진 탐색 트리(BBST)는 모두 트리의 균형을 유지하는 알고리즘(밸런싱)을 적용하여 삽입, 삭제, 검색 연산에서 균일한 성능을 보장한다.