Question: Please implement a Link List using C# programming language. But you can not use any .NET Framework Collection classes for that. It should be your own implementation of Link List.
Do you ever face this kind of question? Can you tell me why people ask to implement a Data Structure which can be implemented by using a class library class? May be they want to see the programming capability by asking this types of questions. Whatever the reasons, we need to give answers to these questions to proceed.
I have a good book on Data Structure. The name is ‘Data Structures Through C in Depth’ by ‘S. K. Srivastava’ and ‘Deepali Srivastava’ from ‘BPB Publications’. In this post I am going to implement a list using an array. I am also going to take help from my Data Structure book.
What Is List?
List is a collection of records. We use list in our daily life. Also in our daily software development. You can take list example from our shopping list to store a collection of objects in memory.
How to Implement List in Computer Memory?
So as a software developer our main job is to implement list of data in computer memory. You can implement list in computer memory in many ways. But in this post I am going to use an array.
What is Array?
Array is a fixed length collection of same type of data, which is stored in adjacent location in computer memory.
Use Array to Implement List in Computer Memory
Ok. Now it is time to get my hands dirty. I am going to start the real programming. Here for simplicity I have decided to develop a console application. Also I am writing all the logic inside a Class Library and compile it into a .dll file. Then the console application will take the reference of the .dll file and use its logic. Again if you want, you can create a test application to test the logic which is written inside the .dll file.
In a list I am going to do five operations.
- Display
- Search
- Count
- Insert
- Delete
Display
Display operation means I need to print all the items which is stored inside the list (inside the array because the list is implemented using an array) on to console in my application. I am assuming that the array has some items. It is not empty. In a real world application we should check this list underflow condition before printing.
for (int counter = 0; counter < theArray.Length; counter++)
{
Console.WriteLine(theArray[counter]);
}
Search
Search operation means I need to find a given item from the list.
int itemToSearch = 2; // This can be given by the user as an input.
bool isFound = false;
for (int i = 0; i < theArray.Length; i++)
{
if (theArray[i] == itemToSearch)
{
isFound = true;
}
}
if (isFound)
{
Console.WriteLine("Item found in the list");
}
else
{
Console.WriteLine("Item not found in the list");
}
Count
Give the number of items in side the list.
int counter = 0;
for (int i = 0; i < theArray.Length; i++)
{
counter++;
}
Console.WriteLine("The list has {0} items", counter);
Insert
When insert a new item in the list then first I need to check that weather the list has a free space for that or not. Because array length is always fixed. In insert operation there are two situations.
- Insert an item at the end of the list.
- Insert an item in between the existing item in the list.
Here also I need to track the total number of items in the array and the capacity of the array.
In the first case I need to set the new item in the position which is one more than the height position. Suppose the capacity of the array is 10 and currently there are 5 (0th to 4th position) items in the array. Now I want to insert a new item to the last of the array. So I need to place the item at 5th (4+1) position of the array.
In the second case I need to right shift all the items from the position where I want to insert the item to the height position of item. Suppose capacity is 10 and currently there are 5 (0th to 4th) items in the array. Now I want to insert a new item to the 3rd position. So I need to right shift all the items starting from 3rd to 4th position.
Delete
First I need to check weather there are any item in the array or not. This is called underflow condition. Delete has also two situations.
- Delete the last item from the array.
- Delete in between from the array.
Again I need to track the capacity of the array and the total number of items in the array.
First case only the total number of items in the array will be decremented.
In the second case I need to left shift all the items starting from the deleted position to highest position of item in the array.
Full Code
Ok, so I am done for today. Here I am posting the code. You can also download the full code from the ‘sample code’ section of my site.
public enum OperationMode
{
Input = 1,
Insert = 2,
Search = 3,
Delete = 4,
Display = 5,
Quit = 6
}
public class List
{
private int[] _list;
private int _numberOfElementInList;
public List(int sizeOfList)
{
_numberOfElementInList = sizeOfList;
_list = new int[sizeOfList];
}
public void PerformOperationOnList(OperationMode mode)
{
int position;
bool isFound;
switch (mode)
{
case OperationMode.Input:
InputList();
break;
case OperationMode.Insert:
Insert();
break;
case OperationMode.Search:
Console.Write("Please enter an item to search: ");
int itemToSearch = int.Parse(Console.ReadLine());
isFound = Search(itemToSearch, out position);
if (isFound)
{
Console.WriteLine("Item found at {0} position", position);
}
else
{
Console.WriteLine("Item can not be found");
}
break;
case OperationMode.Delete:
Delete();
break;
case OperationMode.Display:
Display();
break;
case OperationMode.Quit:
break;
default:
Console.WriteLine("Please enter a valid option");
break;
}
}
private void InputList()
{
for (int counter = 0; counter < _list.Length; counter++)
{
Console.Write("Please enter an item: ");
int item = int.Parse(Console.ReadLine());
_list[counter] = item;
}
}
private void Insert()
{
if (_list.Length == _numberOfElementInList)
{
Console.WriteLine("List overflow");
return;
}
Console.Write("Please enter a position to insert: ");
int position = int.Parse(Console.ReadLine());
Console.Write("Please enter an item to insert: ");
int itemToInsert = int.Parse(Console.ReadLine());
if (position > _numberOfElementInList)
{
Console.WriteLine("Please enter position less than size of the list");
return;
}
// Insert at the last of the list.
if (position == _numberOfElementInList)
{
_list[position] = itemToInsert;
_numberOfElementInList++;
return;
}
// Insert in the middle position of the list.
int temp = _numberOfElementInList - 1;
while (temp >= position)
{
_list[temp + 1] = _list[temp];
temp--;
}
_list[position] = itemToInsert;
_numberOfElementInList++;
}
private bool Search(int itemToSearch, out int position)
{
bool isFound = false;
position = -1;
for (int counter = 0; counter < _list.Length; counter++)
{
if (_list[counter] == itemToSearch)
{
position = counter;
isFound = true;
break;
}
}
return isFound;
}
private void Delete()
{
bool isFound;
int position;
if (_numberOfElementInList == 0)
{
Console.WriteLine("List underflow");
return;
}
Console.Write("Please enter an item to delete: ");
int itemToDelete = int.Parse(Console.ReadLine());
isFound = Search(itemToDelete, out position);
if (isFound)
{
// Delete the last item from the list.
if (position == _numberOfElementInList)
{
_numberOfElementInList--;
}
// Delete item from the middle position of the list.
int temp = position;
while (temp < _numberOfElementInList - 1)
{
_list[temp] = _list[temp + 1];
temp++;
}
_numberOfElementInList--;
}
else
{
Console.WriteLine("Item can not be found in the list");
}
}
private void Display()
{
if (_numberOfElementInList == 0)
{
Console.WriteLine("List underflow");
return;
}
Console.WriteLine();
for (int counter = 0; counter < _numberOfElementInList; counter++)
{
Console.WriteLine(_list[counter]);
}
Console.WriteLine();
}
}
// This class test the logic which is written inside class library.
class Program
{
static void Main(string[] args)
{
Console.WriteLine("Welcome To 'List Using Array' Application\n");
bool isValidToContinue;
List myList;
TakeStartupInput(out isValidToContinue, out myList);
if (isValidToContinue)
{
PerformOperationsOnList(myList);
EndOfProgram(isValidToContinue); // Application end with success.
}
Console.ReadKey(true);
}
private static void TakeStartupInput(out bool isValidToContinue, out List myList)
{
Console.Write("Please enter the size of the list: ");
int size = 0;
isValidToContinue = false;
try
{
size = int.Parse(Console.ReadLine());
isValidToContinue = true;
}
catch (FormatException)
{
Console.WriteLine("Sorry your input is not valid.");
EndOfProgram(isValidToContinue); // Application end with error.
}
catch (Exception)
{
Console.WriteLine("Operation can not be done due to some problem");
EndOfProgram(isValidToContinue); // Application end with error.
}
myList = new List(size);
}
private static void PerformOperationsOnList(List myList)
{
OperationMode mode = OperationMode.Input;
do
{
Console.WriteLine("\nInput");
Console.WriteLine("Insert");
Console.WriteLine("Search");
Console.WriteLine("Delete");
Console.WriteLine("Display");
Console.WriteLine("Quit\n");
Console.Write("Please enter your choise: ");
string choise = string.Empty;
try
{
choise = Console.ReadLine();
}
catch (FormatException)
{
Console.WriteLine
("Please enter valid input."); // Then go to next loop cycle to try again.
}
catch (Exception)
{
Console.WriteLine
("Operation can not be done due to some problem"); // Then go to next loop cycle to try again.
}
if (choise != string.Empty)
{
try
{
mode = (OperationMode)Enum.Parse(typeof(OperationMode), choise, true);
myList.PerformOperationOnList(mode); // Perform logic which is in the class library.
}
catch (ArgumentException)
{
Console.WriteLine("Please enter valid input.");
}
}
} while (mode != OperationMode.Quit);
}
private static void EndOfProgram(bool isValidToContinue)
{
if (isValidToContinue)
{
Console.WriteLine("\nThank you");
}
else
{
Console.WriteLine("\nBetter luck next time");
}
}
}
Hope you enjoy the journey with me while I am developing this application. In future I will develop some more applications on data structure.
You can also download the code from ‘MSDN Code Sample’.
This application is on ‘MSDN Code Sample’
Thank you and happy coding.
Arnab's blog 