.NET Data Structures, Algorithms and Patterns Implementation

By Sameer On August 14, 2007 · Leave a Comment

Here are some common data structures implemented in .NET C# that you can download for free and even contribute to the project if you like (open source). Actual links to the source code for each of the below algorithms to be added in the near future. Learning these Computer Science algorithms and patterns will allow you to more effectively write your code. For example, if your data is already sorted, then it would make sense to use an algorithm such as Binary Search, that depends on a sorted list. Also, these below implentations are not included in the original .NET 2.0 CLR, so if you are looking for a generalized Priority Queue or Red Black Tree you will need to download the below code. Keep in mind it is not perfect, and it is NOT for everyone, but it is a good starting point. Wikipedia has details on most of the below algorithms such as Merge Sort which will explain in which cases it would be good to use and which cases it would not be so good.

Actual links to the source code for each of the below algorithms to be added in the near future. This page is still being improved.

Association<TKey, TValue>
VisitableHashTable<TKey, TValue>

Bubble Sort
Summary: Repeatedly swap elements until the order is correct. Works fast if the list is almost sorted. Doesn’t work so well if you have small elements near the bottom of the list.

Dijkstra’s Single Source Shortest Path algorithm
Summary: Graph "greedy" algorithm that solves the single-source shortest path problem for a directed graph with non negative edge weights.

Bag<T>

VisitableLinkedList<T>

Bucket Sort
Summary: Bucket sort is not a comparison sort, uses buckets, and in some cases can run in linear time

Prim’s Minimal Spanning Tree Algorithm
Summary: A graph algorithm that finds a minimum spanning tree.

BinaryTree<T>
Summary: A tree that each node has at most 2 children. This implementation is a generic tree of type T. For example you can create a Binary Tree of integers, or a Binary Tree of strings, or whatever you like.

VisitableList<T>

Cocktail Sort , Shaker Sort
Summary: Also known as bidirectional bubble sort, is both a stable sorting algorithm and a comparison sort.

BinarySearchTree<TKey, TValue>

VisitableQueue<T>

Comb Sort
Summary: An improved bubble sort that rivals the speed of Quick Sort

Deque<T>

VisitableStack<T>

Gnome Sort
Summary: A sort similar to insertion sort but uses a series of swaps to get the right order of elements. Runs in O(n²) time.

Fibonacci number generation.
Summary: Fibonacci numbers represent a pattern of reproduction numbers found in nature, such as how the population of rabbits will grow over time. Here are a few values: 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, …

GeneralTree<T>
Summary: An implementation of a tree in .NET

Heap Sort
Summary: Usually slower than quicksort, a ‘selection sort’ algorithm that works worst case O(n log n). As well its in-place but not a ‘stable sort’.

Euclid’s Algorithm (also known as Euclidean algorithm)
Summary: An algorithm to find the GCD (greatest common divisor) of two numbers. For example on 16, 18, the GCD is 2.

Graph<T>
Summary: An implementation of a graph in .NET

Insertion Sort
Summary: Very simple but also very slow sort.

Heap<T>
Summary: A heap is a specialized tree type data structure. (more details to be added).

Merge Sort
Summary: A classic divide and conquer algorithm that works by breaking up the data into two parts and sorting each one recursively. It runs in O(n log n) time.

Matrix

Odd-Even Transport Sort

Pascal Set
Summary: You can perform operations on set such as Set Union, Set Difference, Set Intersection, etc.

Quick Sort
Summary: A popular sorting algorithm that works in O(n log n) time on average.

Priority Queue<T>

Selection Sort
Summary: An in place sorting algorithm (meaning it does not require extra storage space) that performs in O(n²) time, meaning it is not usually practical for large lists, but is known for its simplicity.
SkipList<TKey, TValue>

Sorted List<T>

Shell Sort
Summary: An improvement over insertion sort. Runs in O(n log ² n)

Red Black Tree<T>
Summary: Self balancing binary search tree (i.e. even if you insert too much it will automatically reorganize itself into a binary search tree). It can amazingly search, insert, and delete in O(log n) time, meaning if you have 1000 elements, it will take roughly 3 operations to complete!

ReadOnlyPropertyCollection <T, TProperty>

Object Matrix<T>

Hash List<TKey, TValue>

Complex Number
Summary: The complex number (also known as imaginary number) i has the value Square Root of -1. You can do math on complex numbers using this class.

Circular Queue
Summary: A queue that loops around

Splay Tree
Summary: Another self balancing search tree. Runs in O(log n) amortized time.

Kruskal’s Algorithm
Summary: A graph algorithm that finds a minimum spanning tree for a connected weighted graph.

Hypotenuse

Tons of stuff to the Matrix and ObjectMatrix classes.

Vectors

Topological Sort for the Graph data structure.
Summary: Sorts your graph topologically (i.e. a linear ordering of its nodes).

Radix Sort
Summary: Integer sorting algorithm that works on individual digits.

Download it here (ZIP format, binaries, Version 1.3 Alpha)

(Released under the Microsoft Permissive License)
Originally posted here, and the new page is here that includes the source code incase you want to play around with it and possibly submit a better implementation you might have thought up!