Danh sách cấu trúc dữ liệu C# Efficiency

Question

tại thời điểm tôi đang sử dụng List<short> làm bộ đệm để giữ mọi thứ trong khi tính toán được thực hiện cho từng giá trị dựa trên các giá trị khác tiếp tục xuống bộ đệm. Sau đó tôi nhận ra rằng điều này có lẽ không hiệu quả như tôi đã nói rằng List<> là một danh sách liên kết vì vậy mỗi khi tôi làm whatever = myList[100]; điều xấu là phải nhảy xuống tất cả các nút khác trước tiên để có được giá trị tôi muốn. Tôi không muốn sử dụng một Mảng thông thường vì tôi đã tải được Add() và Remove() s đá xung quanh ở những nơi khác trong mã. Vì vậy, tôi cần một lớp kế thừa IList<T> nhưng sử dụng cấu trúc dữ liệu mảng thông thường. Có ai biết một lớp trong. Net hoạt động theo cách này vì vậy tôi không phải viết của riêng tôi? Tôi đã thử sử dụng ArrayList nhưng nó 'aint chung chung!

Answer 1

Không, List<T> là bộ sưu tập chung, không phải danh sách được liên kết. Nếu bạn cần thêm và xóa chức năng thì List<T> là việc thực hiện hầu hết mọi người mặc định.

Answer 2

List<T> không sử dụng triển khai danh sách được liên kết. Bên trong nó sử dụng một mảng, do đó, nó xuất hiện để được chính xác những gì bạn cần. Lưu ý rằng, bởi vì nó là một mảng, loại bỏ/chèn có thể là một hoạt động tốn kém tùy thuộc vào kích thước của danh sách và mục vị trí được gỡ bỏ/chèn vào - O (n). Mặc dù không biết nhiều hơn về cách bạn đang sử dụng nó, tuy nhiên, thật khó để đề xuất một cấu trúc dữ liệu tốt hơn.

Trích dẫn từ phần Nhận xét của docs.

Danh sách (T) là lớp tương đương chung với lớp ArrayList. Nó thực hiện giao diện chung IList (T) sử dụng một mảng có kích thước được tăng động theo yêu cầu.

Answer 3

List<T> được hỗ trợ bởi một mảng chứ không phải danh sách được liên kết. Các truy cập được lập chỉ mục của List<T> xảy ra trong thời gian không đổi.

Answer 4

Ngoài câu trả lời chính xác của tvanfosson, nếu bạn không chắc chắn về cách thức hoạt động của nội bộ, chỉ cần tải lên .NET Reflector và bạn có thể thấy chính xác cách mọi thứ được triển khai. Trong trường hợp này, khoan xuống indexer của List<T> cho chúng ta thấy đoạn mã sau:

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

nơi bạn có thể thấy rằng this._items[index] là một mảng của các loại generic T.