Array và List bên trong

Ở khoá C# Core, array có số ô cố định, còn List<T> thêm bao nhiêu cũng được. Bên trong List<T> vẫn là một array. Hiểu cách nó nới rộng, bạn sẽ biết thao tác nào nhanh, thao tác nào chậm.

Khái niệm

Như bài Array và List của khoá C# Core, array xếp các phần tử vào những ô nằm liền nhau trong bộ nhớ. Nhờ vậy lấy theo vị trí chỉ mất O(1), nhưng số ô cố định từ lúc tạo.

📏 Capacity: số ô của array bên trong List<T>, luôn lớn hơn hoặc bằng Count là số phần tử đang dùng.

Khi array bên trong đầy, List<T> tạo array mới gấp đôi, chép hết phần tử sang, rồi bỏ array cũ.

Ví dụ

Một bản List tối giản, chỉ chứa string:

var cart = new MiniList();
cart.Add("Bút bi");
cart.Add("Vở");
cart.Add("Thước");
Console.WriteLine(cart.Count);      // 3
Console.WriteLine(cart.Capacity);   // 4

class MiniList
{
    private string[] _items = new string[2];

    public int Count { get; private set; }
    public int Capacity => _items.Length;

    public void Add(string item)
    {
        if (Count == _items.Length)
        {
            string[] bigger =
                new string[_items.Length * 2];
            for (int i = 0; i < Count; i++)
            {
                bigger[i] = _items[i];
            }
            _items = bigger;
        }
        _items[Count] = item;
        Count++;
    }
}

• new string[2] tạo array 2 ô trống. Count đếm số ô đã dùng.
• Capacity => _items.Length là property chỉ đọc, viết gọn bằng =>.
• Thêm "Thước" khi 2 ô đã đầy: tạo array 4 ô, chép 2 phần tử cũ sang, rồi mới thêm.
• Chép là O(n), nhưng mỗi lần nới đều gấp đôi nên việc chép hiếm khi xảy ra. Tính trung bình, Add vẫn là O(1).

Insert(i, x) chèn x vào vị trí i, RemoveAt(i) xoá phần tử ở vị trí i, IndexOf(x) trả về vị trí của x.

Mô phỏng chạy List<T> thật, tạo với capacity 2. Array cũng nới gấp đôi như MiniList.

var cart = new List<string>(2);
cart.Add("Bút bi");
cart.Add("Vở");
cart.Add("Thước");
cart.Insert(0, "Thẻ");
cart.RemoveAt(1);
Console.WriteLine(cart[2]);

Thử ngay

Xem List<T> thật của .NET nới rộng thế nào:

var list = new List<string>();
Console.WriteLine(list.Capacity);
for (int i = 1; i <= 9; i++)
{
    list.Add("SP" + i);
    Console.Write(list.Capacity + " ");
}

Đoán trước khi chạy: list mới tạo có capacity bao nhiêu, và capacity thay đổi ở những lần Add nào?

0
4 4 4 4 8 8 8 8 16

Lỗi hay gặp

Lấy dần phần tử đầu bằng RemoveAt(0). Mỗi lần xoá phần tử đầu, cả list dời lên một ô. Lấy hết list theo cách này là O(n²).

// SAI — mỗi RemoveAt(0) dời hết phần còn lại
List<string> orders = new List<string>
{
    "DH1", "DH2", "DH3"
};
while (orders.Count > 0)
{
    Console.WriteLine(orders[0]);
    orders.RemoveAt(0);
}

// ĐÚNG — duyệt từ đầu tới cuối, không xoá
List<string> orders = new List<string>
{
    "DH1", "DH2", "DH3"
};
foreach (string order in orders)
{
    Console.WriteLine(order);
}

Cần vừa lấy ra ở đầu vừa thêm vào ở cuối thì dùng Queue<T> của bài Queue.

Tóm tắt

• List<T> bên trong là array, đầy thì tạo array gấp đôi rồi chép sang.
• Lấy theo vị trí và Add vào cuối là O(1).
• Chèn hoặc xoá ở đầu là O(n), vì phải dời các phần tử phía sau.
• Count là số phần tử đang dùng, Capacity là số ô đã cấp.