Circular linkedlist in C#

 class CustomCircularLinkedList<T>
    {
        public CircularLinkedListItem<T> RootNode;
        public int Count { set; get; }

        public void Add(T value)
        {
            CircularLinkedListItem<T> newNode = new CircularLinkedListItem<T>(value);

            if (RootNode == null)
            {
                this.RootNode = newNode;
                Count++;
                return;
            }

            CircularLinkedListItem<T> node = this.RootNode;

            while (node.NextNode != null)
            {
                node = node.NextNode;
            }

            node.NextNode = newNode;
            newNode.PreviousNode = node;
//This distinguishes double and circular linkedlist
            this.RootNode.PreviousNode = newNode;
        }
    }

    class CircularLinkedListItem<T>
    {
        public CircularLinkedListItem<T> PreviousNode { set; get; }
        public CircularLinkedListItem<T> NextNode { set; get; }
        public T NodeItem { set; get; }

        public CircularLinkedListItem(T value)
        {
            this.NodeItem = value;
        }
    }

Double Linkedlist in C#

class CustomDoubleLinkedList<T>
    {
        private CustomDoubleLinkedListItem<T> RootNode;

        public int Count { set; get; }

        public void AddValue(T value)
        {
            CustomDoubleLinkedListItem<T> CustomDoubleLinkedListItemReference = new CustomDoubleLinkedListItem<T>(value);

            if (RootNode == null)
            {               
                RootNode = CustomDoubleLinkedListItemReference;
                RootNode.PreviousNode = null;
                Count++;
                return;
            }

            CustomDoubleLinkedListItem<T> nextNodeReference= this.RootNode;

            while (nextNodeReference.NextNode != null)
            {               
                nextNodeReference = nextNodeReference.NextNode;
            }
           
            nextNodeReference.NextNode = CustomDoubleLinkedListItemReference;
            CustomDoubleLinkedListItemReference.PreviousNode = nextNodeReference;
        }

        public void InsertAt(T value, uint position)
        {

            if (position > Count)
            {
                throw new InvalidOperationException("Position cannot be greater than link nodes");
            }

            int tempCount = 0;
            CustomDoubleLinkedListItem<T> CustomDoubleLinkedListItemReference = new CustomDoubleLinkedListItem<T>(value);
            CustomDoubleLinkedListItem<T> node = this.RootNode;

            while (tempCount != position && node.NextNode != null)
            {
                node = node.NextNode;
            }

            if (node == this.RootNode)
            {
                CustomDoubleLinkedListItemReference.PreviousNode = null;
            }
            else
            {
                CustomDoubleLinkedListItemReference.PreviousNode = node.PreviousNode;
            }

            CustomDoubleLinkedListItemReference.NextNode = node;
        }

        public void ReverseList()
        {
            CustomDoubleLinkedListItem<T> node = this.RootNode.NextNode;
            CustomDoubleLinkedListItem<T> previousNode;
            CustomDoubleLinkedListItem<T> nextNode;
            while (node != null)
            {
                nextNode = node.PreviousNode;
                previousNode = node.NextNode;
                node.PreviousNode = previousNode;
                node.NextNode = nextNode;

                //Handle the old root
                if (previousNode == null)
                {
                    previousNode = this.RootNode.NextNode;
                    this.RootNode.NextNode = null;
                    //Set the previous node
                    this.RootNode.PreviousNode = previousNode;
                    this.RootNode = node; 
                    previousNode = null;
                }

                if (previousNode == this.RootNode)
                {
                    node.PreviousNode = null;
                }

                node = previousNode;
            }           
        }


        public string DrawNode()
        {
            string output = String.Empty;

            if (RootNode.NextNode == null)
            {
                return RootNode.Value.ToString();
            }

            output = RootNode.Value.ToString();
            CustomDoubleLinkedListItem<T> nextNodeReference = this.RootNode.NextNode;

            while (nextNodeReference.NextNode != null)
            {
                output = String.Concat(output,",", nextNodeReference.PreviousNode.Value.ToString(), "->", nextNodeReference.Value);
                nextNodeReference = nextNodeReference.NextNode;
            }

            return output;
        }
    }

    class CustomDoubleLinkedListItem<T>
    {
        public CustomDoubleLinkedListItem<T> PreviousNode { set; get; }
        public CustomDoubleLinkedListItem<T> NextNode { set; get; }
        public T Value { set; get; }

        public CustomDoubleLinkedListItem(T customDoubleLinkedListItemValue)
        {
            this.Value = customDoubleLinkedListItemValue;
        }
    }

