List<T> و ArrayList

Class Generic با نام List و Class غیرGeneric با نام ArrayList یک Array با اندازهٔ Dynamic از Objectها فراهم می‌کنند و از پرکاربردترین Classهای Collection هستند. ArrayList، IList را پیاده‌سازی می‌کند، درحالی‌که List<T> هم IList و هم IList<T> — و نسخهٔ Read-only یعنی IReadOnlyList<T> — را پیاده‌سازی می‌کند. برخلاف Arrayها، تمام این Interfaceها به‌صورت Public پیاده‌سازی شده‌اند و Methodهایی مانند Add و Remove در معرض قرار دارند و همان‌طور که انتظار دارید کار می‌کنند.

در داخل، List<T> و ArrayList یک Array داخلی از Objectها نگه می‌دارند که وقتی به Capacity برسد با Array بزرگ‌تری جایگزین می‌شود. Append کردن Elementها کارآمد است، چون معمولاً Slot خالی در انتها وجود دارد؛ اما Insert کردن می‌تواند کند باشد، زیرا تمام Elementهای بعد از محل Insert باید Shift شوند تا یک Slot آزاد شود. Remove کردن نیز — به‌ویژه نزدیک ابتدای List — می‌تواند کند باشد. همانند Arrayها، Search در صورتی کارآمد است که BinarySearch روی List مرتب‌شده استفاده شود؛ در غیر این صورت ناکارآمد است، چون هر Item باید جداگانه بررسی شود.

List<T> وقتی T یک Value Type باشد ممکن است چند برابر سریع‌تر از ArrayList باشد، زیرا از هزینهٔ Boxing و Unboxing عناصر جلوگیری می‌کند.

List<T> و ArrayList Constructorهایی دارند که Collection موجودی از Elementها را می‌پذیرند؛ این Constructorها هر Element را از Collection موجود به List جدید کپی می‌کنند:

public class List<T> : IList<T>, IReadOnlyList<T>
{
  public List ();
  public List (IEnumerable<T> collection);
  public List (int capacity);
  // Add+Insert
  public void Add (T item);
  public void AddRange (IEnumerable<T> collection);
  public void Insert (int index, T item);
  public void InsertRange (int index, IEnumerable<T> collection);
  // Remove
  public bool Remove (T item);
  public void RemoveAt (int index);
  public void RemoveRange (int index, int count);
  public int RemoveAll (Predicate<T> match);
  // Indexing
  public T this [int index] { get; set; }
  public List<T> GetRange (int index, int count);
  public Enumerator<T> GetEnumerator();
  // Exporting, copying and converting:
  public T[] ToArray();
  public void CopyTo (T[] array);
  public void CopyTo (T[] array, int arrayIndex);

  public void CopyTo (int index, T[] array, int arrayIndex, int count);
  public ReadOnlyCollection<T> AsReadOnly();
  public List<TOutput> ConvertAll<TOutput> (Converter <T,TOutput>
  converter);
  // Other:
  public void Reverse(); // Reverses order of elements in list.
  public int Capacity { get;set; } // Forces expansion of internal array.
  public void TrimExcess(); // Trims internal array back to size.
  public void Clear(); // Removes all elements, so Count=0.
}
public delegate TOutput Converter <TInput, TOutput> (TInput input);

علاوه بر این Memberها، List<T> نسخهٔ Instance از تمام Methodهای Searching و Sorting مربوط به Array را نیز فراهم می‌کند.

کد زیر Propertyها و Methodهای List را نشان می‌دهد؛ برای مثال‌های Search و Sort، بخش «The Array Class» در صفحهٔ 377 کتاب را ببینید:

var words = new List<string>(); // New string-typed list
words.Add ("melon");
words.Add ("avocado");
words.AddRange (["banana", "plum"]);
words.Insert (0, "lemon"); // Insert at start
words.InsertRange (0, ["peach", "nashi"]); // Insert at start
words.Remove ("melon");
words.RemoveAt (3); // Remove the 4th element
words.RemoveRange (0, 2); // Remove first 2 elements
// Remove all strings starting in 'n':
words.RemoveAll (s => s.StartsWith ("n"));
Console.WriteLine (words [0]); // first word
Console.WriteLine (words [words.Count - 1]); // last word
foreach (string s in words) Console.WriteLine (s); // all words
List<string> subset = words.GetRange (1, 2); // 2nd->3rd words
string[] wordsArray = words.ToArray(); // Creates a new typed array
// Copy first two elements to the end of an existing array:
string[] existing = new string [1000];
words.CopyTo (0, existing, 998, 2);
List<string> upperCaseWords = words.ConvertAll (s => s.ToUpper());
List<int> lengths = words.ConvertAll (s => s.Length);

