C# Tutorial Lesson 25: Linked List

We have learned enough C# machinery to write a simple data structure - linked list. Linked lists are used to save memory at a loss of speed. The are many different implementations of linked lists. The one bellow has a head node and a tail node. These are dummy nodes which point to the first and last elements of the list respectively. List is empty when the head node points to the tail node. The tail node points to itself.

using System;
class OutOfRange: Exception{}
class ListNode
{
    public int data;
    public ListNode next;
};
class List
{
    ListNode headnode, tailnode;
    //list constructor initializes headnode with 0 and makes it point to the tail marker
    //headnode and tailnode do not contain any actual elements; tailnode always points to itself
    public List ()
    {
        headnode = new ListNode (); // List constructor allocates memory for headnode and tailnode
        headnode.data = 0;
        //and does the initialization
        tailnode = new ListNode ();
        tailnode.data = 0;
        headnode.next = tailnode;
        tailnode.next = tailnode;
    }
    // *move_to_node returns pointer to the kth element in the linked list or error if list
    //has less than k elements; headnode and tailnode are not counted as elements of the list
    public ListNode move_to_node (int k)
    {
        int i;
        ListNode temp = headnode;
        for (i = 0; i < k && temp != tailnode; i++)
        {
            temp = temp.next;
        }
        try {
            if (i < k)
                throw (new OutOfRange() );
        }
        catch (Exception e)
        {
            Console.WriteLine("Exception :{}", e);
        }
        return temp;
    }
 
    //insert node a_node after position k.headnode has 0s position;

    public void insert_node (ListNode a_node, int position)
    {
        a_node.next = move_to_node(position).next;
        move_to_node(position).next = a_node;
     }
     //delete node at position and reclaim its memory
 
    public void delete_node (int position)
    {
        //check that a_node is not a headnode or a tailnode; exit if it is
         try
        {
            if (position == 0 || position > list_length ()) // Headnode or tailnode cannot be deleted
                 throw (new OutOfRange());
        }
        catch (Exception e)
        {
             Console.WriteLine("Exception :{}", e);
        }
 
        ListNode temp;
        temp = move_to_node (position);
        move_to_node (position - 1).next = move_to_node (position + 1);
    }
    //return # of elements in the linked list excluding headnode and tailnode
    public int list_length()
    {
        int i;
        ListNode temp = headnode;
        for (i = 0; temp != tailnode; i++)
        {
            temp = temp.next;
         }
        return i - 1;
    }
    //return 1 position of integer k in list of length n
    int search(int k, int n)
    {
        try {
            if (list_length () > 0) // this assertion cheks that list exist
                 throw (new OutOfRange() );
        }
        catch (Exception e)
        {
            Console.WriteLine ("Exception :{}", e);
        }
        ListNode temp = headnode;
        temp = headnode.next;
        // move along the list till integer k is found or tailnode encountered
        for (; temp.data != k && temp != tailnode; temp = temp.next)
            ;
        if (temp == tailnode)
        {
            // k is not in the list
            return 0;
        }
        else {
            // k is in the list;
            return 1;
        }
    }
    public void show_list()
    {
        ListNode temp = headnode;
        temp = headnode.next;
        for (; temp != tailnode; temp = temp.next)
            Console.WriteLine (temp.data);
    }
};
 

class Test{
    public static void Main ()
    {
        List first_list = new List ();
        ListNode node = new ListNode ();
        node.data = 1;
        first_list.insert_node (node, 0); // insert first node into list
        for (int i = 2; i < 11; i++) { // insert 9 more nodes
            node = new ListNode ();
            node.data = i;
            first_list.insert_node (node, 0);
        }
        first_list.show_list (); //show contents of the list
    }
}

Note how similar above implementation of the linked list to ones we have in C++. Just get rid of pointers, delete statements change cout to Console.WriteLine and you are ready to go.