Firat Atagun

Virtual methods in C# are slower than non-virtual methods due to the following reasons :

• Virtual methods use callvirt instruction which does more checking on the type such as null checking for the this operand. Non-virtual methods use call instruction which doesn’t do any extra checking on the type.
• Calling a virtual method requires CLR to find the type of the method, and CLR must further scan the table of the types to check if there is base type of subtype of the class which has the virtual method.
• Calling a virtual method is slower than non-virtual method.
• Virtual methods can not be inlined by JIT. Inlining is an optimization done by JIT.
• Using virtual methods make versioning harder.
• in Java all the methods are virtual by default which hurts the performance.

Insertions to this ADT is O(1) which is faster than List and Arrays. Doesn’t require fragmented memory space so that s another efficiency. Searching is O(n), inserting to the middle is O(n). etc. There are lot of pros and cons of this ADT but in general, very useful.

I didnt add the null checks and invalidation of the nodes etc.

Stack and Queue implementations can use Doubly Linked List. Native implementations of Queue and Stack are using dynamic arrays or arrays, which requires fragmented memory space and re-allocation of arrays, which are expensive operations. Using Circular doubly linked list for Queue and Stack are much more efficient. Moreover, you can save space by using Circular Doubly Linked list compared to dynamic arrays and arrays, due to circular nature of this data structure.

using System;
using System.Collections;
using System.Collections.Generic;

namespace FiratAtagun.DataStructures
{
    public class Node where T : IComparable
    {

        public T Data { set; get; }
        public Node Next { set; get; }
        public Node Prev { set; get; }
        public bool IsHeadSentinel { set; get; }
        public bool IsTailSentinel { set; get; }

        public Node()
        {

        }

        public Node(T t, bool isHeadSentinel = false, bool isTailSentinel = false)
        {
            Data = t;
            IsHeadSentinel = isHeadSentinel;
            IsTailSentinel = isTailSentinel;
        }

    }

    public class CircularDoublyLinkedList : IEnumerable where T: IComparable
    {
        /*
         * TODO: Add BiDirectional nodes;
         * */

        #region Sentinels
        private readonly Node _headSentinel;
        private readonly Node _tailSentinel;
        #endregion

        #region Ctor
        public CircularDoublyLinkedList()
        {
            _headSentinel = new Node(default(T), true);

            _tailSentinel = new Node(default(T), isTailSentinel: true);

            _headSentinel.Prev = _tailSentinel;
            _headSentinel.Next = _tailSentinel;
            _tailSentinel.Prev = _headSentinel;
            _tailSentinel.Next = _headSentinel;
        }
        #endregion

        private int _count = 0;
        public int Count
        {
            get { return _count; }
        }

        public Node Find(T t)
        {
            return FindFirst(t);
        }

        public Node Find(Node node)
        {
            return FindFirst(node);
        }

        ///

        /// Finds the first occurence of T
        /// 

        ///

        /// 
        public Node FindFirst(T t)
        {
            return FindFirst(new Node(t));
        }

        public Node FindFirst(Node node)
        {
            var nodePointer = _headSentinel.Next;

            while (nodePointer.Data.CompareTo(node.Data) != 0)
            {
                nodePointer = nodePointer.Next;

                if (nodePointer.Next == _tailSentinel)
                {
                    return null;
                }
            }

            return nodePointer;
        }

        ///

        /// Finds the last Occurence of an T
        /// 

        ///

        /// 
        public Node FindLast(T t)
        {
            return FindLast(new Node(t));
        }

        public Node FindLast(Node node)
        {
            var nodePointer = _tailSentinel.Prev;

            while (nodePointer.Data.CompareTo(node.Data) != 0)
            {
                nodePointer = nodePointer.Prev;

                if (nodePointer.Prev == _headSentinel)
                {
                    return null;
                }
            }
            return nodePointer;
        }

        ///

        /// Adds a Node
        /// 

        ///

        public void Add(Node node)
        {
             if(_headSentinel.Next == _tailSentinel)
             {
                 _headSentinel.Next = node;

                 node.Prev = _headSentinel;
                 node.Next = _tailSentinel;
                 _tailSentinel.Prev = node;
                 return;
             }

            AddLast(node);
        }

        ///

        /// Adds a node by T
        /// 

        ///

        public void Add(T t)
        {
            Add(new Node(t));
        }

        ///

        /// Adds to the beginning of LinkedList
        /// 

        ///

        public void AddFirst(Node node)
        {
            if(_headSentinel.Next == null)
            {
                _headSentinel.Next = node;
                node.Prev = _headSentinel;
                return;
            }

            var tempNode = _headSentinel.Next;
            _headSentinel.Next.Prev = node;

            _headSentinel.Next = node;

            node.Next = tempNode;
            node.Prev = _headSentinel;
            _count++;
        }

        ///

