C# tutorial-circularly linked list


Circularly linked list

In this example you will learn to create a circularly linked list in C# programming language by using C# Objected-Oriented Programming concept.

The circularly linked list is much similar to the singly linked list, except that in the circularly linked list, the last element of the list points to the first element of the list. By allowing the last element to point to the first element of the list, the all elements of the list are linked together circularly.

Circularly linked list in CSharp C#

In this solution to the exercise, we are going to build a circularly linkedlist that has two links--one(pfirst) points to the first element of the list and another one(plast) point to the last element of the list. The program also provides a menu of choices that a user can use do some operations on the linkedlist.

Circularly linkedlist operations menu in Csharp C#  

Element of circularly linked list

The circularly linked list element has two parts--data and pointer or link. Therefore, we define the the element of the circularly linked list by using a class that has two members--data and next link.

//C# code to define list element

//List element class
class ListNode<T> //T is the generic type.
{
   public ListNode(T elem) { val = elem; next = null; }
   public T val; //element data
   public ListNode<T> next;//next link
}

The operations of the list are outlined in the abstract Cls class:

 //List operations are outlined here and will be implemented by the

//CirLinkedList class

abstract class Cls<T>
{
   public void insert(T val, int pos) { } //insert a new element to the list
   public void delete(int pos) { }//delete an element from the list
   public void printlist() { }//print all elements of the list
   public ListNode<T> findmin() { return null; }//show min element
   public ListNode<T> findmax() { return null; }//show max element

}

Add a new element to circularly linked list

To add an element to the circularly linked list, you need to consider four things:

1. When the list is empty, to add a new element to the list, you only let the pfirst and plast point to the new element.

Csharp C# Add an item to the empty list  



 

 

 

2.If the new element is to be added to the beginning of  the list, you will need to let the next link of the new element points to the pfirst and then update the pfirst to point to the new element.

CSharp C# Add a new element at the beginning of the list  

 3. If the new element is to be added to the middle position of the list, you need to let a pointer point to the position immediately before the position that the new element will be placed in.

CSharp C# Add a new item in the middle of the list  

4. If the new element is to be added to the last of the list, you need to let the link of the plast point to the new element then update the plast to point the new element.

CSharp C# Add the new item to the last of the list  

Note: After the new element was inserted to the list, the next link of the plast is pointed to the pfirst. By doing this, all elements of the list are linked together circularly.

//C# code to add a new element to the circularly linkedlist

public void insert(T val, int pos)

            {

ListNode<T> newnode = new ListNode<T>(val);
int inserted = 1;
//empty list
if (pfirst == null && plast == null)
{
   pfirst = newnode;
   plast = newnode;
   Console.WriteLine("Inserted:{0}", newnode.val);
}

              //Insert at the beginning of the list

                else if (pos == 1)

                {

                    newnode.next = pfirst;

                    pfirst = newnode;

                    Console.WriteLine("Inserted:{0}", newnode.val);

                }

                //Insert in the middle of the list

                else if (pos > 1 && pos <= countelement())

                {

                    ListNode<T> ta;

                    ta = pfirst;

                    for (int t = 1; t < pos - 1; t = t + 1) { ta = ta.next; }

                    newnode.next = ta.next;

                    ta.next = newnode;

                    Console.WriteLine("Inserted:{0}", newnode.val);

 

                }

                else { inserted = 0; Console.WriteLine("Invalid position!"); }

                if (inserted != 0 && plast != null) plast.next = pfirst; //Make the circularly linked

 

            }

Count the number of elements of circularly linked list

To count all elements of the circularly linked list, we will need a loop to traverse through the circularly linked list. We will let a link (i) of ListElem type to point to the pfirst then move the link to its next element and increase the number of element(t) one at a time by using a while loop until the end of the circularly linked list is reached.

 

//C# code to count the number of elements in the list

public int countelement()

            {

                ListNode<T> i;

                int t = 0;

                if (pfirst != null)

                {

                    t = 1;

                    for (i = pfirst.next; i != pfirst; i = i.next)

                    {

                        t = t + 1;

                    }

 

                }

                return t;

            }

