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.
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.
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.
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.
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
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
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]
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 a node is a little more complex and you will need to do more validations.
[Insert algorithm here]
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