        /// Add a node to the beginning of LinkedList By T
        /// 

        ///

        public void AddFirst(T t)
        {
            AddFirst(new Node(t));
        }

        ///

        /// Adds a node to the end of LinkedList
        /// 

        ///

        public void AddLast(Node node)
        {
            if(_tailSentinel.Prev == _headSentinel)
            {
                _tailSentinel.Prev = node;
                _headSentinel.Next = node;
                node.Next = _tailSentinel;
                node.Prev = _headSentinel;
            }

            var tempNode = _tailSentinel.Prev;

            _tailSentinel.Prev.Next = node;

            _tailSentinel.Prev = node;
            node.Next = _tailSentinel;
            node.Prev = tempNode;
            _count++;

        }

        ///

        /// Adds a node to the end of the list by T
        /// 

        ///

        public void AddLast(T t)
        {
            AddLast(new Node(t));
        }

        public void InsertAfter(Node nodeBefore, Node nodeToInsertAfter)
        {
            var node = Find(nodeBefore);
            var currentNext = node.Next;

            node.Next = nodeToInsertAfter;
            nodeToInsertAfter.Prev = node;
            nodeToInsertAfter.Next = currentNext;
            currentNext.Prev = nodeToInsertAfter;
            _count++;
        }

        public void InsertAfter(T t1, T t2)
        {
            InsertAfter(new Node(t1),new Node(t2) );
        }

        public void InsertAfter(Node node1, T t)
        {
            InsertAfter(node1, new Node(t));
        }

        public void InsertBefore(Node node1, Node nodeToInsert)
        {
            var node = Find(node1);
            var currentPrev = node.Prev;

            currentPrev.Next = nodeToInsert;
            nodeToInsert.Prev = currentPrev;
            nodeToInsert.Next = node;
            node.Prev = nodeToInsert;
            _count++;
        }

        public void InsertBefore(T t1, T t2)
        {
            InsertBefore(new Node(t1), t2);
        }

        public void InsertBefore(Node node1, T t)
        {
            InsertBefore(node1, new Node(t));
        }

        ///

        /// Removes the first node
        /// 

        public void RemoveFirst()
        {
            var nodeToRemove = _headSentinel.Next;

            var nodeToBeFirst = nodeToRemove.Next;

            _headSentinel.Next = nodeToBeFirst;
            nodeToBeFirst.Prev = _headSentinel;
            _count--;
        }

        ///

        /// Removes the last node
        /// 

        public void RemoveLast()
        {
            var nodeToRemove = _tailSentinel.Prev;

            var nodeToBeLast = nodeToRemove.Prev;

            _tailSentinel.Prev = nodeToBeLast;
            nodeToBeLast.Next = _tailSentinel;
            _count--;
        }

        ///

        /// Disconnects the first occurence of a node
        /// Same as removing a node's first occurence from the list
        /// 

        ///

        public void Disconnect(Node node)
        {

            var nodeToDisconnet = Find(node);

            var nextNode = nodeToDisconnet.Next;
            var prevNode = nodeToDisconnet.Prev;

            prevNode.Next = nextNode;
            nextNode.Prev = prevNode;
            _count--;
        }

        public void Disconnect(T t)
        {
            Disconnect(new Node(t));
        }

        ///

        /// TODO : Remove all occurences of a given T in a single pass.
        /// 

        public void Clear()
        {
            _headSentinel.Next = _tailSentinel;
            _tailSentinel.Prev = _headSentinel;
            _headSentinel.Prev = _tailSentinel;
            _tailSentinel.Next = _headSentinel;
            _count = 0;
        }

        ///

        /// From End to beginning enumerator
        /// 

        public IEnumerable FromEndToBeginning
        {
            get
            {
                var node = _tailSentinel.Prev;
                while(node != _headSentinel)
                {
                    yield return node.Data;
                    node = node.Prev;
                }
            }
        }

        #region IEnumerable Members

        public IEnumerator GetEnumerator()
        {
            Node node = _headSentinel.Next;
            while(node != _tailSentinel)
            {
                yield return node.Data;
                node = node.Next;

            }
        }

        #endregion

        #region IEnumerable Members

        IEnumerator IEnumerable.GetEnumerator()
        {
            return GetEnumerator();
        }

        #endregion
    }
}

Double ended queue, dequeue, is one of the nicest data structures I like. It can be implemented efficiently using doubly linked list as well as singly linked list. There are other implementations which uses arrays and lists.

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;

namespace FiratAtagun.DataStructures
{
    public class MyDeck : IEnumerable
    {

        private LinkedList data;

        public MyDeck()
        {
            data = new LinkedList();
        }

        public MyDeck(IEnumerable collection)
        {
            data = new LinkedList(collection);
        }

        public void OfferLast(T item)
        {
            data.AddLast(item);
        }

