List trong C#: Add, Remove, Contains, Find và Sort

List<T> là một collection có thứ tự, tự co giãn khi bạn thêm và xóa phần tử. Nó nằm trong System.Collections.Generic, truy cập theo chỉ số giống mảng (list[0]), và là lựa chọn mặc định cho "một nhóm thứ gì đó" trong C#.

Tạo list và thêm phần tử

Tham số kiểu trong dấu ngoặc nhọn cho biết list chứa gì: List<string>, List<int>, List<Order>.

using System;
using System.Collections.Generic;

class Program
{
    static void Main()
    {
        var cart = new List<string>();
        cart.Add("apples");
        cart.Add("bread");

        var names = new List<string> { "Ana", "Ben" };  // collection initializer
        names.Insert(0, "Zoe");                         // at position 0
        names.AddRange(new[] { "Chloe", "Dev" });        // several at once

        var fromArray = new List<int>(new[] { 3, 1, 2 });

        Console.WriteLine(cart.Count);
        Console.WriteLine(string.Join(", ", names));
        Console.WriteLine(names[1]);
        names[1] = "Ana B.";                             // replace by index
        Console.WriteLine(names[1]);
        Console.WriteLine(fromArray.Count);
    }
}

Đầu ra:

2
Zoe, Ana, Ben, Chloe, Dev
Ana
Ana B.
3

Count là thuộc tính, không phải phương thức (mảng dùng Length, LINQ có phương thức Count(); với list hãy dùng thuộc tính). Insert đẩy mọi phần tử phía sau lùi một vị trí, nên chèn vào đầu một list lớn tốn thời gian tỷ lệ với kích thước list. Add vào cuối mới là thao tác rẻ.

Xóa phần tử

Có bốn cách xóa, tùy theo điều bạn biết về phần tử:

using System;
using System.Collections.Generic;

class Program
{
    static void Main()
    {
        var scores = new List<int> { 40, 85, 62, 40, 91, 55 };

        bool removed = scores.Remove(40);          // first 40 only
        Console.WriteLine(removed + ": " + string.Join(", ", scores));

        Console.WriteLine(scores.Remove(100));     // not found, nothing happens

        scores.RemoveAt(0);                        // by index
        Console.WriteLine(string.Join(", ", scores));

        int count = scores.RemoveAll(s => s < 60); // every match
        Console.WriteLine(count + " removed: " + string.Join(", ", scores));

        try
        {
            scores.RemoveAt(10);
        }
        catch (ArgumentOutOfRangeException e)
        {
            Console.WriteLine("Caught " + e.GetType().Name);
        }

        scores.Clear();
        Console.WriteLine(scores.Count);
    }
}

Đầu ra:

True: 85, 62, 40, 91, 55
False
62, 40, 91, 55
2 removed: 62, 91
Caught ArgumentOutOfRangeException
0

Remove nhận một giá trị và chỉ xóa phần tử khớp đầu tiên. Để xóa mọi bản sao của một giá trị, dùng RemoveAll(s => s == 40). Chỉ số không hợp lệ trên list sẽ ném ArgumentOutOfRangeException (còn mảng ném IndexOutOfRangeException), cả với list[i] lẫn RemoveAt(i). RemoveRange(index, count) xóa một khối liên tiếp.

Count và Capacity

List giữ các phần tử trong một mảng bên trong. Capacity là kích thước của mảng đó; Count là số ô đã dùng. Khi Count chạm Capacity, lần Add tiếp theo sẽ cấp phát một mảng lớn gấp đôi và sao chép mọi thứ sang.

using System;
using System.Collections.Generic;

class Program
{
    static void Main()
    {
        var list = new List<int>();
        Console.WriteLine("Count " + list.Count + ", Capacity " + list.Capacity);

        for (int i = 1; i <= 9; i++)
        {
            list.Add(i);
            Console.WriteLine("Count " + list.Count + ", Capacity " + list.Capacity);
        }

        var sized = new List<int>(1000); // preallocate when you know the size
        Console.WriteLine("Count " + sized.Count + ", Capacity " + sized.Capacity);
    }
}

Đầu ra:

Count 0, Capacity 0
Count 1, Capacity 4
Count 2, Capacity 4
Count 3, Capacity 4
Count 4, Capacity 4
Count 5, Capacity 8
Count 6, Capacity 8
Count 7, Capacity 8
Count 8, Capacity 8
Count 9, Capacity 16
Count 0, Capacity 1000

