Tree Data structure in C Sharp .NET
Here is a simple Tree data structure in C sharp.NET
using System;
using System.Collections.Generic;
using System.Text;
namespace Algorithms
{
class Tree
{
private TreeNode root;
public Tree()
{
root = null;
}
public TreeNode FindRecursive(TreeNode root, int dataValue)
{
if (root == null)
{ return null; }
else if (root.DataValue == dataValue)
{ return root; }
else if (root.DataValue < dataValue)
{ return FindRecursive(root.RightNode, dataValue);}
else
{ return FindRecursive(root.LeftNode, dataValue);
}
}
public TreeNode Find(int dataValue)
{
if (root == null)
{
return null;
}
else
{
TreeNode currentNode = root;
while (currentNode != null)
{
if (currentNode.DataValue == dataValue)
{
return currentNode;
}
else if (currentNode.DataValue < dataValue)
{
currentNode = currentNode.RightNode;
}
else if (currentNode.DataValue > dataValue)
{
currentNode = currentNode.LeftNode;
}
return null;
}
return null;
}
}
}
public class TreeNode
{
private int dataValue;
private TreeNode leftNode = null;
private TreeNode rightNode = null;
public TreeNode(int data)
{
dataValue = data;
}
public TreeNode LeftNode
{
get
{
return leftNode;
}
set
{
leftNode = value;
}
}
public TreeNode RightNode
{
get
{
return rightNode;
}
set
{
rightNode = value;
}
}
public int DataValue
{
get
{
return dataValue;
}
set
{
dataValue = value;
}
}
}
}
Labels: CSharpTricks, DataStructures
Sunday, March 25, 2007
Check If Cycle exists in a Linked List
Check if the linked list contains a cycle
using System;
using System.Collections.Generic;
using System.Text;
namespace Algorithms
{
public class LinkedList
{
private Node head;
public LinkedList()
{
head = null;
}
public bool CheckCycle()
{
Node step1Node = head;
Node step2Node = head.NextNode;
while (true)
{
if ((step2Node == null)||(step2Node.NextNode == null))
return false;
else if ((step1Node.Equals(step2Node))||(step1Node.Equals(step2Node.NextNode)))
return true;
else
{
step2Node = step2Node.NextNode;
step2Node = step2Node.NextNode;
step1Node = step1Node.NextNode;
}
}
}
public int FindPosition(int data)
{
Node checkNode = head;
int position = 1;
int dataPosition = 0;
while (checkNode != null)
{
if (checkNode.DataValue == data)
{
dataPosition = position;
}
checkNode = checkNode.NextNode;
position = position + 1;
}
return dataPosition;
}
}
public class Node
{
private int dataValue;
private Node nextNode = null;
public Node(int data)
{
dataValue = data;
}
public Node NextNode
{
get
{
return nextNode;
}
set
{
nextNode = value;
}
}
public int DataValue
{
get
{
return dataValue;
}
set
{
dataValue = value;
}
}
}
}
Labels: CSharpTricks, DataStructures
Sunday, February 25, 2007
Nth Element from the last in a Linked List
Another advanced algorithm is to find the Nth Element from the LAST with the optimal performance.Here is the implementation
using System;
using System.Collections.Generic;
using System.Text;
namespace Algorithms
{
public class LinkedList
{
private Node head;
public LinkedList()
{
head = null;
}
public int FindNthElementFromLast(int m)
{
int n = m - 1;
int returnValue = -1;
if (n >= 0)
{
Node nthElement = head;
Node currentElement = head;
for (int i =0;i less than n;i++)
{
if (currentElement.NextNode != null)
{
currentElement = currentElement.NextNode;
}
else
{
returnValue = -1;
return returnValue;
}
}
if (returnValue != -1)
{
while (currentElement.NextNode != null)
{
currentElement = currentElement.NextNode;
nthElement = nthElement.NextNode;
}
returnValue = nthElement.DataValue;
}
}
return returnValue;
}
}
public class Node
{
private int dataValue;
private Node nextNode = null;
public Node(int data)
{
dataValue = data;
}
public Node NextNode
{
get
{
return nextNode;
}
set
{
nextNode = value;
}
}
public int DataValue
{
get
{
return dataValue;
}
set
{
dataValue = value;
}
}
}
}
Labels: CSharpTricks, DataStructures
Linked List SORT Algorithm
If you need a sort algorithm in Linked List. Please check other implementation in my last blog.
using System;
using System.Collections.Generic;
using System.Text;
namespace Algorithms
{
public class LinkedList
{
private Node head;
public LinkedList()
{
head = null;
}
public void Sort()
{
if (head != null)
{
int j = 0;
Node MinElement = head;
Node currentElement = MinElement.NextNode;
while (currentElement != null)
{
if (currentElement.DataValue < MinElement.DataValue)
{
MinElement = currentElement;
Insert(MinElement.DataValue);
DeleteAtPosition(j+1);
}
MinElement = MinElement.NextNode;
}
}
}
}
public class Node
{
private int dataValue;
private Node nextNode = null;
public Node(int data)
{
dataValue = data;
}
public Node NextNode
{
get
{
return nextNode;
}
set
{
nextNode = value;
}
}
public int DataValue
{
get
{
return dataValue;
}
set
{
dataValue = value;
}
}
}
}
Labels: CSharpTricks, DataStructures
Linked List in C Sharp.NET
I got tones of emails, lately for Linklist and Tree data structure implemetationHere is a simple Linked List Data structure in C Sharp.NET. A LinkedList will always have two class a LinkedList class and a Node Class.
I have also included most common options to insert and Delete nodes.
using System;
using System.Collections.Generic;
using System.Text;
namespace Algorithms
{
public class LinkedList
{
private Node head;
public LinkedList()
{
head = null;
}
public void Insert(int dataValue)
{
if (head == null)
{
Node nodeInsert = new Node(dataValue);
head = nodeInsert;
nodeInsert.NextNode = null;
}
else
{
Node nodeInsert = new Node(dataValue);
nodeInsert.NextNode = head;
head = nodeInsert;
}
}
public void InsertAtPosition(Node insertNode, int i)
{
if (i == 0)
{
insertNode.NextNode = head;
head = insertNode;
}
else
{
Node currentNode = head;
Node currentNodeNext = head.NextNode;
for (int j = 0; j < i; j++)
{
currentNode = currentNode.NextNode;
currentNodeNext = currentNode.NextNode;
}
if (currentNode != null)
{
currentNode.NextNode = insertNode;
insertNode.NextNode = currentNodeNext;
}
}
}
public void DeleteAtPosition(int i)
{
if (i == 0)
{
head = null;
}
else
{
Node currentNode = head;
Node currentNodeNext = head.NextNode;
for (int j = 0; j < i; j++)
{
currentNode = currentNode.NextNode;
currentNodeNext = currentNode.NextNode;
}
if (currentNode != null)
{
currentNode.NextNode = currentNodeNext.NextNode;
}
}
}
public bool Delete(Node nodeToDelete)
{
bool returnFlag = false;
if (head == null)
returnFlag = false;
else if (head.Equals(nodeToDelete))
{
head = null;
returnFlag = true;
}
else
{
Node checkNode = head;
Node checkNodeNext = head.NextNode;
while (checkNodeNext != null)
{
if (checkNodeNext.Equals(nodeToDelete))
{
checkNode.NextNode = checkNodeNext.NextNode;
checkNodeNext = null;
returnFlag = true;
}
}
}
return returnFlag;
}
public void Print()
{
Node firstNode = head;
while (firstNode != null)
{
Console.Write(firstNode.DataValue + " ");
firstNode = firstNode.NextNode;
}
}
public void Clear()
{
Node checkNode = head;
Node checkNodeNext;
while (checkNode != null)
{
checkNodeNext = checkNode.NextNode;
checkNode = null;
checkNode = checkNodeNext;
}
}
}
public class Node
{
private int dataValue;
private Node nextNode = null;
public Node(int data)
{
dataValue = data;
}
public Node NextNode
{
get
{
return nextNode;
}
set
{
nextNode = value;
}
}
public int DataValue
{
get
{
return dataValue;
}
set
{
dataValue = value;
}
}
}
}
Labels: CSharpTricks, DataStructures
Saturday, January 20, 2007
largest element in the array by comparing to All - C#
To find out the largest element in the array by comparing to All elements methodThis methd has an Big Oh notation performance of O(n2)
public static int GetIndexLargestCompareToAll(int[] numbers)
{
int currentMaxIndex = -1;
int length = numbers.Length;
bool isMax = false;
try
{
if (length == 0)
currentMaxIndex = -1;
else if (length == 1)
currentMaxIndex = 0;
else
{
for (int i = 0; i < length; i++)
{
isMax = true;
for (int j = 0; j < length; j++)
{
if (numbers[j] > numbers[i])
isMax = false;
}
if (isMax)
currentMaxIndex = i;
}
}
}
catch (Exception)
{
currentMaxIndex = -1;
}
return currentMaxIndex;
}
Labels: CSharpTricks, DataStructures, Technology
Sunday, June 25, 2006
Largest Element in the Array using C #
To find out the largest element in the array by comparing to the Max methodThis methd has an Big Oh notation performance of O(n)
public static int GetIndexLargestCompareToMax(int[] numbers)
{
int currentMaxIndex = -1;
int length = numbers.Length;
try
{
if (length == 0)
currentMaxIndex = -1;
else if (length == 1)
currentMaxIndex = 0;
else
{
currentMaxIndex = 0;
for (int j = 1; j < length; j++)
{
if (numbers[j] > numbers[currentMaxIndex])
{
currentMaxIndex = j;
}
}
}
}
catch (Exception)
{
currentMaxIndex = -1;
}
return currentMaxIndex;
}
Labels: CSharpTricks, DataStructures