<p>I would like to know how people implement the following data structures in C# without using the base class library implementations:-</p>

<ul>
<li>Linked List</li>
<li>Hash Table</li>
<li>Binary Search Tree</li>
<li>Red-Black Tree</li>
<li>B-Tree</li>
<li>Binomial Heap</li>
<li>Fibonacci Heap</li>
</ul>

<p>and any other fundamental data structures people can think of!</p>

<p>I am curious as I want to improve my understanding of these data structures and it'd be nice to see C# versions rather than the typical C examples out there on the internet!</p>

[{'answer_id': 48319, 'author': 'Konrad Rudolph', 'author_id': 1968, 'author_profile': 'https://Stackoverflow.com/users/1968', 'pm_score': 3, 'selected': False, 'text': '<p>There\'s a series of <a href="http://msdn.microsoft.com/en-us/vcsharp/aa336800.aspx" rel="nofollow noreferrer">MSDN articles</a> on this subject. However, I haven\'t really read the text myself. I believe that the collections framework by .NET has a broken interface and cannot be extended very well.</p>\n\n<p>There\'s also <a href="http://www.itu.dk/research/c5/" rel="nofollow noreferrer">C5</a>, a libray that I am investigating right now.</p>\n\n<p>For the reason mentioned above, I\'ve had the project to implement my own collections library for .NET but I\'ve stopped this project after the first benchmark revealed that even a straightforward, non-thread-safe generic <code>Vector</code> implementation is slower than the native <code>List&lt;T&gt;</code>. Since I\'ve taken care not to produce any inefficient IL code, this means that .NET is simply not suited (yet) for writing on-par replacements for intrinsic data structures, and that the .NET framework has to use some behind-the-scenes knowledge to optimize the builtin collection classes.</p>\n'}, {'answer_id': 48350, 'author': 'Brad Leach', 'author_id': 708, 'author_profile': 'https://Stackoverflow.com/users/708', 'pm_score': 2, 'selected': False, 'text': '<p>I would recommend two resources for the data structures you mention:\nFirst, there is the .NET Framework Source Code (information can be found on ScottGu\'s blog <a href="http://weblogs.asp.net/scottgu/archive/2008/01/16/net-framework-library-source-code-now-available.aspx" rel="nofollow noreferrer">here</a>).</p>\n\n<p>Another useful resource is the Wintellect\'s Power Collections found on Codeplex <a href="http://www.codeplex.com/PowerCollections" rel="nofollow noreferrer">here</a>.</p>\n\n<p>Hope this helps!</p>\n'}, {'answer_id': 48464, 'author': 'FlySwat', 'author_id': 1965, 'author_profile': 'https://Stackoverflow.com/users/1965', 'pm_score': 2, 'selected': False, 'text': '<p>Here is a generic Binary Search Tree. The only thing I didn\'t do was implement IEnumerable&lt;T&gt; so you could traverse the tree using a enumerator. However that should be fairly straight forward.</p>\n\n<p>Special thanks to Scott Mitchel for his BSTTree article, I used it as a reference on the delete method.</p>\n\n<p>The Node Class:</p>\n\n<pre><code>    class BSTNode&lt;T&gt; where T : IComparable&lt;T&gt;\n    {\n        private BSTNode&lt;T&gt; _left = null;\n        private BSTNode&lt;T&gt; _right = null;        \n        private T _value = default(T);\n\n        public T Value\n        {\n            get { return this._value; }\n            set { this._value = value; }\n        }\n\n        public BSTNode&lt;T&gt; Left\n        {\n            get { return _left; }\n            set { this._left = value; }\n        }\n\n        public BSTNode&lt;T&gt; Right\n        {\n            get { return _right; }\n            set { this._right = value; }\n        }        \n    }\n</code></pre>\n\n<p>And the actual Tree class:</p>\n\n<pre><code>    class BinarySearchTree&lt;T&gt; where T : IComparable&lt;T&gt;\n    {\n        private BSTNode&lt;T&gt; _root = null;\n        private int _count = 0;\n\n        public virtual void Clear()\n        {\n            _root = null;\n            _count = 0;\n        }\n\n        public virtual int Count\n        {\n            get { return _count; }\n        }\n\n        public virtual void Add(T value)\n        {\n            BSTNode&lt;T&gt; newNode = new BSTNode&lt;T&gt;();\n            int compareResult = 0;\n\n            newNode.Value = value;\n\n            if (_root == null)\n            {\n                this._count++;\n                _root = newNode;\n            }\n            else\n            {\n                BSTNode&lt;T&gt; current = _root;\n                BSTNode&lt;T&gt; parent = null;\n\n                while (current != null)\n                {\n                    compareResult = current.Value.CompareTo(newNode.Value);\n\n                    if (compareResult &gt; 0)\n                    {\n                        parent = current;\n                        current = current.Left;\n                    }\n                    else if (compareResult &lt; 0)\n                    {\n                        parent = current;\n                        current = current.Right;\n                    }\n                    else\n                    {\n                        // Node already exists\n                        throw new ArgumentException("Duplicate nodes are not allowed.");\n                    }\n                }\n\n                this._count++;\n\n                compareResult = parent.Value.CompareTo(newNode.Value);\n                if (compareResult &gt; 0)\n                {\n                    parent.Left = newNode;\n                }\n                else\n                {\n                    parent.Right = newNode;\n                }\n            }\n        }\n\n        public virtual BSTNode&lt;T&gt; FindByValue(T value)\n        {\n            BSTNode&lt;T&gt; current = this._root;\n\n            if (current == null)\n                return null;   // Tree is empty.\n            else\n            {\n                while (current != null)\n                {\n                    int result = current.Value.CompareTo(value);\n                    if (result == 0)\n                    {\n                        // Found the corrent Node.\n                        return current;\n                    }\n                    else if (result &gt; 0)\n                    {\n                        current = current.Left;\n                    }\n                    else\n                    {\n                        current = current.Right;\n                    }\n                }\n\n                return null;\n            }\n        }\n\n        public virtual void Delete(T value)\n        {\n\n            BSTNode&lt;T&gt; current = this._root;\n            BSTNode&lt;T&gt; parent = null;\n\n            int result = current.Value.CompareTo(value);\n\n            while (result != 0 &amp;&amp; current != null)\n            {\n                if (result &gt; 0)\n                {\n                    parent = current;\n                    current = current.Left;\n                }\n                else if (result &lt; 0)\n                {\n                    parent = current;\n                    current = current.Right;\n                }\n\n                result = current.Value.CompareTo(value);\n            }\n\n            if (current == null)\n                throw new ArgumentException("Cannot find item to delete.");\n\n\n\n            if (current.Right == null)\n            {\n                if (parent == null)\n                    this._root = current.Left;\n                else\n                {\n                    result = parent.Value.CompareTo(current.Value);\n                    if (result &gt; 0)\n                    {\n                        parent.Left = current.Left;\n                    }\n                    else if (result &lt; 0)\n                    {\n                        parent.Right = current.Left;\n                    }\n                }\n            }\n            else if (current.Right.Left == null)\n            {\n                if (parent == null)\n                    this._root = current.Right;\n                else\n                {\n                    result = parent.Value.CompareTo(current.Value);\n                    if (result &gt; 0)\n                    {\n                        parent.Left = current.Right;\n                    }\n                    else if (result &lt; 0)\n                    {\n                        parent.Right = current.Right;\n                    }\n                }\n            }\n            else\n            {\n\n                BSTNode&lt;T&gt; furthestLeft = current.Right.Left;\n                BSTNode&lt;T&gt; furthestLeftParent = current.Right;\n\n                while (furthestLeft.Left != null)\n                {\n                    furthestLeftParent = furthestLeft;\n                    furthestLeft = furthestLeft.Left;\n                }\n\n                furthestLeftParent.Left = furthestLeft.Right;\n\n                furthestLeft.Left = current.Left;\n                furthestLeft.Right = current.Right;\n\n                if (parent != null)\n                {\n                    result = parent.Value.CompareTo(current.Value);\n                    if (result &gt; 0)\n                    {\n                        parent.Left = furthestLeft;\n                    }\n                    else if (result &lt; 0)\n                    {\n                        parent.Right = furthestLeft;\n                    }\n                }\n                else\n                {\n                    this._root = furthestLeft;\n                }\n            }\n\n            this._count--;\n        }\n    }\n}\n</code></pre>\n'}, {'answer_id': 49375, 'author': 'rudigrobler', 'author_id': 5147, 'author_profile': 'https://Stackoverflow.com/users/5147', 'pm_score': 1, 'selected': False, 'text': '<p>Check out <a href="https://github.com/SSCLI" rel="nofollow noreferrer">Rotor 2</a> or use <a href="https://www.red-gate.com/products/dotnet-development/reflector/" rel="nofollow noreferrer">reflector</a> too see how Microsoft did it!!!</p>\n\n<p>also you can check <a href="https://referencesource.microsoft.com/#mscorlib/system/collections/generic/list.cs" rel="nofollow noreferrer">Microsoft reference source</a></p>\n'}, {'answer_id': 459149, 'author': 'Robert Claypool', 'author_id': 23566, 'author_profile': 'https://Stackoverflow.com/users/23566', 'pm_score': 2, 'selected': False, 'text': '<p><a href="https://github.com/ngenerics/ngenerics" rel="nofollow noreferrer">NGenerics</a></p>\n\n<p>"A class library providing generic data structures and algorithms not implemented in the standard .NET framework."</p>\n'}]
['https://Stackoverflow.com/questions/48307', 'https://Stackoverflow.com', 'https://Stackoverflow.com/users/3394/']