C# OOP: Singly Linked List

By using C# objected-oriented concept, create a singly linked list.
The singly linked list is a chain of its item. Each item contain two parts--data and a link. The data part is to store information and the link part of an item is used to point or to store the address of the next item.

You are going to build a singly linked list that has two links--one(pfirst) links to the first item of the list and another one(plast) point to the last item of the list. The program also provides a menu of choices that a user can use do some operations on the linked list data structure.
  
Solution: To keep the solution simple, we divide it in to different steps as you see their links on the right menu.

C# OOP: Singly Linked List



Element of singly linked list

Step 1: Define element of the singly linked list
The linked list element has two parts--data and a link. Therefore, we define the the element of the 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
}

C# OOP: Singly Linked List



Add element to list singly linked list

Step 2: Add an element to the linked list
To add an element to the linked list, you need to consider 4 things:
1. When the list is empty, to add a new element to the list, you only let the pfirst and plast links point to the new item. We mark the null value of link of an element by crossed lines.

 

2.If the new element is to be added to the beginning of  the list, you will need to let the link of the new item points to the pfirst and then update the pfirst to point to the new item.
  
 3. If the new element is to be added to the middle position of the list, you need to let a link point to the position immediately before the position that the new element will be placed in.
  
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.
  
//C# code to insert a new item to the linkedlist

public void insert(T val, int pos)
{
ListNode<T> newnode = new ListNode<T>(val);
//empty list
if (pfirst == null && plast == null)
{
 newnode.next = 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 <= countitem())
{
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 if (pos == countitem() + 1)
{
 newnode.next = null; //The next link of the item is null.
 plast.next = newnode;
 plast = newnode;
 Console.WriteLine("Inserted:{0}", newnode.val);

}
else Console.WriteLine("Invalid position!");


}

C# OOP: Singly Linked List



Count elements of the singly linked list

Step 3: Count elements of the singly linkedlist
To count all elements of the linkedlist, we will need a loop to traverse through the linkedlist. We will let a variable (i) of ListElem type to point to the pfirst then move to its next element and increase the number of item(t) one at a time by using a while loop until the end of the linkedlist(indicated by null value) is reached.

//C# code count items in the linked list
public int countitem()
{
ListNode<T> i;
int t = 0;
for (i = pfirst; i != null; i = i.next)
{
   t = t + 1;
}
return t;
}

C# OOP: Singly Linked List



Delete item of singly linked list

Step 4: Delete an element of the singly linked list
To delete an element of the 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. 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 variable to point to the pfirst then move the pfirst to point to its next element and set the temporary varialbe to null.
  
2. If the element to be deleted is in the middle of the list, you need a traversing variable(temp) to point to the element before the element to be deleted and a temporary variable(del) to point to the element to be deleted. Then let the link of the traversing pointer to point to the link of the temporary pointer. To handle situation where the element to be deleted is the last element of the list, you need to test whether the link of the temporary variable is null. If it is really null, you need to update the plast pointer to point to the traversing variable. Finally set the temporary pointer to null.
  
//C# code to delete an item from the linked list
public void delete(int pos)
{
if (countitem() > 0)
{ //make sure the list is not empty.
ListNode<T> temp,del;

if (pos == 1)
{//delete the first item
if(countitem()==1){ //The list contains only one item
pfirst=null;
plast=null;

}
else{ //The list contains more than one item
temp=pfirst;
pfirst=pfirst.next; 
temp=null;
}
Console.WriteLine("Deleted");

}

else if (pos > 1 && pos <=countitem())
{//delete middle item
temp=pfirst;
int i;
for(i=1;i<pos-1;i=i+1){temp=temp.next;} //move to the item staying before the target item to be deleted
del=temp.next; //target item to be deleted
temp.next=del.next;
if(del.next==null)plast=temp; //delete last item
del=null;
Console.WriteLine ("Deleted");

}

else Console.WriteLine("Invalid position!");

}

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

    }
}

C# OOP: Singly Linked List



Print items of singly linked list

Step 5: Print all elements of the 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
public void showall()
{
  ListNode<T> t;
  if (countitem() > 0)
  {
    Console.WriteLine("All items in the list:");
    for (t = pfirst; t != null; t = t.next)
    {

         Console.WriteLine(t.val);
    }
  }
else Console.WriteLine("No item found!");
}

C# OOP: Singly Linked List



Menu to operate singly linked list

Step 6: 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 showmenu(){

Console.WriteLine("=================================");
Console.WriteLine("Linked List 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 all items");
Console.WriteLine("5.Exit");

}

public static void select(){

LinkedList<int> mylist=new LinkedList<int>();
int val,ch, pos;
char yes = 'y';

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:
Console.WriteLine("All items:");
mylist.showall();
break;

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

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

}


Console.Write("Continue? Press y to continue:");
yes =char.Parse (Console.ReadLine());

}



}