        public T PollLast()
        {
            var lastItem = data.Last;
            data.RemoveLast();
            return lastItem.Value;
        }

        public void OfferFirst(T item)
        {
            data.AddFirst(item);
        }

        public T PollFirst()
        {
            var firstItem = data.First;
            data.RemoveFirst();
            return firstItem.Value;
        }

        public T PeekLast()
        {
            return data.Last.Value;
        }

        public T PeekFirst()
        {
            return data.First.Value;
        }

        public T Find(T item)
        {
            return data.Find(item).Value;
        }

        public IEnumerable FirstN(int distance)
        {
            return data.Take(distance);
        }

        public IEnumerable LastN(int distance)
        {
            return data.Skip(data.Count - distance);
        }

        #region IEnumerable Members

        public IEnumerator GetEnumerator()
        {
            return new MyDeckEnumerator(data);
        }

        #endregion

        #region IEnumerable Members

        System.Collections.IEnumerator System.Collections.IEnumerable.GetEnumerator()
        {
            return GetEnumerator();
        }

        #endregion

        private class MyDeckEnumerator : IEnumerator
        {

            private readonly LinkedList data;
            private LinkedListNode CurrentItem;

            public MyDeckEnumerator(LinkedList linkedList)
            {
                data = linkedList;
            }

            #region IEnumerator Members

            public T Current
            {
                get { return CurrentItem.Value; }
            }

            #endregion

            #region IDisposable Members

            public void Dispose()
            {
               // throw new NotImplementedException();
            }

            #endregion

            #region IEnumerator Members

            object System.Collections.IEnumerator.Current
            {
                get { return CurrentItem.Value; }
            }

            public bool MoveNext()
            {
                if(CurrentItem != data.Last)
                {
                    if(CurrentItem == null)
                    {
                        CurrentItem = data.First;
                        return true;
                    }
                    CurrentItem = CurrentItem.Next;
                    return true;
                }
                return false;
            }

            public void Reset()
            {
                CurrentItem = data.First;
            }

            #endregion
        }
    }
}

Nullable types apply to structs. Objects already are able to assigned null values, therefore it doesnt make sense an object to be a valuable. That being said, Nullable<T> is equivalent to T?.

Eg:

Nullable num = null;
Nullable dateTime = null;
int? number= null;
DateTime? myBday = null;

Two read-only properties of Nullable are : HasValue , Value. HasValue property returns a boolean if the Nullable has a value otherwise returns false. Value read-only property accesses the value of the Type. There is also a method GetValueOrDefault, which returns the Value of the Type of returns the default value of the type.

A complementary operator to Nullable types is ??.

Conversions from a Nullable type to related type is possible, however might cause an exception.

int? num = null;

int num2 = (int)num; // this would cause an exception cause num is null.

For comparison operators <,>,== etc., nullable types can not be compared with a type that has a value.

int? num= null;
int num2 = 10;
if(num<num2) // you cant compare a value with null hence returns false.
{

}

?? operator comes to help if you need to evaluate a value with null and assign something to it:
eg:

int? num = null;
int result = num ?? 100;

This mean, if num is null then assing 100 to the variable.

You can also chain ?? operator as follows :
int num = null ?? null ?? 1;

Boxing and UnBoxing is possible for Nullable Types as follows :

int? num = null;
object o = num; // boxing

int? newNum = (int?) o; //unboxing

bool? bl = null; // this is possible, a boolean variable can be true, false and null.

object? ob = bl; // boxing, now ob object is null
bool? newbl = (bool?)ob; // unboxing, newbl is assigned to null

// Best practice to cast a bool? to bool  is as follows :

bool? b = null;

if(b.HasValue)
{
// use b.Value
}
else
{
// b doenst have a value, ie: null.
}

Interfaces can contain events, indexers, methods, and properties. Interfaces doesnt contain and implementation. Classes and structs can implement more than one interface. Interfaces can implement multiple interfaces.

Explicit interface implementation can not be overridden by a derived class unlike implicit interface implementation.

If an object is implementation two different interfaces which have the same method names, explicit interfaces can be used to avoid collision.

Generic interfaces are more efficient than regular interfaces cause, they eliminate boxing and unboxing.

if a type doesn’t have a IS-A relationship use, interfaces which is CAN-DO relationship.

It is usually easier to implement inheritance than interfaces, because you can build a base class and inherit all the functionality from it, on contrary, you need to implement all the method from interface if you implement it. so it is usually more work.

Interface implementations for all types might be problematic, for example type A, can implement the interface quite well, however type B, can implement the interface with bugs, which might cause a problem.

If you add a method to the base class, inherited classes automatically can implement that method, so any change to the base class can be seen by derived classes, however, if you make a change to an interface you need to make the change all the classes that implements that interface which is more tedious.

If there is not much code share between types, using interfaces makes more sense. If there s a lot to share between types, inheritance makes sense.