Lista w C#: Add, Remove, Contains, Find i Sort

List<T> to uporządkowana kolekcja, która rośnie i maleje w miarę dodawania i usuwania elementów. Znajduje się w System.Collections.Generic, indeksuje się ją jak tablicę (list[0]) i jest domyślnym wyborem w C#, gdy potrzebujesz "zbioru rzeczy".

Tworzenie listy i dodawanie elementów

Parametr typu w nawiasach ostrych mówi, co przechowuje lista: 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);
    }
}

Wynik:

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

Count to właściwość, a nie metoda (tablice używają Length, LINQ ma metodę Count(); na liście używaj właściwości). Insert przesuwa każdy dalszy element o jedno miejsce, więc wstawianie na początek dużej listy zajmuje czas proporcjonalny do jej rozmiaru. Add na końcu to tania operacja.

Usuwanie elementów

Są cztery sposoby usuwania, zależnie od tego, co wiesz o elemencie:

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);
    }
}

Wynik:

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

Remove przyjmuje wartość i usuwa tylko pierwsze dopasowanie. Aby usunąć wszystkie kopie wartości, użyj RemoveAll(s => s == 40). Zły indeks na liście rzuca ArgumentOutOfRangeException (tablica rzuca zamiast tego IndexOutOfRangeException), zarówno dla list[i], jak i dla RemoveAt(i). RemoveRange(index, count) usuwa cały blok.

Count a Capacity

Lista trzyma elementy w wewnętrznej tablicy. Capacity to rozmiar tej tablicy; Count to liczba zajętych miejsc. Gdy Count osiągnie Capacity, następne Add alokuje tablicę dwa razy większą i kopiuje do niej wszystko.

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);
    }
}

Wynik:

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

Podwajanie sprawia, że większość wywołań Add to tylko zapis do wolnego miejsca. Jeśli wiesz mniej więcej, ile elementów przybędzie, przekaż tę liczbę do konstruktora, aby pominąć pośrednie kopiowania. Pamiętaj, że new List<int>(1000) nadal ma Count równe 0: list[0] na takiej liście rzuca wyjątek. Pojemność to miejsce, a nie elementy.

Wyszukiwanie: 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)));
    }
}

Wynik:

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

Find zwraca pierwsze dopasowanie albo wartość domyślną typu (null dla klasy), gdy nic nie pasuje, więc sprawdź wynik przed użyciem. Ostatnia linia wypisuje False, bo Contains używa Equals, a klasa bez nadpisanego Equals porównuje referencje: nowy Product z tymi samymi polami to inny obiekt. Zamiast tego szukaj według właściwości przez Exists albo Find albo nadpisz w klasie Equals i GetHashCode.

Każda z tych metod przechodzi listę od początku, więc każde wywołanie to O(n). Przy wielokrotnym wyszukiwaniu według klucza Dictionary odpowiada w stałym czasie.

Sortowanie listy

Sort() sortuje w miejscu według naturalnego porządku elementów. Przekaż lambdę porównującą, aby sortować według czegokolwiek innego.

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
    }
}

Wynik:

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

Porównanie zwraca liczbę ujemną, gdy a powinno być pierwsze, dodatnią, gdy b, i zero przy remisie; dokładnie to daje CompareTo. W praktyce liczą się dwie różnice między Sort a OrderBy z LINQ:

• Sort zmienia listę; OrderBy zwraca nową sekwencję i zostawia listę w spokoju.
• Sort nie jest stabilne: elementy równe w porównaniu mogą zamienić się miejscami. OrderBy jest stabilne, a ThenBy dodaje drugi klucz: players.OrderBy(p => p.Score).ThenBy(p => p.Name).

Wywołanie Sort() bez porównania na liście obiektów twojej własnej klasy rzuca InvalidOperationException, bo lista nie wie, jak uporządkować elementy. Przekaż porównanie albo zaimplementuj w klasie IComparable<T>.

Reverse() odwraca kolejność w miejscu. Ponieważ System.Linq też definiuje rozszerzenie Reverse, list.Reverse() na List<T> wybiera wersję działającą w miejscu, która nic nie zwraca.

Pętle i usuwanie w trakcie iteracji

foreach odczytuje każdy element po kolei. Pętla for daje też indeks. Nie można natomiast dodawać ani usuwać elementów w trakcie foreach po tej samej liście:

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));
    }
}

Wynik:

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

Wyjątek to InvalidOperationException z komunikatem "Collection was modified; enumeration operation may not execute." Pętla for idąca do przodu nie rzuca wyjątku, ale po cichu pomija element tuż za każdym usuniętym, bo wszystko przesuwa się o jeden indeks w dół. Pętla od tyłu tego unika. Trzecie rozwiązanie to iterowanie po kopii: foreach (var t in orders.ToList()).

Zmiana właściwości elementu wewnątrz foreach (na przykład order.Status = "sent") jest w porządku. Dodawanie lub usuwanie elementów psuje enumerator, podobnie jak zastąpienie elementu przez indekser (orders[i] = 0).

Konwersja między listami a tablicami

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));
    }
}

Wynik:

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

W obu kierunkach elementy są kopiowane do nowego miejsca w pamięci, więc późniejsza zmiana listy nie wpływa na tablicę. ConvertAll to własna wersja listy odpowiadająca Select(...).ToList() z LINQ. Wypisanie listy przez Console.WriteLine(list) pokazuje nazwę typu (System.Collections.Generic.List`1[System.String]); użyj string.Join.

Ściągawka

Typowe błędy

• Usuwanie wewnątrz foreach. Rzuca InvalidOperationException; użyj RemoveAll albo pętli for od tyłu.
• Oczekiwanie, że Remove(x) usunie każdą kopię. Usuwa pierwszą; użyj RemoveAll.
• Używanie Contains na obiektach bez Equals. Porównuje referencje; szukaj według właściwości przez Exists.
• Indeksowanie listy utworzonej z pojemnością. new List<int>(10) jest pusta; najpierw dodaj elementy.
• Założenie, że Sort zachowuje kolejność remisów. Nie zachowuje; użyj OrderBy, gdy kolejność równych elementów ma znaczenie.
• Przypisanie listy, żeby ją współdzielić, a potem zaskoczenie zmianami. var copy = list; to ta sama lista; new List<T>(list) to kopia.