Nhờ nhân đôi, hầu hết lời gọi Add chỉ là ghi vào một ô trống. Nếu bạn biết đại khái sẽ có bao nhiêu phần tử, hãy truyền con số đó cho hàm khởi tạo để bỏ qua các lần sao chép trung gian. Lưu ý new List<int>(1000) vẫn có Count bằng 0: gọi list[0] trên nó sẽ ném ngoại lệ. Capacity là chỗ trống, không phải phần tử.

Tìm kiếm: Contains, IndexOf, Find, Exists

using System;
using System.Collections.Generic;

class Product
{
    public string Name;
    public decimal Price;
    public Product(string name, decimal price) { Name = name; Price = price; }
}

class Program
{
    static void Main()
    {
        var tags = new List<string> { "new", "sale", "gift" };
        Console.WriteLine(tags.Contains("sale"));
        Console.WriteLine(tags.IndexOf("gift"));
        Console.WriteLine(tags.IndexOf("used"));

        var products = new List<Product>
        {
            new Product("Mug", 8.50m),
            new Product("Lamp", 32.00m),
            new Product("Pen", 1.20m),
        };

        Product lamp = products.Find(p => p.Name == "Lamp");
        Console.WriteLine(lamp.Price);

        List<Product> cheap = products.FindAll(p => p.Price < 10m);
        Console.WriteLine(cheap.Count + " cheap items");

        Console.WriteLine(products.Exists(p => p.Price > 100m));
        Console.WriteLine(products.FindIndex(p => p.Name == "Pen"));

        Product missing = products.Find(p => p.Name == "Desk");
        Console.WriteLine(missing == null);

        // Contains compares references for a class without Equals:
        Console.WriteLine(products.Contains(new Product("Mug", 8.50m)));
    }
}

Đầu ra:

True
2
-1
32.00
2 cheap items
False
2
True
False

Find trả về phần tử khớp đầu tiên, hoặc giá trị mặc định của kiểu (null với lớp) khi không có gì khớp, nên hãy kiểm tra trước khi dùng kết quả. Dòng cuối in False vì Contains dùng Equals, và một lớp không ghi đè Equals sẽ so sánh tham chiếu: một Product mới có cùng các trường vẫn là một đối tượng khác. Hãy tìm theo thuộc tính bằng Exists hoặc Find, hoặc ghi đè Equals và GetHashCode trong lớp.

Mọi phương thức này đều duyệt list từ đầu, nên mỗi lần gọi là O(n). Với việc tra cứu lặp lại theo khóa, Dictionary trả lời trong thời gian hằng số.

Sắp xếp list

Sort() sắp xếp tại chỗ theo thứ tự tự nhiên của phần tử. Truyền một lambda so sánh để sắp xếp theo bất cứ tiêu chí nào khác.

using System;
using System.Collections.Generic;
using System.Linq;

class Player
{
    public string Name;
    public int Score;
    public Player(string name, int score) { Name = name; Score = score; }
    public override string ToString() { return Name + " " + Score; }
}

class Program
{
    static void Main()
    {
        var numbers = new List<int> { 5, 2, 9, 1 };
        numbers.Sort();
        Console.WriteLine(string.Join(", ", numbers));

        numbers.Sort((a, b) => b.CompareTo(a)); // descending
        Console.WriteLine(string.Join(", ", numbers));

        var players = new List<Player>
        {
            new Player("Ana", 120),
            new Player("Ben", 95),
            new Player("Chloe", 150),
        };

        players.Sort((a, b) => a.Score.CompareTo(b.Score)); // by property
        Console.WriteLine(string.Join(", ", players));

        List<Player> byName = players.OrderByDescending(p => p.Name).ToList(); // new list
        Console.WriteLine(string.Join(", ", byName));
        Console.WriteLine(string.Join(", ", players)); // unchanged by OrderBy
    }
}

Đầu ra:

1, 2, 5, 9
9, 5, 2, 1
Ben 95, Ana 120, Chloe 150
Chloe 150, Ben 95, Ana 120
Ben 95, Ana 120, Chloe 150

Phép so sánh trả về số âm khi a nên đứng trước, số dương khi b nên đứng trước, và 0 khi hai bên bằng nhau; CompareTo cho ra đúng như vậy. Có hai khác biệt giữa Sort và OrderBy của LINQ đáng chú ý trong thực tế:

• Sort thay đổi list; OrderBy trả về một chuỗi mới và giữ nguyên list.
• Sort không ổn định: các phần tử so sánh bằng nhau có thể đổi chỗ. OrderBy ổn định, và ThenBy thêm khóa thứ hai: players.OrderBy(p => p.Score).ThenBy(p => p.Name).

