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.

C# Queue uses Circular buffer internally. Using linear array or list is inefficient. Therefore Circular Buffer/ Circular array can be used to implement Queue. Also, Queue can be implemented using Linked List. Similaryly, Stack implementation can use Circular buffer or linked lists.

HashTable uses collision detection and collision avoidance to prevent collision of items inserted to it. HashTable uses linear probing and quadratic probing to do this. Linear probing works as following, while inserting an element to a hashtable, item’s hashcode is being calculated. if there is already an item with the same hashcode in the hastable, next item to the existing item is checked. if it s empty new item is inserted there. So it checks one item at a time next to the existing item until there is an empty spot. Quadratic probing work with squaring the element position and inserting the available spot. N + 1*1 , N + 2*2 , N+3*3 and so on.

Dictionary uses chaining for hashcode collision. This is one of the other difference between hashtable and dictionary the other being generics.  Chaining doesnt work like probing, instead of searching for an available slot, collided item is chained, attached to the existing item using a linked list (another data structure). Moreover, dictionary is much more efficient than stack, queue or list because of expansion strategy. While list doubles the size of the internal structure when it needs to resize, dictionary uses the next big prime number. Moreover, while inserting items to dictionary order is discarded, unlike list, queue or stack. Seaching for an element in dictionary is constant time O(1). where as in list or array, it takes linear time O(n). Therefore dictionaries are very efficient.

Moreover, Dictionaries can be used to compress, compact data and save memory. such as Huffman encoding.

In C#, Comparer<T> base class can be implemented and sub typed in order for ordering, such as sorting.

Since Comparer<T> base class implements IComparer, and IComparer<T>, you wont have to implement them. Also IComparer (non generic version is already implemented for you.). You will just create a new Comparer class that extends Comparar<T> base class. and implement the custom ordering functionality.

Lets say we have a Person class that have id and name properties. and we have a PersonComparerById as follows

public class Person
{
   public string Name { set; get; }
   public int id { set; get; }
}

public class PersonComparerById : Comparer<Person>
{

  public override int Compare(Person x, Person y)
  {
    if(ReferenceEquals(x,y) || x.id == y.id)
    {
      return 0;
    }

   return x.id.CompareTo(y.id);
  }
}

// And we have the following code set:

var persons = new List<Person>();
persons.Add(new Person { id = 3, Name = "serkan" });
persons.Add(new Person { id = 5, Name = "atagun" });
persons.Add(new Person { id = 2, Name = "firat" });

IComparer<Person> personComparer = new PersonComparerById();

persons.Sort(personComparer);

foreach (var person in persons)
{
    Console.WriteLine(person.Name);
}

The result would be

firat
serkan
atagun

in sorted order. Comparer<T> base class is used for custom ordering. It can be plugged to collections for ordering.

EqualityComparer is used for Hashtables and Dictionaries for custom equality comparison. You ll need to make a new class and implement base class EqualityComparer<T> which have two abstract methods namely, Equals(T t1, T t2) and getHashCode().

Next is to pass an instance of the custom EqualityComparer class to the collection.

class Person{
string Name{set;get;}
int id {set;get;}
}

class PersonEqualityComparer : EqualityComprarer{

public override bool Equals(Person a, Person b){

return a.id == b.id;

}

public override int GetHashCode(){

return id.getHashCode();

}

}

This class does the equality comparison based on Person’s Id.

IEqualityComparer<Person> comparer = new PersonEqualityComparer();

Dictionary<Person, string> collection = new Dictionary<Person, string>(comparer);

collection.add(new Person{ name =”serkan”, id=1});

collection.add(new Person{name=”serkan”, id= 1});

this statement would throw and exception due to duplicate keys. Which is expected.

Dictionary<Person, string> collection = new Dictionary<Person, string>();

collection.add(new Person{ name =”serkan”, id=1});

collection.add(new Person{name=”serkan”, id= 1});

However, this statements wouldnt throw an exception cause the default comparers use different hashcode and equality comparison.

Custom EqualityComparer classes are used with dictionary and hashtables.