Delete an element of circularly linked list

To delete an element of the circularly linked list, you need to consider the followings:

1. If the element to be deleted is the first element of the list and the list contains only one element, you only need to assign null to the pfirst and plast links. If the element to be deleted is the first element of the list and the list contain more than one element, you need a temporary link to point to the pfirst then move the pfirst to point to its next element and set the temporary link to null.

C# Delete the first item of the list  

2. If the element to be deleted is in the middle of the list, you need a traversing link(temp) to point to the element before the element to be deleted and a temporary link(del) to point to the element to be deleted. Then let the next link of the traversing link to point to the next link of the temporary link. To handle situation where the element to be deleted is the last element of the list, you need to test whether the target element is equal to the plast. If it is really equal, you need to update the plast to point to the traversing link. Finally set the temporary link to null.

C# Delete middle item of the list  

//C# code to  delete an element of the circularly linked list

public void delete(int pos)

            {

                int deleted = 1;

                if (pfirst != null)

                { //make sure the list is not empty.

                    ListNode<T> tr, temp;

 

                    if (pos == 1)

                    {//delete the first element

                        if (countelement() == 1)

                        { //The list contains only one element

                            pfirst = null;

                            plast = null;

 

                        }

                        else

                        { //The list contains more than one element

                            tr = pfirst;

                            pfirst = pfirst.next;

                            tr = null;

                        }

                        Console.WriteLine("Deleted");

 

                    }

 

                    else if (pos > 1 && pos <= countelement())

                    {//delete middle element

                        tr = pfirst;

                        int i;

                        for (i = 1; i < pos - 1; i = i + 1) { tr = tr.next; } //move to the element staying before the target element to be deleted

                        temp = tr.next; //target element to be deleted

                        tr.next = temp.next;

                        if (temp.next == null) plast = tr; //delete last element

                        temp = null;

                        Console.WriteLine("Deleted");

 

                    }

 

                    else { deleted = 0; Console.WriteLine("Invalid position!"); }

                    if (deleted != 0 && plast != null) plast.next = pfirst; //keep the list circularly linked

 

                }

 

                else Console.WriteLine("No element found");

 

            }

Max and Min elements of Circularly Linked List

To find the minimum element of the circularly linked list, you need to compare each element of the list by allowing a min variable to point to the first element of the list then starting to compare its data with its next element. If the data of its next element is less than the data of the min, simply allow the min to catch the next element.

//Find min element

public ListNode<T> findmin()

 {

                ListNode<T> t, min; 

                min = pfirst;

            if (pfirst != null) //not empty list

                { //continue to find the min by comparison

                    t = pfirst.next;

                  while (t != pfirst)

                  {

                    if (t.val.ToString().CompareTo(min.val.ToString()) < 0) min = t;

                     t = t.next;

                    } 

                    return min;

                }

                else return null;  //empty list

            }

 

Finding the maximum element of the circularly linked list can be done similarly as finding the minimum element. You need to compare each element of the list by allowing a max variable to point to the first element of the list then starting to compare its data with its next element. If the data of its next element is greater than the data of the max, simply allow the max to catch the next element.


//Find max element

public ListNode<T> findmax()

{

       ListNode<T> t, max; 

       max = pfirst;

       if (pfirst != null) //not empty list

        { //continue to find the max element by comparison

           t = pfirst.next;

           while (t != pfirst)

           {

             if (t.val.ToString().CompareTo(max.val.ToString()) > 0) max = t;

             t = t.next;

            } 

             return max;

         } 

                else return null;//empty list 

  }

 

Search an element in Circularly Linked List

Another important operation of the circularly linked list is searching for an element. To search for a specific element in the circularly linked list is a sequential process. The comparison starts from the beginning of the list until the target element is found or until the end of the list is reached. Therefore, the firs matched element is returned.

//Searching for an element in the circularly linked list

