NetFabric.DoubleLinkedList

An alternative to the System.Collections.Generic.LinkedList<T> with reverse operation and enumeration without allocation.

The public API is very similar but the internals are very different with a more efficient implementation.

New overrides and methods were added to minimizing the memory allocations, number of loops, conditions and assignments required in multiple scenarios.

Benchmarks

Performance comparison between System.Collections.Generic.LinkedList<T> and DoubleLinkedList<T>. Shorter is better.

The benchmarks project is part of the repository. You can check the code and run it on your machine.

Forward and reverse enumeration

DoubleLinkedList<T> does not implement IEnumerable<T>. Call the methods EnumerateForward() or EnumerateReversed() to get an enumerator that goes in the direction you require.

var list = new DoubleLinkedList<int>(new[] {1, 2, 3, 4});
foreach (var item in list.EnumerateReversed())
	Console.Write(item);

outputs

4321

Although these enumerators are optimized for performance, they perform a bit more method calls and conditions than simply using a while loop to go throught the Node references. The performance penalty can be seen on the benchmarks above. The advantage is that these can be used with LINQ or any third-party method that takes IEnumerable, IEnumerable<T> or IReadOnlyCollection<T> as parameter.

var list = new DoubleLinkedList<int>(new[] {1, 2, 3, 4});
Console.Write(list.EnumerateReversed().First());

outputs

4

AddFirst() and AddLast()

These methods now support the addition of collections of items. These can come from an IEnumerable<T>, IReadOnlyList<T> or another DoubleLinkedList<T>.

When the parameter is IReadOnlyList<T> or DoubleLinkedList<T>, they can be added reversed.

var list = new DoubleLinkedList<int>(new[] {1, 2, 3, 4});
var anotherList = new DoubleLinkedList<int>(new[] {5, 6, 7, 8});
list.AddFirst(anotherList, true);
foreach (var item in list.EnumerateForward())
	Console.Write(item);

outputs

87651234

AddFirstFrom() and AddLastFrom()

These methods perform the addition of a DoubleLinkedList<T> but moving the nodes into the other DoubleLinkedList<T>. No memory allocations and copies of values are performed.

The DoubleLinkedList<T> passed as parameter becomes empty.

Append()

A static method that returns a DoubleLinkedList<T> instance with the items of both lists appended.

var list = DoubleLinkedList.Append(
	new DoubleLinkedList<int>(new[] {1, 2, 3, 4}), 
	new DoubleLinkedList<int>(new[] {5, 6, 7, 8}));
foreach (var item in list.EnumerateForward())
	Console.Write(item);

outputs

12345678

Clone()

Returns a shallow clone of the a DoubleLinkedList<T>.

var list = new DoubleLinkedList<int>(new[] {1, 2, 3, 4});
var clone = list.Clone();
foreach (var item in list.EnumerateForward())
	Console.Write(item);

outputs

1234

Reverse()

Returns a shallow clone of the a DoubleLinkedList<T> with the items in reversed order.

var list = new DoubleLinkedList<int>(new[] {1, 2, 3, 4});
var reversed = list.Reverse();
foreach (var item in reversed.EnumerateForward())
	Console.Write(item);

outputs

4321

ReverseInPlace()

ReverseInPlace() reverses the list items in-place. It flips the internal node references with no memory allocations.

var list = new DoubleLinkedList<int>(new[] {1, 2, 3, 4});
list.ReverseInPlace();
foreach (var item in list.EnumerateForward())
	Console.Write(item);

also outputs

4321