목록 데이터 구조 C# 효율성

Question

현재로서는 List<short>을 버퍼로 사용하여 잠시 동안 버퍼를 유지하면서 버퍼의 다른 값을 기반으로 각 값을 계산합니다. 나는 그때 내가 아마도 whatever = myList[100];을 할 때마다 List<>이 연결된리스트라는 말을 들었을 때 이것이 매우 효과적이지 않다는 것을 깨달았습니다. 불쌍한 점은 내가 원하는 값으로 가기 위해 다른 모든 노드를 먼저 뛰어 넘어야한다는 것입니다. 나는 Add()과 Remove()의 부하를 코드의 다른 위치에서 사용하고 있기 때문에 일반 배열을 사용하고 싶지 않습니다. 따라서 IList<T>을 상속하지만 일반 배열 데이터 구조를 사용하는 클래스가 필요합니다. 누구든지 이런 식으로 작동합니다 .net 내 클래스를 알고 그래서 내 자신을 작성하지 않아도됩니까? 나는 ArrayList를 사용하여 시도했지만 그것은 일반적이지 않다!

Answer 1

아니요, List<T>은 연결 목록이 아닌 일반 모음입니다. 기능을 추가 및 제거해야하는 경우 대부분 List<T> 구현이 기본값입니다.

Answer 2

List<T>은 연결된 목록 구현을 사용하지 않습니다. 내부적으로는 배열을 사용하기 때문에 필요로하는 것과 정확히 일치합니다. 배열이기 때문에 목록의 크기와 제거/삽입되는 위치 항목 (O (n))에 따라 Remove/insert가 값 비싼 연산이 될 수 있습니다. 그러나 어떻게 사용하고 있는지에 대해 알지 못하면 더 나은 데이터 구조를 추천하기가 어렵습니다.

docs의 비고 섹션에서 인용하십시오.

List (T) 클래스는 ArrayList 클래스의 일반적인 기능입니다. 그것은 필요에 따라 동적으로 크기가 증가하는 배열을 사용하여 IList (T) 제네릭 인터페이스를 구현합니다.

Answer 3

List<T>은 연결된 목록이 아닌 배열로 지원됩니다. List<T>의 인덱싱 된 액세스는 일정한 시간 내에 발생합니다.

Answer 4

tvanfosson의 정답뿐 아니라 무언가가 내부적으로 어떻게 작동하는지 잘 모르는 경우 .NET Reflector을로드하면 정확하게 구현 된 것을 볼 수 있습니다. 당신이 this._items[index]은 제네릭 형식 T의 배열입니다 것을 볼 수 있습니다

public T this[int index] 
{ 
    get 
    { 
     if (index >= this._size) 
     { 
      ThrowHelper.ThrowArgumentOutOfRangeException(); 
     } 
     return this._items[index]; 
    } 
    // ... 

이 경우, List<T>의 인덱서 드릴 다운하는 것은 우리에게 다음과 같은 코드를 보여줍니다.