public ListNode<T> find(T tar)

            {

                ListNode<T> t; 

                bool f = false;

                if (pfirst != null)

                {

                    if (pfirst.val.ToString().CompareTo(tar.ToString()) == 0) return pfirst;//found at the beginning of the list 

                    else

                    {

                        t = pfirst.next;

                        while (t != pfirst)

                        {

                            if (t.val.ToString().CompareTo(tar.ToString()) == 0) { f = true; break; }

                            t = t.next;

                        } 

                    } 

                    if (f != false) return t;

                    else return null;

                }

                else return null;

            }

Print all elements of Circularly Linked List

To print all elements of the list is simple, you need to traverse through the list and output the data of each element.

//Print all elements of the Circularly Linked List

public void printlist()

 {

                ListNode<T> t;

                if (pfirst != null)

                {

                    Console.WriteLine(pfirst.val);                   

                    for (t = pfirst.next; t != pfirst; t = t.next)

                    {

                        Console.WriteLine(t.val);

                    }

                }

                else Console.WriteLine("No element found!");

 }

Display a menu of choices

To show the menu that allow the user to choose an operation on the linked list, you need the showmenu() and select() functions as shown below:

public static void select()

            {

                CirLinkedList<int> mylist = new CirLinkedList<int>();

                ListNode<int> temp;

                int val, ch, pos;

                char yes = 'y';

                //display menu

                showmenu();

                while (yes == 'y')

                {

                    Console.Write("Enter your choice:");

                    ch = int.Parse(Console.ReadLine().ToString());

                    switch (ch)

                    {

                        case 1:

                            Console.Write("Value:");

                            val = int.Parse(Console.ReadLine());

                            Console.Write("Position:");

                            pos = int.Parse(Console.ReadLine());

                            mylist.insert(val, pos);

                            break;

 

                        case 2:

                            Console.Write("Position:");

                            pos = int.Parse(Console.ReadLine());

                            mylist.delete(pos);

                            break;

 

                        case 3:

                            Console.WriteLine("Number of items:" + mylist.countitem());

                            break;

 

                        case 4:

                            if (mylist.findmax() != null && mylist.findmin() != null)

                                Console.WriteLine("Min item:{0}\nMax item:{1}", mylist.findmin().val, mylist.findmax().val);

                            break;

 

                        case 5: Console.Write("Find what?");

                            val = int.Parse(Console.ReadLine());

                            temp = mylist.find(val);

                            if (temp != null) Console.WriteLine("Found {0}", temp.val);

                            else Console.WriteLine("Not found"); break;

                        case 6:

                            Console.WriteLine("All items:");

                            mylist.printlist();

                            break;

 

                        case 7: Environment.Exit(0); break;

 

                        default: Console.WriteLine("Invalid choice!"); break;

 

                    }

                    Console.Write("Continue? Press y to continue:");

                    yes = char.Parse(Console.ReadLine());

 

                }

 

            }

 

public static void showmenu()

{

     Console.WriteLine("======================================");

     Console.WriteLine("Circularly LinkedList Operations Menu");

      Console.WriteLine("======================================");

      Console.WriteLine("1.Add a new item");

      Console.WriteLine("2.Delete an item");

      Console.WriteLine("3.Show number of items");

      Console.WriteLine("4.Show min and max items");

      Console.WriteLine("5.Find an item");

      Console.WriteLine("6.Show all items");

      Console.WriteLine("7.Exit");

 

            }

    }

Put the code together

This is the complete C# code of a circularly linked list data structure:




Comments

CAPTCHA image




This website intents to provide free and high quality tutorials, examples, exercises and solutions, questions and answers of programming and scripting languages:
C, C++, C#, Java, VB.NET, Python, VBA,PHP & Mysql, SQL, JSP, ASP.NET,HTML, CSS, JQuery, JavaScript and other applications such as MS Excel, MS Access, and MS Word. However, we don't guarantee all things of the web are accurate. If you find any error, please report it then we will take actions to correct it as soon as possible.