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:

## Discussion