C# List<T> Rehberi: Ekleme, Silme, Capacity, Sıralama ve Arama

Sürüm notu: Bu yazıdaki kodlar C# 10 ve .NET 6 API'leriyle yazılmıştır; .NET 10 SDK ile derlenip denenmiştir.

Önce Tahmin Et

Katalog sayfasında stokta olmayan kitapları göstermek istemiyoruz. Listeyi baştan sona dolaşıp stoğu sıfır olanları siliyoruz. Bu kod ekrana ne yazar?

List<Book> books = new()
{
    new("978-0441172719", "Dune", 12.99m, Stock: 4),
    new("978-0553293357", "Foundation", 9.50m, Stock: 0),
    new("978-0261102217", "The Hobbit", 10.99m, Stock: 0),
    new("978-0451524935", "1984", 8.99m, Stock: 7),
};

for (int i = 0; i < books.Count; i++)
{
    if (books[i].Stock == 0)
    {
        books.RemoveAt(i);
    }
}

Console.WriteLine(string.Join(", ", books.Select(b => b.Title)));

record Book(string Isbn, string Title, decimal Price, int Stock);

Index Kayınca Element Atlanır

Çıktı Dune, The Hobbit, 1984. Stoğu sıfır olan The Hobbit listede kaldı. Döngü i = 1'de Foundation'ı siler. Silme işlemi arkadaki bütün element'leri birer adım öne kaydırır; The Hobbit artık 1 numaralı index'te durur. Döngü ise i++ ile 2'ye geçer ve 2 numarada artık 1984 vardır. The Hobbit'e hiç bakılmadı.

Sinema salonunda sıra sıra bilet kontrol ettiğini düşün. 5 numaralı koltuktaki kişiyi dışarı çıkardığın anda herkes bir koltuk kayıyorsa, 6'ya geçtiğinde aslında 7'deki kişiye bakarsın. Aradaki kişi kontrolden kaçar.

Aynı işi foreach ile yapmayı denersen List<T> seni daha sert durdurur. Döngünün içinde books.Remove(book) çağırdığında şu exception gelir:

Unhandled exception. System.InvalidOperationException: Collection was modified; enumeration operation may not execute.

List<T> içinde bir sürüm sayacı tutar ve her değişiklikte onu artırır. Enumerator her adımda sayacın değişip değişmediğine bakar; değiştiyse devam etmeyi reddeder. Sessizce yanlış sonuç üretmektense yüksek sesle patlamak daha iyidir. İki doğru yol var:

// books: yazının başındaki dört kitaplık liste
List<Book> copy = new(books);

int removed = books.RemoveAll(b => b.Stock == 0);
Console.WriteLine($"RemoveAll: {removed} removed, left: {string.Join(", ", books.Select(b => b.Title))}");

for (int i = copy.Count - 1; i >= 0; i--) // sondan başa: kayma, bakılmış kısımda olur
{
    if (copy[i].Stock == 0)
    {
        copy.RemoveAt(i);
    }
}
Console.WriteLine($"Backwards: {string.Join(", ", copy.Select(b => b.Title))}");

RemoveAll: 2 removed, left: Dune, 1984
Backwards: Dune, 1984

RemoveAll hem okunaklı hem de hızlı. Listeyi tek geçişte dolaşır, kalan element'leri yerinde sıkıştırır ve kaç element sildiğini döndürür. Sondan başa dolaşmak da doğru sonuç verir, ama her RemoveAt arkadaki element'leri yeniden kaydırdığı için çok silmede RemoveAll'dan yavaştır.

List<T>'nin İçinde Bir Array Var

Bütün bu davranışın sebebi List<T>'nin içinde düz bir T[] tutması. Count içinde kaç element olduğunu, Capacity ise o array'in kaç element alabildiğini söyler. Array dolduğunda liste iki kat büyüklüğünde yeni bir array ayırır ve her şeyi oraya kopyalar:

List<int> orderIds = new();
Console.WriteLine($"Count {orderIds.Count,2} -> Capacity {orderIds.Capacity}");

int lastCapacity = orderIds.Capacity;
for (int id = 1; id <= 20; id++)
{
    orderIds.Add(id);
    if (orderIds.Capacity != lastCapacity)
    {
        Console.WriteLine($"Count {orderIds.Count,2} -> Capacity {orderIds.Capacity}");
        lastCapacity = orderIds.Capacity;
    }
}

