Simple linked list implementation in C#

Linked list is the most basic data structure taught in the colleges.Though it looks simple,the kind of complex problems we can solve through it is just amazing.In languages like C,C++ its very easy to understand though pointers.Unfortunately or fortunately in C#,we don't need pointers to learn about linked list though internally,its all pointers all the way to the memory addresses.In this post I will try to explain how a link list can be implemented in C#.
Ok,enough of technical jargon.Lets come straight to the point.
Definition : A linked list is a simple chain of nodes where a node points to next node and so on till the next node doesn't points to anything.
Now what is a node? A node is a simple object which contains some data and a reference to next node.Lets code both our node and linked list class.




The Node class is self explanatory.
As we can see the Linked List class just contains a head node and all the nodes are added to this node.A little bit of explanation on Add function.It takes a parameter of Node type which we are adding to the head.
The main point to note down here is that we are not adding after the head,rather we are adding before the head.If we realise, we find that it is based on stack based adding which will become more evident when we print the nodes.

Lets write the client code.It is a simple console application which uses these 2 classes.
Following is the output :
fourth
third
second
first
And we are not surprised why this is the output.
Now lets modify our linkedlist class so that we always add a node after the head.The modified Add function is :


This time the output is :
first
second
third
fourth
This is just the beginning of linked lists and in future we will see more practical examples of linked lists.This is the beauty of C# that internal memory addressing is hidden from us and all we have to know is how reference and value types work in C#. .NET runtime do the all work of referencing and dereferencing for us.


Comments

  1. Mr.AFebruary 12, 2012 at 10:50 PM

    This is an excellent and simple example

    ReplyDelete
  2. ivarravi111May 3, 2012 at 12:27 AM

    Excellent . Thx

    ReplyDelete
  3. UnknownSeptember 25, 2012 at 5:13 AM

    ohhhh!!!!! Sir thanks Sir. Finally I able to program linked list in c#. very simple and great tutorial. Thanks

    ReplyDelete
  4. UnknownFebruary 24, 2013 at 8:38 PM

    thanks for simple yet very valuable article

    ReplyDelete
  5. UnknownMarch 28, 2013 at 3:20 AM

    The print function is implemented in such a way that you can use it to print the contents of the linked list only once. In my opinion, it is better to have a function that does its job every time it is called.

    I would suggest adding a traversal pointer to the print function, and the problem is solved.

    public void PrintNodes()
    {
    Node traversal = head;
    while (traversal != null)
    {
    Console.WriteLine(traversal.data);
    traversal = traversal.next;
    }
    }

    ReplyDelete
  6. anonymousMay 19, 2013 at 5:50 AM

    thank you so much!!!!! im really very grateful to u. this program is very clear with good explanation.i can now picture linked lists in my mind very clearly. i've been breaking my head from past 1 week not understanding linked list. this solved my problem.

    ReplyDelete
  7. BharatAugust 16, 2013 at 1:01 AM

    It was very well explained. Thanks a lot.

    - Bharat

    ReplyDelete

Post a Comment

Popular posts from this blog

Composition over Inheritance

We had often heard that composition is better than inheritance. Why is it so? First of all how is one different from the other and what are the similarities in them? Lets say we are writing simulation software for Rocket Launching systems which are to be supplied to different countries. Now these different countries can use them as they want it. The code for our launching system is below: public   class   Launcher {      public   bool  LaunchMissile()     {          Console .WriteLine( "Missile launched" );          return   true ;     } } public   class   SufraceToAirMissileLauncher : Launcher {   } Now, country A uses this code to launch missile as follows: static   void  Main( string [] args)     {          SufraceToAirMissileLauncher  staLauncher =  new   SufraceToAirMissileLauncher ();          bool  isLaunched =   staLauncher.LaunchMissile();     } This is how Inheritance is used. The various launchers can reuse the base Launcher class code to launch m
Read more

Some basic linked list problems

Image
In my earlier  post  , we had seen how to implement a basic linked list in C#. We also saw both stack and queue based additions to the linked list. In this post we are going to look at some of the basic linked list problems which will prepare us for more adventure ahead.We will start with basic node class. We would keep adding functions in the LinkedList class as we program. Right now the list is empty with only 2 nodes- head and current which both point to null.Below I am giving the code for simple insertion and printing of nodes,once they are added. Below I am giving code for some functions which can be added to this class. These are : Node Find Find a node in the list.It returns the node when it is found.If the corresponding node is not found null is returned. The next problem is to remove a node from the list. Here we would create a small helper function which would return a previous node. The given functions are below : The next problem is Reversing a list . The next
Read more