LinkedList

    class CustomSingleLinkedList<T>
    {
        private CustomLinkedListItem<T> rootNode;
        public int Count = 0;

        public void Add(T value)
        {
            CustomLinkedListItem<T> linkedListItem = new CustomLinkedListItem<T>(value);

            if (rootNode == null)
            {
                rootNode = linkedListItem;
                ++Count;
                return;
            }

            CustomLinkedListItem<T> previousNode = rootNode;

            while (previousNode.Reference != null)
            {
                previousNode = previousNode.Reference;               
            }

            previousNode.Reference = linkedListItem;
            ++Count;
        }


        public void InsertAt(T value, int position)
        {
            if (position > Count)
            {
                throw new IndexOutOfRangeException();
            }

            int tempCount = 0;
            CustomLinkedListItem<T> linkedListItem = new CustomLinkedListItem<T>(value);
            CustomLinkedListItem<T> node = rootNode;
            CustomLinkedListItem<T> tempnode = null;

            while (tempCount != position && node.Reference != null)
            {
                tempnode = node;
                node = node.Reference;
                tempCount++;
            }

            if (tempnode != null)
            {
                tempnode.Reference = linkedListItem;
            }
            else
            {
                this.rootNode = linkedListItem;
            }
           
            linkedListItem.Reference = node;          
        }

        public void ChangeValueAt(int position, T value)
        {
            int tempCount = 1;
            CustomLinkedListItem<T> node = rootNode;

            while (tempCount != position && node.Reference != null)
            {
                node = node.Reference;
                tempCount++;
            }

            node.Item = value;
        }

        public T ValueAt(int position)
        {
            T value = default(T);

            int tempCount = 1;
            CustomLinkedListItem<T> node = rootNode;

            while (tempCount != position && node.Reference != null)
            {
                node = node.Reference;
                tempCount++;
            }

            value = node.Item;
            return value;
        }

        public void ReverseLinkedList()
        {
            int tempCount = Count;

            for (int i = 1, j = tempCount; i < j; i++, j--)
            {
                T Temp = ValueAt(i);
                ChangeValueAt(i, ValueAt(j));
                ChangeValueAt(j, Temp);
            }
        }

        public T ReturnLastItem()
        {
            if (rootNode == null)
            {
                throw new InvalidOperationException("Root node is null");
            }

            if (rootNode.Reference == null)
            {
                return rootNode.Item;
            }

            CustomLinkedListItem<T> node = rootNode;

            while (node.Reference != null)
            {
                node = node.Reference;
            }

            return node.Item;
        }

        public void RemoveLastItem()
        {
            if (rootNode == null)
            {
                throw new InvalidOperationException("Root node is null");
            }

            if (rootNode.Reference == null)
            {
                rootNode = null;
                return;
            }

            CustomLinkedListItem<T> node = this.rootNode;
            CustomLinkedListItem<T> tempnode = null;

            while (node.Reference != null)
            {
                tempnode = node;
                node = node.Reference;
            }

            tempnode.Reference = null;
        }

        public void RemoveFirstItem()
        {
            if (rootNode == null)
            {
                throw new InvalidOperationException("Root node is null");
            }

            if (rootNode.Reference != null)
            {
                rootNode = rootNode.Reference;
            }
            else
            {
                rootNode = null;
            }
        }       
    }

    class CustomLinkedListItem<T>
    {
        public T Item { set; get; }
        public CustomLinkedListItem<T> Reference { set; get; }

        public CustomLinkedListItem(T item)
        {
            this.Item = item;
        }
    }

Implement stack from two que

class StackFromQue
    {
        private Queue<int> a = new Queue<int>();
        private Queue<int> b = new Queue<int>();

        //Optimize for Push operation
        public void Push(int value)
        {
            a.Enqueue(value);
        }

        public int Pop()
        {
            if (a.Count.Equals(0) && b.Count.Equals(0))
            {
                throw new InvalidOperationException("Empty stack");
            }

            if (a.Count > 0)
            {
                return PopOperation(a, b);
            }
            else
            {
                return PopOperation(b, a);
            }
        }

        private int PopOperation(Queue<int> first, Queue<int> second)
        {
            while (first.Count > 1)
            {
                second.Enqueue(first.Dequeue());
            }

            return first.Dequeue();
        }
    }

Explanation:

1. For Push operation, Enque all the values in Que 1.

2. For Pop opeartion, deque all the values from the current que into the next que until there is only one value in the current que. Return the last value and deque them. For the next value swap the ques.

Note: This is optimized for Push operation. It can be optimized for Pop operation in the reverse manner.

Merge Sort in C#

Merge Sort in C#

 public int[] MergeSortAction(int[] input)
        {
            int inputArrayLength = input.Length;

            if (inputArrayLength.Equals(1))
            {
                return input;
            }

            int middle = inputArrayLength / 2;
            int[] left = new int[middle];
            int[] right = new int[inputArrayLength - middle];

            //for (int i = 0; i < middle; i++)
            //{
            //    left[i] = input[i];
            //}

            //for (int i = 0; i < inputArrayLength - middle; i++)
            //{
            //    right[i] = input[i + middle];
            //}

            Array.Copy(input, 0, left, 0, middle);
            Array.Copy(input, middle, right, 0, inputArrayLength - middle);

            left = MergeSortAction(left);
            right = MergeSortAction(right);
           
            int[] sortedArray = new int[inputArrayLength];
            int leftp = 0;
            int rightp = 0;

            for (int count = 0; count < inputArrayLength; count++)
            {
                if (rightp == right.Length || (leftp < left.Length && left[leftp] <= right[rightp]))
                {
                    sortedArray[count] = left[leftp];
                    leftp++;
                }
                else if (leftp == left.Length || (rightp < right.Length && right[rightp] <= left[leftp]))
                {
                    sortedArray[count] = right[rightp];
                    rightp++;
                }
            }

            return sortedArray;
        }

Quick Sort in C#

Quick Sort in C#

public List<int> QuickSortAction(List<int> input, int left, int right)
        {         
            int i = left;
            int j = right;
            int pivotValue = input[(left + right) / 2];
            int temp = 0;

            while (i <= j)
            {
                while (input[i] < pivotValue)
                {
                    i++;
                }
                while (pivotValue < input[j])
                {
                    j--;
                }
                if (i <= j)
                {
                    temp = input[i];
                    input[i++] = input[j];
                    input[j--] = temp;
                }
            }

            if (left < j)
            {
                QuickSortAction(input, left, j);
            }

            if (i < right)
            {
                QuickSortAction(input, i, right);
            }

            return input;
        }