orderIds.Clear();
Console.WriteLine($"After Clear: Count {orderIds.Count}, Capacity {orderIds.Capacity}");

orderIds.TrimExcess();
Console.WriteLine($"After TrimExcess: Capacity {orderIds.Capacity}");

List<int> sized = new(1000);
sized.EnsureCapacity(1500);
Console.WriteLine($"Presized: Capacity {sized.Capacity}");

Count  0 -> Capacity 0
Count  1 -> Capacity 4
Count  5 -> Capacity 8
Count  9 -> Capacity 16
Count 17 -> Capacity 32
After Clear: Count 0, Capacity 32
After TrimExcess: Capacity 0
Presized: Capacity 2000

Boş bir liste hiç array ayırmaz. İlk Add'de kapasite 4 olur, sonra her dolduğunda ikiye katlanır. Bu, eşyaların sığmayınca iki kat büyük bir eve taşınmaya benzer. Taşınmak pahalıdır, çünkü bütün eşyalar tek tek yeni eve gider. Ama ev her seferinde ikiye katlandığı için taşınma sayısı çok az kalır. Bir milyon element eklerken yalnızca yirmi civarında taşınma olur. Bu yüzden Add'in maliyeti ortalamada O(1) kabul edilir (amortized O(1)).

Kaç element geleceğini biliyorsan, örneğin veritabanından 1000 satır okuyacaksan, new List<T>(1000) ile kapasiteyi baştan ver ve taşınmaların hepsinden kurtul. .NET 6 ile gelen EnsureCapacity sonradan aynı işi yapar; çıktıda göründüğü gibi, istenen 1500'e değil 2000'e çıktı, çünkü büyürken yine ikiye katlamayı tercih eder. Clear kapasiteyi korur, aynı listeyi tekrar dolduracaksan bu iyi bir şeydir. Belleği gerçekten geri vermek istiyorsan TrimExcess çağırırsın.

Eklemek: Add, AddRange, Insert

List<string> titles = new() { "Dune", "1984" };

titles.Add("Foundation");
titles.AddRange(new[] { "The Hobbit", "Brave New World" });
titles.Insert(0, "Neuromancer");
titles.InsertRange(2, new[] { "Hyperion", "Solaris" });

Console.WriteLine(string.Join(" | ", titles));
Console.WriteLine($"Count: {titles.Count}, [2]: {titles[2]}, last: {titles[^1]}");

titles.Insert(20, "Snow Crash"); // ArgumentOutOfRangeException

Neuromancer | Dune | Hyperion | Solaris | 1984 | Foundation | The Hobbit | Brave New World
Count: 8, [2]: Hyperion, last: Brave New World
Unhandled exception. System.ArgumentOutOfRangeException: Index must be within the bounds of the List. (Parameter 'index')

Add sona ekler ve ucuzdur. AddRange, gelen collection'ın boyunu biliyorsa kapasiteyi tek seferde ayarlar; döngüyle tek tek Add çağırmaktan iyidir. Insert ise araya ekler ve bunun bedeli, ekleme noktasından sonraki her element'in bir adım kaymasıdır: O(n). Listenin başına sürekli ekleme yapıyorsan yanlış collection'ı seçmiş olabilirsin; bu serinin Queue<T> ve LinkedList<T> yazısında alternatiflerini göreceğiz. Son satır da bir hatırlatma: Insert'e en fazla Count verebilirsin, yani sona eklemek serbest ama boşluk bırakmak yasak.

Silmek ve Eşitlik

RemoveAt(index) konuma göre, Remove(item) değere göre siler. RemoveRange(index, count) bir aralığı, Clear() her şeyi siler. Remove'un işi biraz daha incelikli, çünkü "bu element listede var mı" sorusunun cevabı tipin eşitlik tanımına bağlı:

// books: yazının başındaki dört kitaplık liste
bool bookRemoved = books.Remove(new Book("978-0553293357", "Foundation", 9.50m, 0));

List<CartLine> lines = new() { new CartLine("978-0441172719", 2) };
bool lineRemoved = lines.Remove(new CartLine("978-0441172719", 2));

Console.WriteLine($"Book removed: {bookRemoved}, count: {books.Count}");
Console.WriteLine($"Line removed: {lineRemoved}, count: {lines.Count}");