Class غیرGeneric با نام ArrayList به Castهای دست‌وپاگیر نیاز دارد، همان‌طور که مثال زیر نشان می‌دهد:

ArrayList al = new ArrayList();
al.Add ("hello");
string first = (string) al [0];
string[] strArr = (string[]) al.ToArray (typeof (string));

چنین Castهایی توسط Compiler قابل Verification نیستند؛ کد زیر با موفقیت Compile می‌شود اما در Runtime شکست می‌خورد:

int first = (int) al [0]; // Runtime exception

ArrayList از نظر Functionality شبیه List<object> است. هر دو وقتی مفیدند که به Listی از Elementهای Mixed-type نیاز دارید که Base Type مشترکی جز object ندارند. یک مزیت احتمالی ArrayList در این حالت وقتی است که لازم باشد با Reflection — فصل ۱۹ — با List کار کنید. Reflection با ArrayList غیرGeneric ساده‌تر از List<object> است.

اگر Namespace با نام System.Linq را Import کنید، می‌توانید با فراخوانی Cast و سپس ToList یک ArrayList را به List Generic تبدیل کنید:

ArrayList al = new ArrayList();
al.AddRange (new[] { 1, 5, 9 } );
List<int> list = al.Cast<int>().ToList();

Cast و ToList Extension Methodهایی در Class با نام System.Linq.Enumerable هستند.

LinkedList<T>

LinkedList<T> یک Doubly Linked List Generic است؛ شکل 7-4 را ببینید. Doubly Linked List زنجیره‌ای از Nodeهاست که هرکدام به Node قبلی، Node بعدی و Element واقعی Reference می‌دهند. مزیت اصلی آن این است که Element را همیشه می‌توان در هر نقطه از List به‌صورت کارآمد Insert کرد، چون فقط نیاز به ساخت Node جدید و Update چند Reference دارد. بااین‌حال، پیدا کردن محل Insert در وهلهٔ اول ممکن است کند باشد، زیرا Mechanism ذاتی برای Index مستقیم در Linked List وجود ندارد؛ باید Nodeها یکی‌یکی Traverse شوند و Binary-chop Search ممکن نیست.

LinkedList<T>، IEnumerable<T> و ICollection<T> — و نسخه‌های Nongeneric آن‌ها — را پیاده‌سازی می‌کند، اما IList<T> را نه، چون دسترسی براساس Index پشتیبانی نمی‌شود. Nodeهای List با Class زیر پیاده‌سازی می‌شوند:

public sealed class LinkedListNode<T>
{
  public LinkedList<T> List { get; }
  public LinkedListNode<T> Next { get; }
  public LinkedListNode<T> Previous { get; }
  public T Value { get; set; }
}

هنگام افزودن Node می‌توانید Position آن را نسبت به Node دیگر یا در ابتدا/انتهای List مشخص کنید. LinkedList<T> Methodهای زیر را برای این کار فراهم می‌کند:

public void AddFirst(LinkedListNode<T> node);
public LinkedListNode<T> AddFirst (T value);
public void AddLast (LinkedListNode<T> node);
public LinkedListNode<T> AddLast (T value);
public void AddAfter (LinkedListNode<T> node, LinkedListNode<T> newNode);
public LinkedListNode<T> AddAfter (LinkedListNode<T> node, T value);
public void AddBefore (LinkedListNode<T> node, LinkedListNode<T> newNode);
public LinkedListNode<T> AddBefore (LinkedListNode<T> node, T value);

Methodهای مشابهی برای حذف Elementها وجود دارد:

public void Clear();
public void RemoveFirst();
public void RemoveLast();
public bool Remove (T value);
public void Remove (LinkedListNode<T> node);

LinkedList<T> Fieldهای داخلی برای نگهداری تعداد Elementها و نیز Head و Tail List دارد. این موارد با Propertyهای Public زیر در دسترس قرار می‌گیرند:

