Category: DOT NET

LinkedList

LinkedList<T> is a generic doubly linked list.

Doubly linked list is a chain of nodes in which each references the node before, the node after and the actual element.

Benefit – element can always be inserted efficiently anywhere in the list, since it just involves creating a new node and updating a few references.

Implements IEnumerable<T> and ICollection<T>.

LinkedList<T> supports copying to an array for indexed processing and obtaining an enumerator to support foreach statement.

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

var tune = new LinkedList();
tune.AddFirst ("do");                           tune.Dump(); // do
tune.AddLast ("so");                            tune.Dump(); // do - so

tune.AddAfter (tune.First, "re");               tune.Dump(); // do - re- so
tune.AddAfter (tune.First.Next, "mi");          tune.Dump(); // do - re - mi- so
tune.AddBefore (tune.Last, "fa");               tune.Dump(); // do - re - mi - fa- so

tune.RemoveFirst();                             tune.Dump(); // re - mi - fa - so
tune.RemoveLast();                              tune.Dump(); // re - mi - fa

LinkedListNode miNode = tune.Find ("mi");
tune.Remove (miNode);                           tune.Dump(); // re - fa
tune.AddFirst (miNode);                         tune.Dump(); // mi- re - fa

IReadOnlyList<T>

Low version of IList<T> which provides only readonly view of list.

public interface IReadOnlyList<out T> : IEnumerable<T>, IEnumerable
{
	int Count { get; }
	T this[int index] { get; }
}

IList<T> and IList

IList<T>

Standard interface for collection indexable by position.

Functionality inherited from ICollection<T> and IEnumerable<T>.

Provides the ability to read or write an element by position.

public interface IList : ICollection, IEnumerable, IEnumerable
{
	T this [int index] { get; set; }
	int IndexOf (T item);
	void Insert (int index, T item);
	void RemoveAt (int index);
}

IndexOf – performs liner search, returns -1 if item not found.

Insert – inserts at specified index.

RemoveAt – removes at specified index.

IList

public interface IList : ICollection, IEnumerable
{
object this [int index] { get; set }
bool IsFixedSize { get; }
bool IsReadOnly { get; }
int Add (object value);
void Clear();
bool Contains (object value);
int IndexOf (object value);
void Insert (int index, object value);
void Remove (object value);
void RemoveAt (int index);
}

Add – returns an integer index of the newly added item.

ICollection<T> and ICollection

ICollection<T> is the standard interface for countable collections of objects.

It provides the ability to determine the size of a collection (Count).

If the collection is writable you can also Add, Remove and Clear items from the collection.

Collection can be traversed via foreach statement since it extends IEnumerable.

Methods and Properties

Contains – determine whether an item exists in the collection.

ToArray – copy the collection into an array.

IsReadOnly – determine whether the collection is read-only.

Count-size of the collection.

Add– add item to the collection.

Remove– remove item from collection.

Clear– clear collection.

Generic Collection

public interface ICollection<T> : IEnumerable<T>, IEnumerable
{
	int Count { get; }
	
	bool Contains (T item);
	void CopyTo (T[] array, int arrayIndex);
	bool IsReadOnly { get; }

	void Add(T item);
	bool Remove (T item);
	void Clear();
}

Non Generic Collection

public interface ICollection : IEnumerable
{
	int Count { get; }
	bool IsSynchronized { get; }
	object SyncRoot { get; }
	void CopyTo (Array array, int index);
}

The interface is implemented in conjunction with either IList or IDictionary.

IEnumerable and IEnumerator

Related Article

IEnumerator Interface

Elements in a collection are enumerated in a forward manner only.

public interface IEnumerator
{
	bool MoveNext();
	object Current { get; }
	void Reset();
}

MoveNext – advances the current element to the next position or returns false if there are no more elements in the collection.

Current – returns the element at the current position.

Reset – moves back to the start of the collection.

Collections do not implement enumerators, instead they provide enumerators via the interface IEnumerable.

public interface IEnumerable
{
	IEnumerable GetEnumerator();
}

IEnumerable

Provides flexibility in that the iteration logic can be farmed off to another class.

Several consumers can enumerate the collection at once without interfering with each other.

IEnumerable can be thought of as IEnumeratorProvider.

string s = "Hello";

// Because string implements IEnumerable, we can call GetEnumerator():
IEnumerator rator = s.GetEnumerator();

while (rator.MoveNext())
{
	char c = (char) rator.Current;
	Console.Write (c + ".");
}

Console.WriteLine();

// Equivalent to:

foreach (char c in s)
	Console.Write (c + ".");

IEnumerable<T> and IEnumerator<T>

IEnumerator and IEnumerable are nearly always implemented in conjunction with their extended generic versions.

public interface IEnumerator : IEnumerator, IDisposable
{
	T Current { get; }
}

public interface IEnumerable : IEnumerable
{
	IEnumerator GetEnumerator();
}

By defining typed version of Current and GetEnumerator, these interfaces strengthen static type safety and avoid the boxing overhead.

Arrays automatically implement IEnumerable<T>.

IEnumerable<T> and IDisposable

IEnumerator<T> inherits from IDisposable.

This allows enumerators to hold references to resources such as database connections to ensure that those resources are released when enumeration is complete.

foreach (var element in somethingEnumerable) { ... }

translates into:

using ( var rator = somethingEnumerable.GetEnumerator())
	while (rator.MoveNext())
	{
		var element = rator.Current;
		...
	}

The using block ensures disposal.

IEnumerable s = "Hello";

using (var rator = s.GetEnumerator())
	while (rator.MoveNext())
	{
		char c = (char) rator.Current;
		Console.Write (c + ".");
	}

Non Generic Interface

void Main()
{
   Count("the quick brown fox".Split());
}

public static int Count(IEnumerable e)
{
   int count = 0;
   foreach (object element in e)
   {
      var subCollection = element as IEnumerable;
      if (subCollection != null)
          count += Count (subCollection);
      else
          count++;
   }
   return count;
}

IEnumerable or IEnumerable<T> can be implemented for one of the reasons:

• To support the foreach statement.
• To inter-operate with anything expecting a standard collections.
• To meet the requirements of a more sophisticated collection interface.
• To support collection initializers.

To implement IEnumerable/IEnumerable<T>:

• If class is wrapping another collection, return the wrapped collection’s enumerator
• Using the iterator yield return
• By instantiating your own implementation

Using Iterator

void Main()
{
	foreach (int element in new MyCollection())
		Console.WriteLine (element);
}

public class MyCollection : IEnumerable
{
	int[] data = { 1, 2, 3 };
	
	public IEnumerator GetEnumerator()
	{
		foreach (int i in data)
			yield return i;
	}
}

Using Iterator using Generic

void Main()
{
	foreach (int element in new MyGenCollection())
		Console.WriteLine (element);
}

public class MyGenCollection : IEnumerable<int>
{
	int[] data = { 1, 2, 3 };

	public IEnumerator GetEnumerator()
	{
		foreach (int i in data)
			yield return i;
	}

	IEnumerator IEnumerable.GetEnumerator()     // Explicit implementation
	{                                           // keeps it hidden.
		return GetEnumerator();
	}
}

Using Iterator Method

The yield statement allows for an easier variation. Instead of writing a class the iteration logic can be moved into a method returning a generic IEnumerable<T> and let the compiler take care of the rest.

void Main()
{
	foreach (int i in Test.GetSomeIntegers())
		Console.WriteLine (i);
}

public class Test
{
	public static IEnumerable  GetSomeIntegers()
	{
		yield return 1;
		yield return 2;
		yield return 3;
	}
}