record Book(string Isbn, string Title, decimal Price, int Stock);

class CartLine
{
    public CartLine(string isbn, int quantity)
    {
        Isbn = isbn;
        Quantity = quantity;
    }

    public string Isbn { get; }
    public int Quantity { get; }
}

Book removed: True, count: 3
Line removed: False, count: 1

Remove içeride EqualityComparer<T>.Default kullanır. record, bütün property'leri aynıysa iki instance'ı eşit sayar; bu yüzden yeni oluşturduğumuz Book listedekini buldu. Sıradan bir class ise Equals'ı override etmediği sürece referans karşılaştırır: aynı değerleri taşıyan yeni bir CartLine listedekiyle "aynı" değildir ve Remove sessizce false döndürür. Contains ve IndexOf da aynı kurala uyar. Eşitliği OOP serisindeki eşitlik ve karşılaştırma yazısında derinlemesine anlatıyoruz.

Aramak: Find Ailesi

using System.Globalization;

CultureInfo.CurrentCulture = CultureInfo.InvariantCulture;

// books: yazının başındaki dört kitaplık liste
Book? cheap = books.Find(b => b.Price < 10m);
int hobbitIndex = books.FindIndex(b => b.Title == "The Hobbit");
List<Book> outOfStock = books.FindAll(b => b.Stock == 0);
bool anyExpensive = books.Exists(b => b.Price > 50m);
bool allPriced = books.TrueForAll(b => b.Price > 0m);
Book? missing = books.Find(b => b.Title == "Snow Crash");

Console.WriteLine($"Find: {cheap?.Title}, FindIndex: {hobbitIndex}, FindAll: {outOfStock.Count}");
Console.WriteLine($"Exists: {anyExpensive}, TrueForAll: {allPriced}, missing: {missing?.Title ?? "(null)"}");

List<DateOnly> releaseDates = new() { new(1965, 8, 1), new(1951, 6, 1) };
DateOnly future = releaseDates.Find(d => d.Year > 2030);
Console.WriteLine($"Future release: {future}");

Find: Foundation, FindIndex: 2, FindAll: 2
Exists: False, TrueForAll: True, missing: (null)
Future release: 01/01/0001

Find koşulu sağlayan ilk element'i, FindLast sonuncuyu, FindIndex ilkinin index'ini (bulamazsa -1), FindAll hepsini yeni bir listede döndürür. Exists ve TrueForAll ise LINQ'teki Any ve All'un List<T>'ye özel karşılıkları. Bunlar LINQ'ten önce, .NET Framework 2.0 zamanından kalma method'lar; yeni kodda ikisi de geçerli.

Son satıra dikkat: Find bulamadığında default(T) döndürür. Reference type için bu null'dır ve kontrol etmesi kolaydır. DateOnly gibi bir value type içinse sonuç 1 Ocak 0001 tarihidir ve gerçek bir tarihten ayırt edilemez. Value type listelerde FindIndex kullanıp -1'i kontrol etmek daha güvenli.

Bütün bu method'lar listeyi baştan sona dolaşır: O(n). On element için önemsiz, yüz bin element üzerinde her istekte ISBN ile arama yapıyorsan değil. O ihtiyacın cevabı bir sonraki yazının konusu olan Dictionary ve HashSet.

Sıralamak: Sort ve Comparer

// books: yazının başındaki dört kitaplık liste
try
{
    books.Sort();
}
catch (InvalidOperationException ex)
{
    Console.WriteLine($"{ex.Message} / {ex.InnerException?.Message}");
}

books.Sort((x, y) => x.Price.CompareTo(y.Price));
Console.WriteLine(string.Join(", ", books.Select(b => $"{b.Title} {b.Price}")));

books.Sort((x, y) => string.CompareOrdinal(x.Isbn, y.Isbn));
int index = books.BinarySearch(new Book("978-0451524935", "", 0m, 0), new IsbnComparer());
Console.WriteLine($"BinarySearch: {index} -> {books[index].Title}");

record Book(string Isbn, string Title, decimal Price, int Stock);

class IsbnComparer : IComparer<Book>
{
    public int Compare(Book? x, Book? y) => string.CompareOrdinal(x?.Isbn, y?.Isbn);
}