public int Count { get; } // Fast
public LinkedListNode<T> First { get; } // Fast
public LinkedListNode<T> Last { get; } // Fast

LinkedList<T> همچنین Methodهای Searching زیر را پشتیبانی می‌کند که هرکدام مستلزم Enumerate شدن داخلی List هستند:

public bool Contains (T value);
public LinkedListNode<T> Find (T value);
public LinkedListNode<T> FindLast (T value);

در نهایت، LinkedList<T> کپی‌کردن به Array برای Indexed Processing و گرفتن Enumerator برای پشتیبانی از foreach را نیز فراهم می‌کند:

public void CopyTo (T[] array, int index);
public Enumerator<T> GetEnumerator();

نمونهٔ استفاده از LinkedList<string>:

var tune = new LinkedList<string>();
tune.AddFirst ("do"); // do
tune.AddLast ("so"); // do - so
tune.AddAfter (tune.First, "re"); // do - re- so
tune.AddAfter (tune.First.Next, "mi"); // do - re - mi- so
tune.AddBefore (tune.Last, "fa"); // do - re - mi - fa- so
tune.RemoveFirst(); // re - mi - fa - so
tune.RemoveLast(); // re - mi - fa
LinkedListNode<string> miNode = tune.Find ("mi");
tune.Remove (miNode); // re - fa
tune.AddFirst (miNode); // mi- re - fa
foreach (string s in tune) Console.WriteLine (s);

Queue<T> و Queue

Queue<T> و Queue Data Structureهای First-in, First-out یا FIFO هستند و Methodهایی برای Enqueue — افزودن Item به Tail Queue — و Dequeue — دریافت و حذف Item از Head Queue — دارند. Method با نام Peek نیز Element موجود در Head Queue را بدون حذف‌کردن برمی‌گرداند، و Property با نام Count نیز وجود دارد که برای بررسی وجود Element پیش از Dequeue مفید است.

با اینکه Queueها قابل Enumeration هستند، IList<T>/IList را پیاده‌سازی نمی‌کنند، زیرا Memberها را نمی‌توان مستقیماً براساس Index دسترسی داد. بااین‌حال، Method با نام ToArray برای کپی Elementها به Array فراهم شده تا از آنجا بتوان به‌شکل Random به آن‌ها دسترسی داشت:

public class Queue<T> : IEnumerable<T>, ICollection, IEnumerable
{
  public Queue();
  public Queue (IEnumerable<T> collection); // Copies existing elements
  public Queue (int capacity); // To lessen auto-resizing
  public void Clear();
  public bool Contains (T item);
  public void CopyTo (T[] array, int arrayIndex);
  public int Count { get; }
  public T Dequeue();
  public void Enqueue (T item);
  public Enumerator<T> GetEnumerator(); // To support foreach
  public T Peek();
  public T[] ToArray();
  public void TrimExcess();
}

مثال استفاده از Queue<int>:

var q = new Queue<int>();
q.Enqueue (10);
q.Enqueue (20);
int[] data = q.ToArray(); // Exports to an array
Console.WriteLine (q.Count); // "2"
Console.WriteLine (q.Peek()); // "10"
Console.WriteLine (q.Dequeue()); // "10"
Console.WriteLine (q.Dequeue()); // "20"
Console.WriteLine (q.Dequeue()); // throws an exception (queue empty)

Queueها در داخل با Arrayای پیاده‌سازی می‌شوند که در صورت نیاز Resize می‌شود؛ بسیار شبیه Class Generic با نام List. Queue Indexهایی نگه می‌دارد که مستقیماً به Elementهای Head و Tail اشاره می‌کنند؛ بنابراین عملیات Enqueue و Dequeue بسیار سریع هستند، جز زمانی که Resize داخلی لازم باشد.

Stack<T> و Stack

Stack<T> و Stack Data Structureهای Last-in, First-out یا LIFO هستند و Methodهایی برای Push — افزودن Item به بالای Stack — و Pop — دریافت و حذف Element از بالای Stack — فراهم می‌کنند. Method غیرتخریبی Peek نیز وجود دارد، همچنین Property با نام Count و Method با نام ToArray برای Export کردن Data جهت Random Access:

public class Stack<T> : IEnumerable<T>, ICollection, IEnumerable
{
  public Stack();
  public Stack (IEnumerable<T> collection); // Copies existing elements
  public Stack (int capacity); // Lessens auto-resizing
  public void Clear();
  public bool Contains (T item);
  public void CopyTo (T[] array, int arrayIndex);
  public int Count { get; }
  public Enumerator<T> GetEnumerator(); // To support foreach
  public T Peek();
  public T Pop();
  public void Push (T item);
  public T[] ToArray();
  public void TrimExcess();
}

مثال Stack<int>:

var s = new Stack<int>();
s.Push (1); // Stack = 1
s.Push (2); // Stack = 1,2
s.Push (3); // Stack = 1,2,3
Console.WriteLine (s.Count); // Prints 3
Console.WriteLine (s.Peek()); // Prints 3, Stack = 1,2,3
Console.WriteLine (s.Pop()); // Prints 3, Stack = 1,2
Console.WriteLine (s.Pop()); // Prints 2, Stack = 1
Console.WriteLine (s.Pop()); // Prints 1, Stack = <empty>
Console.WriteLine (s.Pop()); // throws exception

Stackها نیز مانند Queue<T> و List<T> در داخل با Arrayای پیاده‌سازی می‌شوند که در صورت نیاز Resize می‌شود.

BitArray

BitArray Collectionی با اندازهٔ Dynamic از Valueهای bool فشرده است. از نظر Memory از Array سادهٔ bool و List<bool> Generic کارآمدتر است، چون برای هر Value فقط یک Bit مصرف می‌کند، درحالی‌که Type با نام bool در حالت عادی برای هر Value یک Byte اشغال می‌کند.

Indexer مربوط به BitArray Bitهای منفرد را می‌خواند و می‌نویسد:

var bits = new BitArray(2);
bits[1] = true;

چهار Method برای Operatorهای Bitwise وجود دارد: And، Or، Xor و Not. همه به‌جز مورد آخر یک BitArray دیگر می‌پذیرند:

bits.Xor (bits); // Bitwise exclusive-OR bits with itself
Console.WriteLine (bits[1]); // False

HashSet<T> و SortedSet<T>

HashSet<T> و SortedSet<T> ویژگی‌های متمایز زیر را دارند:

• Methodهای Contains آن‌ها با Hash-based Lookup سریع اجرا می‌شود.
• Elementهای Duplicate ذخیره نمی‌کنند و درخواست افزودن Duplicate را بدون خطا نادیده می‌گیرند.
• نمی‌توانید براساس Position به Element دسترسی داشته باشید.

SortedSet<T> Elementها را مرتب نگه می‌دارد، اما HashSet<T> چنین نمی‌کند.

اشتراک Functionality این دو Type در Interface با نام ISet<T> بیان می‌شود. از .NET 5، این Classها Interface با نام IReadOnlySet<T> را نیز پیاده‌سازی می‌کنند؛ Typeهای Immutable Set نیز آن را پیاده‌سازی می‌کنند که در بخش «Immutable Collections» صفحهٔ 406 توضیح داده می‌شود.

HashSet<T> با Hashtableای پیاده‌سازی شده که فقط Keyها را نگه می‌دارد؛ SortedSet<T> با Red/Black Tree پیاده‌سازی شده است.

هر دو Collection، ICollection<T> را پیاده‌سازی می‌کنند و Methodهایی مانند Contains، Add و Remove دارند. علاوه بر این، Method حذف مبتنی بر Predicate با نام RemoveWhere نیز وجود دارد.

کد زیر از یک Collection موجود HashSet<char> می‌سازد، Membership را Test می‌کند و سپس Collection را Enumerate می‌کند؛ به نبود Duplicateها توجه کنید:

var letters = new HashSet<char> ("the quick brown fox");
Console.WriteLine (letters.Contains ('t')); // true
Console.WriteLine (letters.Contains ('j')); // false
foreach (char c in letters) Console.Write (c); // the quickbrownfx

دلیل اینکه می‌توانیم یک string را به Constructor مربوط به HashSet<char> بدهیم این است که string، IEnumerable<char> را پیاده‌سازی می‌کند.

Methodهای واقعاً جالب، عملیات Set هستند. عملیات زیر Destructive هستند، یعنی Set را تغییر می‌دهند:

public void UnionWith (IEnumerable<T> other); // Adds
public void IntersectWith (IEnumerable<T> other); // Removes
public void ExceptWith (IEnumerable<T> other); // Removes
public void SymmetricExceptWith (IEnumerable<T> other); // Removes

درحالی‌که Methodهای زیر فقط Set را Query می‌کنند و بنابراین Nondestructive هستند:

public bool IsSubsetOf (IEnumerable<T> other);
public bool IsProperSubsetOf (IEnumerable<T> other);
public bool IsSupersetOf (IEnumerable<T> other);
public bool IsProperSupersetOf (IEnumerable<T> other);
public bool Overlaps (IEnumerable<T> other);
public bool SetEquals (IEnumerable<T> other);

UnionWith تمام Elementهای Set دوم را به Set اصلی اضافه می‌کند و Duplicateها را کنار می‌گذارد. IntersectWith Elementهایی را حذف می‌کند که در هر دو Set وجود ندارند. می‌توانیم تمام Vowelها را از Set Characterها چنین استخراج کنیم:

var letters = new HashSet<char> ("the quick brown fox");
letters.IntersectWith ("aeiou");
foreach (char c in letters) Console.Write (c); // euio

ExceptWith Elementهای مشخص‌شده را از Source Set حذف می‌کند. در اینجا تمام Vowelها حذف می‌شوند:

var letters = new HashSet<char> ("the quick brown fox");
letters.ExceptWith ("aeiou");
foreach (char c in letters) Console.Write (c); // th qckbrwnfx

SymmetricExceptWith همهٔ Elementها را به‌جز آن‌هایی که فقط در یکی از دو Set یکتا هستند حذف می‌کند:

var letters = new HashSet<char> ("the quick brown fox");
letters.SymmetricExceptWith ("the lazy brown fox");
foreach (char c in letters) Console.Write (c); // quicklazy

توجه کنید چون HashSet<T> و SortedSet<T>، IEnumerable<T> را پیاده‌سازی می‌کنند، می‌توانید Type دیگری از Set یا Collection را به‌عنوان Argument هر Method مربوط به عملیات Set بدهید.

SortedSet<T> تمام Memberهای HashSet<T> را به‌علاوهٔ موارد زیر ارائه می‌کند:

public virtual SortedSet<T> GetViewBetween (T lowerValue, T upperValue)
public IEnumerable<T> Reverse()
public T Min { get; }
public T Max { get; }

SortedSet<T> همچنین Constructorای دارد که به‌صورت اختیاری IComparer<T> می‌پذیرد، نه Equality Comparer.

مثال زیر همان Letterها را در SortedSet<char> Load می‌کند:

var letters = new SortedSet<char> ("the quick brown fox");
foreach (char c in letters) Console.Write (c); // bcefhiknoqrtuwx

پس از آن می‌توان Letterهای بین f و i را در Set چنین گرفت:

foreach (char c in letters.GetViewBetween ('f', 'i'))
  Console.Write (c); // fhi

Dictionaries

Dictionary یک Collection است که هر Element آن یک Key/Value Pair است. Dictionaryها معمولاً برای Lookup و Sorted Listها استفاده می‌شوند.

.NET از طریق Interfaceهای IDictionary و IDictionary<TKey,TValue> یک Protocol استاندارد برای Dictionaryها تعریف می‌کند و مجموعه‌ای از Classهای General-purpose Dictionary نیز دارد. این Classها از جنبه‌های زیر با یکدیگر تفاوت دارند:

• اینکه Itemها در Sequence مرتب ذخیره می‌شوند یا نه.
• اینکه Itemها علاوه بر Key براساس Position یا Index نیز قابل دسترسی هستند یا نه.
• Generic یا Nongeneric بودن.
• سرعت یا کندی Retrieval براساس Key در Dictionary بزرگ.

جدول 7-1 در صفحهٔ بعد Classهای Dictionary و تفاوت‌های آن‌ها را خلاصه می‌کند. زمان‌های Performance برحسب Millisecond هستند و براساس اجرای 50,000 Operation روی Dictionary با Key و Value از نوع Integer در یک PC با سرعت 1.5 GHz به دست آمده‌اند. تفاوت Performance میان همتایان Generic و Nongeneric که Structure داخلی مشابه دارند ناشی از Boxing است و فقط برای Elementهای Value Type ظاهر می‌شود.