DataStructures

This repository contains implementations of 28 data structures in C#, plus the sorting, traversal, and pathfinding algorithms built on top of them.

Data structures included

#	Data structure	Class	Project	Notes
1	Array-backed list	MyList<T>	Generics	Generic list with add, index, and print
2	Singly linked list	SingleLinkedList<T>	SinglyLinkedList
3	Doubly linked circular list	DoublyCircularLinkedList<T>	DoublyCircularLinkedList	Add at index, remove, clear
4	Array-backed stack	ArrayStack<T>	Stack	Resizing array
5	Linked-list stack	LinkedListStack<T>	Stack	Built on SingleLinkedList<T>
6	Naive array stack	TrashAhh<T>	Stack	Deliberately inefficient variant
7	Array-backed queue	ArrayQueue<T>	Queues	Circular buffer with resize
8	Linked-list queue	LinkedListQueue<T>	Queues	Built on SingleLinkedList<T>
9	Binary search tree	BST<T>	Trees	Insert, remove, search, in/pre/post-order and breadth-first traversals
10	Binary search tree	BinarySearchTree<T>	BST	Second implementation, used by the burst trie
11	Binary heap	MyHeap<T>	Heap	Min-heap by default, custom IComparer<T>, static HeapSort
12	AVL tree	AVL<T>	AVL	Self-balancing BST with rotations
13	Skip list	SkipList<T>	SkipList	Probabilistic layered list
14	Undirected graph	BasicGraph<T>	Graphs	Adjacency lists, BFS/DFS traversal and pathfinding
15	Weighted directed graph	Graf<T>	WDGraph	BFS, DFS, Dijkstra, Bellman-Ford, A*
16	Weighted directed graph	Draf<T>	WDGraph	Earlier variant with Dertex/Dedge types, BFS, DFS, Dijkstra
17	Hash map	MonkeyHash<TKey, TValue>	Hash	Implements IDictionary<TKey, TValue> with bucket chaining
18	Bloom filter	BloomFilter<T>	BloomFilter	Pluggable hash functions, ProbablyContains
19	LRU cache	LRUCache<T>	LRUCache	Linked-list backed least-recently-used eviction
20	Huffman coding tree	HuffmanTree	HuffmanCoding	Builds the tree and encodes/decodes to a BitArray
21	Union-find (quick find)	QuickFind<T>	UnionFind
22	Union-find (quick union)	QuickUnion<T>	UnionFind
23	B-tree	BT<T>	BTree	Multi-way balanced tree with node splitting
24	Left-leaning red-black tree	RBTree<T>	RedBlackTree	Implements ISortedSet<T>; insert, remove, set operations
25	Burst trie	BurstTrie	BurstTrie	Trie whose containers are BinarySearchTree<string> and burst when full
26	Treap	Treap<T>	Treap	Randomised BST keyed by priority
27	Multi-level flattenable list	DataStructureThing<T>	WeirdDataStructure	Nodes with next and child links plus a Flatten operation
28	Enumerable binary string	BinaryString / BinaryEnumerator	BinaryEnumerator	Custom IEnumerable<char> / IEnumerator<char>

The Snake game also contains two game-specific structures, SnakeQueue and SegmentDoublyLinkedList, which are not counted above.

Algorithms included

Algorithm	Where
Bubble sort, selection sort, insertion sort	SimpleSorts/Program.cs
Merge sort	MoreRecursionPractice/RecurssiveSort.cs
Quick sort (Lomuto and Hoare partition)	RecursionPractices/QuickSort.cs
Heap sort	MyHeap<T>.HeapSort
Breadth-first and depth-first traversal and pathfinding	BasicGraph<T>, Graf<T>, Draf<T>
Dijkstra, Bellman-Ford, A*	Graf<T> (Dijkstra also in Draf<T>)
Huffman encoding and decoding	HuffmanTree
Recursion exercises (Fibonacci, countdown, array sum, string reverse, triangle)	Recursion/Program.cs

Layout

Each project targets net8.0.

Solution folder	Projects
01 SimpleSorting	SimpleSorts (bubble, selection, insertion sort)
02 Generics	Generics (MyList<T>)
03 OOPAndDotNET	BinaryEnumerator (IEnumerable<T> / yield), ComparerDemo (IComparer<T>)
04 LinkedLists	SinglyLinkedList, CircularDoublyLinkedList (only a Node<T> class, list never written), DoublyCircularLinkedList
05 StacksAndQueues	Stack (array + linked list), Queues (array + linked list), StacksAndQueuesTests, Snake (MonoGame game built on the queue and doubly linked list)
06 Trees	Trees (BST<T> with traversals), BST (BinarySearchTree<T>)
07 Recursion	Recursion, MoreRecursionPractice (merge sort), RecursionPractices (quick sort), RecursionTests
08 SelfBalancingTrees	Heap, AVL, SkipList, SelfBalancingTreesTests
09 Graphs	Graphs (undirected), WDGraph (weighted directed, Bellman-Ford, A*), GraphTests, WDGraphVisualizer, Visualizer (MonoGame)
10 AdvancedConcepts	Hash (MonkeyHash<TKey,TValue>), BloomFilter, LRUCache, HuffmanCoding, UnionFind (quick find), AdvancedConceptsTests, UnionFindVisualizer (WinForms)
11 AdvancedSelfBalancingTrees	BTree, RedBlackTree (left-leaning, implements ISortedSet<T>), SortedSet (demo Main only), RedBlackTreeTests, BurstTrie, BurstTrieTests
12 Extra	Treap, WeirdDataStructure

Extra/CppTreap and Extra/NewCPPTreap are C++ treap implementations kept for reference. They are not part of the .NET solution.

Building and testing

dotnet build DataStructures.sln

dotnet test DataStructures.sln

Requires the .NET 8 SDK or newer.