Failed to compare two elements in the array. / At least one object must implement IComparable.
1984 8.99, Foundation 9.50, The Hobbit 10.99, Dune 12.99
BinarySearch: 2 -> 1984

Parametresiz Sort(), element'lerin kendilerini nasıl karşılaştıracağını bilmesini ister; Book IComparable<Book> implemente etmediği için runtime'da patladı. Lambda alan overload ise karşılaştırmayı dışarıdan verir: negatif "x önce", pozitif "y önce", sıfır "eşit" demek. BinarySearch, sıralı bir listede O(log n) ile arar; ama listenin aynı kurala göre sıralı olması şart. Aynı comparer'ı iki yerde de kullanmak bu yüzden önemli.

Sort'un bir özelliği daha var: stable değildir. Eşit kabul edilen element'lerin birbirine göre sırası korunmaz. 40 kitabı stoğa göre sıraladım; yarısının stoğu 0, yarısının 1, adları da Book00'dan Book39'a gidiyor:

List<Book> books = new();
for (int i = 0; i < 40; i++)
{
    books.Add(new Book($"Book{i:D2}", Stock: i % 2));
}

List<Book> sorted = new(books);
sorted.Sort((x, y) => x.Stock.CompareTo(y.Stock));
List<Book> ordered = books.OrderBy(b => b.Stock).ToList();

Console.WriteLine("Sort:    " + string.Join(" ", sorted.Take(8).Select(b => b.Title)));
Console.WriteLine("OrderBy: " + string.Join(" ", ordered.Take(8).Select(b => b.Title)));

record Book(string Title, int Stock);

Sort:    Book00 Book22 Book28 Book20 Book38 Book18 Book16 Book30
OrderBy: Book00 Book02 Book04 Book06 Book08 Book10 Book12 Book14

Sort stoğu 0 olanları başa topladı ama kendi aralarındaki sırayı karıştırdı. LINQ'in OrderBy'ı ise stable; eşitlerin orijinal sırasını korur. Ekranda önce fiyata, sonra ada göre sıralanmış bir liste göstermek istiyorsan ya karşılaştırmaya ikinci kriteri de koy ya da OrderBy(...).ThenBy(...) kullan. Ayrıca Sort listeyi yerinde değiştirir, OrderBy yeni bir sıra üretir; LINQ serisinde bu farkı ayrıntılı göreceğiz.

Sık Düşülen Tuzaklar

Dolaşırken listeyi değiştirmek. foreach içinde Add ya da Remove çağırmak exception'la, ileri doğru for ile silmek sessizce atlanan element'lerle biter. RemoveAll kullan ya da sondan başa dolaş.

Value type listede Find'ın sonucuna güvenmek. Bulamadığında 0, false ya da 01/01/0001 döner. FindIndex ile -1'i kontrol et.

class element'lerle Remove ve Contains kullanıp eşitlik tanımlamamak. Referans karşılaştırması yapılır ve aynı veriyi taşıyan yeni bir object asla bulunmaz.

Listeyi her istekte arama yapılan bir yapı olarak kullanmak. Sık arama yapılan büyük listelerde Contains ve Find her seferinde baştan sona yürür. Key ile erişim gerekiyorsa Dictionary kur.

Sort'un stable olduğunu varsaymak. Küçük listelerde sıranın korunduğunu görebilirsin, ama buna güvenemezsin. Yukarıdaki 40 kitaplık örnek bunu açıkça gösterdi.

Küçük Bir Deneme

★☆☆ Yazının başındaki ileri doğru for döngüsünü, silme yaptığında i'yi artırmayacak şekilde düzelt ve RemoveAll ile aynı sonucu aldığını göster.

★★☆ 1000 element'lik bir listeyi önce new List<int>(), sonra new List<int>(1000) ile doldur; kapasitenin kaç kez değiştiğini say.

★★★ Sort'a verdiğin karşılaştırmayı önce fiyata, fiyatlar eşitse ada göre bakacak şekilde genişlet. Aynı fiyatlı üç kitap ekle ve onların artık ada göre dizildiğini doğrula.

List<T>'de arama yapmanın bedelini gördük. Bir sonraki yazıda key ile anında erişen Dictionary<TKey, TValue>'ye ve tekil element'leri tutan HashSet<T>'ye geçiyoruz: TryGetValue, key eşitliği ve comparer'lar.