This article covers different data structures and how to implement them from the ground.

This article will try no to cover List<T>, Dictionary<T> or any other data structure included in the .NET Framework but implementing a Class that achieve the same result in an optimal way.

## Linked List

There are different kind of Linked list, we will start with the Singly Linked List.

A singly linked list is a series of Nodes linked in a sequence from the head node to the tail node.

Includes the following elements.

**Head**. First element of the list if any.
**Tail**. Last element of the list, may be equals to head when only one node is available.
**Nodes**. Node that contains a reference to a child and a value.

Insertion is fast since we know the tail we can just directly insert a new element in the list.

It’s considered a list with a dynamic size since we can always add elements to the list. The list can grow indefinitely. Compared to arrays that always have a fixed size.

The .NET framework has List<> and LinkedList<>, for the purposes of this post we will not cover these data types but create own classes using base data types.

**Insert**

Since we already know the tail we just add the new node as a child of the tail and the new tail is the added element. Insertion of nodes for linked list are assumed that it will be a new tail and head keeps intact.

**Search**

We start searching from head and go over its children and grand children and so on until we find the value or we end without results.

**Delete**

There are many scenarios when deleting nodes. The easiest scenario is to delete the head, we make the new head the child’s head.

**Traverse the Linked List**

It’s an easy operation, we just navigate from head to tail, node by note.

**Traverse in reverse**

An algorithm to do a traverse in revers will be put here.

**Doubly Linked List**

It’s a list that contains reference to the child and parent node, in other words node.NextNode and node.PreviousNode. With this kind of linked list doing a reverse traverse is much more efficient compared to a singly linked list.

If we plan to insert a node we need to take into account to update the Previous node and Next node.

This is all by know in regards linked list.

## Binary Search Tree (BST)

Below is an example of a Binary Search Tree, it’s also known as an Unbalanced Binary Search Tree

5
/ \
3 7
\ \
4 8
\
10
/
9

The logic of this data structure is this.

- There only a parent node
- Nodes can have at most 2 child nodes, left and right
- Left node always will be lower than parent, right node the opposite

**Insert Nodes**

To insert nodes we will use a recursive method to repetitively compare either if the inserted value is lower or greater than current node and to check if there is already a left or right child, if there is already a child we send the child as input to the recursive array.

[A CODE EXAMPLE OF INSERTION WILL BE HERE]

**Search Node**

We have also a recursive array that looks for a value until it can find it or reach the end of the array.

[Insert c# algorithm here]

**Delete Node**

Delete a node is a little more complex and you will need to do more validations.

[Insert algorithm here]

**Other tasks**

There are other tasks that you can perform for a BST, some of them are listed below.

- Find node
- Find node´s parent
- Find greatest and smallest value in BST