loading...
Cover image for Fundamental Data Structures and Algorithms in C#

Fundamental Data Structures and Algorithms in C#

adavidoaiei profile image Adavidoaiei Dumitru-Cornel Updated on ・8 min read

Stack
Queue
Linked List
Hashtable
Binary Search
Binary Search Tree
Graphs
Sorting Algorithms

The importance of the algorithms complexity is given by the fact that it tells us if the code is scaling. Most fundamental data structures and algorithms are already implemented in the .NET Framework, it is important to know how these data structures work and what time, memory complexity they have for the basic operations: accessing element, searching element, deleting element, adding element.


To get an idea of ​​what a good complexity means and a less good one we have the following chart:

In the .NET Framework we have implemented the following data structures: array, stack, queue, linked list and algorithms: binary search, the rest which we do not find in the .NET Framework can be found in NuGet packages or on GitHub. Array is one of the most used and well-known data structures and I will not go into detail with the operating principle.

Stack

Stack is a data structure implemented in the .NET Framework in two ways, simple stack in System.Collections namespace, and stack as generic data structure in System.Collections.Generic namespace, the principle of stack structure operation is LIFO (last in first out), the last element entered first out.


Example of using simple stack from the namespace System.Collections:


Example of using generic stack from the namespace System.Collections.Generic:

Stack applications:
  • undo / redo functionality
  • word reversal
  • stack back/forward on browsers
  • backtracking algorithms
  • bracket verification

Queue

Queue is a data structure implemented in the .NET Framework in two ways, the simple queue in System.Collections namespace, and the queue as the generic data structure in System.Collections.Generic namespace, the working principle of queue structures is FIFO (first in first out), the first element entered first out.

Example of using the simple queue from the namespace System.Collections:


Example of using the generic queue from the namespace System.Collections.Generic:

Real life example of queue:
The system from the point of sale of a restaurant.

Linked List

Linked List is a data structure implemented in the .NET Framework as a generic data structure in System.Collections.Generic namespace, the principle of functioning of the linked list structures is that each node in the list has a reference to the next node, except the tail of the list, which has no reference to the next node.

An example of search in linked list of the third item starting from the end:

Example of using the generic linked list from namespace System.Collections.Generic:

Hashtable

Hashtable is a data structure implemented in the .NET Framework in two ways, simple Hashtable in the namespace System.Collections and as generic data structure Dictionary in System.Collections.Generic namespace, it is recommended to use Dictionary instead of Hashtable, the working principle of Hashtable and Dictionary is that construct a hash that is index into an array usually using polynomials. Searching in a Hashtable and Dictionary has the complexity of time O(1).

Example of using generic Dictionary from System.Collections.Generic namespace:


Hashtable applications:
  • is used in fast data lookup - the compiler symbol table
  • indexing the database
  • caches
  • unique data representation

Of course, the .NET Framework contains several data structures optimized for certain problems, the purpose of this article is not to present all data structures from .NET Framework, I presented only common data structures from courses of algorithms and data structures.

Binary Search

Search algorithms are another topic in the courses of algorithms and data structures, we can use sequential search with O(n) complexity, or binary search with O(log n) complexity if the elements are sorted.
The idea behind binary search is that we access the middle element and compare with the searched one if it is smaller repeats the recursive process for the first half, otherwise it is searching in the second half, the binary search in the .NET Framework is implemented with Array.BinarySearch.

An example of using binary search using the Array.BinarySearch method in the .NET Framework:

Binary Search Tree

A GitHub repository with custom implementations for most data structures: https://github.com/aalhour/C-Sharp-Algorithms.
I will continue to present a binary search tree. The idea is to have a node root, each node has at most two child nodes, the one on the left is smaller than the root, as well as the left subtree, the right node is larger than the root, so is the right subtree.
Example of binary tree construction:

Searching in a binary search tree has the complexity of time O(log n) , example of searching in binary tree:

Binary search tree traversal:
Preorder

  • Root through
  • Go through the left subtree
  • Go through the right subtree

Inorder

  • Go through the left subtree
  • Root through
  • Go through the right subtree

Postorder

  • Go through the left subtree
  • Go through the right subtree
  • Root through

In the .NET Framework , the SortedList data structure uses internally a binary tree to keep the sorted elements.

Graphs

The graphs are data structures characterized by nodes and edges joining the nodes, usually using the notation G = (V, E) where, V represents the set of nodes (vertices, vertices), and E represents the set of edges (edges), in the programming language is represented by adjacency matrices for example a [i, j] = k, this means that between node i and j we have an edge with weight k, and adjacent lists are also used for their representation.


The graphs and trees can also be crossed in breadth(BREADTH FIRST) with a queue, depth(DEPTH FIRST) with a stack.

An implementation of the DEPTH FIRST algorithm of a graph in C# with recursivity:


An implementation of the BREATH FIRST algorithm of a graph in C# with a queue:

Sorting Algorithms

Sorting algorithms are another topic from the courses of algorithms and data structures, a table with their complexities:

Posted on by:

Discussion

markdown guide