Gọi Sort() trên list chứa lớp của bạn mà không truyền phép so sánh sẽ ném InvalidOperationException, vì list không biết cách sắp thứ tự các phần tử. Hãy truyền phép so sánh hoặc cài đặt IComparable<T> cho lớp.

Reverse() đảo ngược tại chỗ. Vì System.Linq cũng định nghĩa extension Reverse, nên list.Reverse() trên một List<T> sẽ chọn phiên bản tại chỗ, phiên bản này không trả về gì.

Duyệt list, và xóa trong lúc duyệt

foreach đọc từng phần tử theo thứ tự. Vòng lặp for cho bạn thêm cả chỉ số. Điều bạn không thể làm là thêm hoặc xóa phần tử giữa chừng một foreach trên chính list đó:

using System;
using System.Collections.Generic;

class Program
{
    static void Main()
    {
        var orders = new List<int> { 120, 15, 80, 5, 60 };

        try
        {
            foreach (int total in orders)
            {
                if (total < 20) orders.Remove(total);
            }
        }
        catch (InvalidOperationException e)
        {
            Console.WriteLine("Caught " + e.GetType().Name);
        }

        orders = new List<int> { 120, 15, 80, 5, 60 };

        // Fix 1: RemoveAll
        var a = new List<int>(orders);
        a.RemoveAll(t => t < 20);
        Console.WriteLine(string.Join(", ", a));

        // Fix 2: loop backwards, so removals do not shift items you have not seen
        var b = new List<int>(orders);
        for (int i = b.Count - 1; i >= 0; i--)
        {
            if (b[i] < 20) b.RemoveAt(i);
        }
        Console.WriteLine(string.Join(", ", b));
    }
}

Đầu ra:

Caught InvalidOperationException
120, 80, 60
120, 80, 60

Ngoại lệ là InvalidOperationException với thông báo "Collection was modified; enumeration operation may not execute." Vòng lặp for duyệt xuôi không ném lỗi, nhưng âm thầm bỏ qua phần tử ngay sau mỗi phần tử bạn xóa, vì mọi thứ bị dồn xuống một chỉ số. Duyệt ngược sẽ tránh được điều đó. Cách thứ ba là duyệt trên một bản sao: foreach (var t in orders.ToList()).

Thay đổi thuộc tính của một phần tử bên trong foreach (chẳng hạn order.Status = "sent") thì không sao. Thêm hoặc xóa phần tử làm hỏng enumerator, và thay một phần tử qua indexer (orders[i] = 0) cũng vậy.

Chuyển đổi giữa list và mảng

using System;
using System.Collections.Generic;
using System.Linq;

class Program
{
    static void Main()
    {
        string[] cities = { "Oslo", "Lima", "Pune" };

        List<string> list = cities.ToList();       // or new List<string>(cities)
        list.Add("Kyiv");

        string[] back = list.ToArray();
        Console.WriteLine(back.Length);
        Console.WriteLine(cities.Length);           // the original array is unchanged

        List<int> lengths = list.ConvertAll(c => c.Length);
        Console.WriteLine(string.Join(", ", lengths));
        Console.WriteLine(string.Join(" / ", list));
    }
}

Đầu ra:

4
3
4, 4, 4, 4
Oslo / Lima / Pune / Kyiv

Cả hai chiều đều sao chép phần tử sang vùng lưu trữ mới, nên thay đổi list về sau không ảnh hưởng đến mảng. ConvertAll là phiên bản riêng của list cho Select(...).ToList() trong LINQ. In một list bằng Console.WriteLine(list) chỉ hiện tên kiểu (System.Collections.Generic.List`1[System.String]); hãy dùng string.Join.

Tra cứu nhanh

Lỗi thường gặp

• Xóa bên trong foreach. Ném InvalidOperationException; hãy dùng RemoveAll hoặc vòng lặp for duyệt ngược.
• Tưởng Remove(x) xóa mọi bản sao. Nó chỉ xóa bản đầu tiên; hãy dùng RemoveAll.
• Dùng Contains với đối tượng không có Equals. Nó so sánh tham chiếu; hãy tìm theo thuộc tính bằng Exists.
• Truy cập theo chỉ số vào list vừa tạo với capacity. new List<int>(10) là list rỗng; hãy thêm phần tử trước.
• Tưởng Sort giữ thứ tự các phần tử bằng nhau. Không phải vậy; dùng OrderBy khi thứ tự giữa các phần tử bằng nhau quan trọng.
• Gán list để dùng chung rồi bất ngờ vì nó thay đổi. var copy = list; vẫn là cùng một list; new List<T>(list) mới là bản sao.