Skip to content

An alternative to LinkedList<T> with reverse operation and enumeration without allocation.

License

Notifications You must be signed in to change notification settings

NetFabric/NetFabric.DoublyLinkedList

Repository files navigation

NetFabric.DoublyLinkedList

GitHub last commit (master) Build Coverage NuGet Version NuGet Downloads

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 DoublyLinkedList<T>.

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

Constructor performance

Method Count Mean Error StdDev Median Ratio RatioSD Gen 0 Gen 1 Gen 2 Allocated
LinkedList_Enumerable 0 12.082 ns 0.3174 ns 0.4942 ns 12.091 ns 1.00 0.00 0.0191 - - 40 B
LinkedList_List 0 21.542 ns 0.9611 ns 2.7884 ns 19.863 ns 2.07 0.21 0.0382 - - 80 B
DoublyLinkedList_Enumerable 0 10.749 ns 0.0741 ns 0.0657 ns 10.761 ns 0.89 0.04 0.0191 - - 40 B
DoublyLinkedList_List 0 7.533 ns 0.1320 ns 0.1170 ns 7.511 ns 0.62 0.03 0.0191 - - 40 B
DoublyLinkedList_List_Reversed 0 7.391 ns 0.1275 ns 0.1192 ns 7.386 ns 0.61 0.03 0.0191 - - 40 B
LinkedList_Enumerable 10 205.166 ns 1.2539 ns 1.1116 ns 205.147 ns 1.00 0.00 0.2677 - - 560 B
LinkedList_List 10 241.563 ns 1.7717 ns 2.3651 ns 241.213 ns 1.18 0.01 0.2675 - - 560 B
DoublyLinkedList_Enumerable 10 163.873 ns 1.8013 ns 1.5042 ns 163.424 ns 0.80 0.01 0.2677 - - 560 B
DoublyLinkedList_List 10 142.060 ns 1.3490 ns 1.1265 ns 142.538 ns 0.69 0.01 0.2487 - - 520 B
DoublyLinkedList_List_Reversed 10 139.378 ns 1.0579 ns 0.8834 ns 139.184 ns 0.68 0.00 0.2487 - - 520 B
LinkedList_Enumerable 100 1,804.348 ns 16.3064 ns 15.2530 ns 1,808.247 ns 1.00 0.00 2.3327 - - 4,880 B
LinkedList_List 100 1,894.060 ns 12.0334 ns 11.2561 ns 1,895.876 ns 1.05 0.01 2.3327 - - 4,880 B
DoublyLinkedList_Enumerable 100 1,355.031 ns 16.9081 ns 14.1191 ns 1,352.691 ns 0.75 0.01 2.3327 - - 4,880 B
DoublyLinkedList_List 100 1,216.764 ns 11.3984 ns 10.6620 ns 1,218.606 ns 0.67 0.01 2.3136 - - 4,840 B
DoublyLinkedList_List_Reversed 100 1,233.906 ns 11.7235 ns 10.9662 ns 1,238.096 ns 0.68 0.01 2.3136 - - 4,840 B

Enumeration performance

Method Categories Count Mean Error StdDev Ratio RatioSD Gen 0 Gen 1 Gen 2 Allocated
LinkedList_Forward_While Forward 100000 320.0 μs 3.77 μs 3.53 μs 1.00 0.00 - - - -
LinkedList_Forward_ForEach Forward 100000 496.1 μs 5.55 μs 5.19 μs 1.55 0.02 - - - -
DoublyLinkedList_Forward_While Forward 100000 306.3 μs 3.37 μs 3.15 μs 0.96 0.01 - - - -
DoublyLinkedList_Forward_ForEach Forward 100000 470.0 μs 4.44 μs 3.70 μs 1.47 0.01 - - - -
LinkedList_Reverse_While Reverse 100000 353.5 μs 6.03 μs 5.03 μs 1.00 0.00 - - - -
LinkedList_Reverse_ForEach Reverse 100000 934.6 μs 7.46 μs 6.23 μs 2.64 0.04 41.0156 41.0156 41.0156 400,393 B
DoublyLinkedList_Reverse_While Reverse 100000 356.4 μs 2.89 μs 2.70 μs 1.01 0.02 - - - -
DoublyLinkedList_Reverse_ForEach Reverse 100000 499.3 μs 6.13 μs 5.44 μs 1.42 0.03 - - - -

Forward and reverse enumeration

DoublyLinkedList<T> does not directly implement IEnumerable<T>. Call the properties Forward or Backward to get an enumerator that goes in the direction you require.

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

outputs

4321

These methods allow the use of LINQ on either direction:

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

outputs

4

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.

var current = doublyLinkedList.Last;
while (current is object)
{
    Console.Write(current.Value);
    current = current.Previous;
}

The enumerators also supports random access by using an indexer. It allows indexing relative to the head or the tail of the list.

var head = doublyLinkedList.Forward[0];
var tail = doublyLinkedList.Backward[0];

Please note that this DoublyLinkedList is not optimized for random access. It will use the shortest path to the item but it will have to step through the list to get there.

AddFirst() and AddLast()

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

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

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

outputs

87651234

AddFirstFrom() and AddLastFrom()

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

The DoublyLinkedList<T> passed as parameter becomes empty.

Append()

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

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

outputs

12345678

Clone()

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

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

outputs

1234

Reverse()

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

var list = new DoublyLinkedList<int>(new[] {1, 2, 3, 4});
var reversed = list.Reverse();
foreach (var item in reversed.Forward)
	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 DoublyLinkedList<int>(new[] {1, 2, 3, 4});
list.ReverseInPlace();
foreach (var item in list.Forward)
	Console.Write(item);

also outputs

4321