Generic Programming in C#.Net


In C#.Net you can easily use templates in your classes to enable generic uses of objects. Take the simple linked list for example. You have a chain of Nodes, and the data inside the nodes is what will be generic. It could anything such as strings, integers, pointers, and abstract data types.

The following implementation of a singly liked list uses templates. I wrote this especially because linked lists is a popular type of data structure, and what better way to teach generic programming examples by also including data structures as well?

Please pay special attention to the syntax, commenting, and how various operators are overloaded. For example, if we wanted to test for equality between two nodes that have generic data, we need to overload both == and != and we have to dynamically cast generic types to be explicit with comparison.

    //we can create a template for a class or struct using the following syntax
    //class Name <generic variable name>
    class LinkedList <T>
    {
        class Node //Node class is nested inside Linked list, so it can use the generic type 'T'
        {
            public T data;
            public Node next;
            public Node(T data)
            {
                this.data = data;
                this.next = null;
            }
            //in order to compare certain objects, when templatizing, 
            //make sure to always overload necessary operators
            //for example, if you wanted the linked list to be in some ascending/descending order
            //overload ==, !=, <, >, etc...

            //in this case, we dont care about order
            public T getData()
            {
                return this.data;
            }
            //when we overload ==, we need to have dynamic casting comparing two generic types
            public static bool operator==(Node n1, T data)
            {
                return ((dynamic)n1.data == (dynamic)data);
            }
            public static bool operator !=(Node n1, T data)
            {
                return ((dynamic)n1.data != (dynamic)data);
            }
        }
        /*Note: for data structures or objects that require setting to null, 
         * you need to mark it as a class
         * */
        Node head;
        Node end;
        public LinkedList()
        {
            head = null;
            end = null;
        }
        public bool insert(T data)
        {
            //because we have an end pointer
            //we can insert in O(1)
            Node n = new Node(data);
            if (empty())
            {
                head = end = n;
                return true;
            }
            else
            {
                end.next = n;
                end = n;
                return true;
            }
        }
        public bool empty()
        {
            return (head == null);
        }
        public bool delete(T target)
        {
            if (empty())
            {
                return false;
            }
            Node current = head;
            Node temp = null;
            bool isDeleted = false;
            while (current != null && !isDeleted)
            {
                if (current.next == target)
                {
                    temp = current.next.next;
                    current.next = temp;
                    isDeleted = true;
                }
                else
                {
                    current = current.next;
                }
            }
            return isDeleted;
        }
        public bool removeFront()
        {
            if (empty())
            {
                return false;
            }
            else
            {
                if (head.next != null)
                {
                    head = head.next;
                }
                else
                {
                    head = end = null;
                }
                return true;
            }
        }
        public bool removeEnd()
        {
            if(empty())
            {
                return false;
            }
            Node current = head;
            while (current != null)
            {
                if (current.next.next == null)
                {
                    end = current.next;
                }
                else
                {
                    current = current.next;
                }
            }
            return true;
        }
        public bool find(T data)
        {
            Node current = head;
            Node target = new Node(data);
            while (current != null)
            {
                if (current == target)
                {
                    break;
                }
                else
                {
                    current = current.next;
                }
            }
            return true;
        }
        public void Display()
        {
            if (empty())
            {
                Console.WriteLine("Empty List!");
                return;
            }
            Node current = head;
            while (current != null)
            {
                Console.Write("{0}->", current.getData());
                current = current.next;
            }
            Console.Write("NULL");
            Console.WriteLine();
        }
    }
Advertisements

One thought on “Generic Programming in C#.Net

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s