Implementing Linked Lists in C#

For updated version of this blog/post, please visit www.agnosticdevs.com

Why?

The question is why you need Linked Lists and why it is the foundation of any Abstract Data Structure.

Take any of the Data Structures - Stacks, Queues, Heaps, Trees; there are two ways to go about implementing them -

  • Using Arrays
  • Using Linked Lists

Now you use Arrays when you know about the size of the Nodes in the list at Compile time and Linked Lists are helpful in a way that you are free to add as many Nodes to the List as required at Runtime.

 

How?

Now, let's see how we go about implementing a Simple Linked List in C#.

Note: We'd be dealing with singly linked list for time being, there's also another version of linked lists - the Doubly Linked List which maintains two pointers (NEXT and BEFORE).

 

Class Diagram

Let's see the Class Diagram first:

 Class Diagram

 

Code

    1 // -----------------------------------------------------------------------

    2 // <copyright file="Node.cs" company="">

    3 // TODO: Update copyright text.

    4 // </copyright>

    5 // -----------------------------------------------------------------------

    6 

    7 namespace CSharpAlgorithmsAndDS

    8 {

    9     using System;

   10     using System.Collections.Generic;

   11     using System.Linq;

   12     using System.Text;

   13 

   14     /// <summary>

   15     /// TODO: Update summary.

   16     /// </summary>

   17     public class Node

   18     {

   19         public Object data { get; set; }

   20 

   21         public Node Next { get; set; }

   22     }

   23 }

   24 

 

 

 

    1 // -----------------------------------------------------------------------

    2 // <copyright file="LinkedList.cs" company="">

    3 // TODO: Update copyright text.

    4 // </copyright>

    5 // -----------------------------------------------------------------------

    6 

    7 namespace CSharpAlgorithmsAndDS

    8 {

    9     using System;

   10     using System.Collections.Generic;

   11     using System.Linq;

   12     using System.Text;

   13 

   14     /// <summary>

   15     /// TODO: Update summary.

   16     /// </summary>

   17     public class LinkedList

   18     {

   19         private Node Head;

   20 

   21         public void AddNode(Node n)

   22         {

   23             n.Next = this.Head;

   24             this.Head = n;

   25 

   26         }

   27 

   28         public void printNodes()

   29         {

   30 

   31             while (Head!=null)

   32             {

   33                 Console.WriteLine(Head.data);

   34                 Head = Head.Next;

   35 

   36             }

   37 

   38         }

   39     }

   40 }

   41 

 

 

 

 

    1 using System;

    2 using System.Collections.Generic;

    3 using System.Linq;

    4 using System.Text;

    5 

    6 namespace CSharpAlgorithmsAndDS

    7 {

    8     class Program

    9     {

   10         static void Main(string[] args)

   11         {

   12             LinkedList ll = new LinkedList();

   13             Node A = new Node();

   14             A.data = "A";

   15 

   16             Node B = new Node();

   17             B.data = "B";

   18 

   19             Node C = new Node();

   20             C.data = "C";

   21             ll.AddNode(A);

   22             ll.AddNode(B);

   23             ll.AddNode(C);

   24 

   25             ll.printNodes();

   26         }

   27     }

   28 }

   29 

 

 

 

Final Words

This is just a start, I will add more posts on Linked List covering more operations like Delete etc. and will also explore Doubly Linked List / Implementing Stacks/ Heaps/ Trees / Queues and what not using Linked Lists.

 


Published Saturday, October 6, 2012 7:28 AM by nijhawan.saurabh

Comments

# re: Implementing Linked Lists in C#

Sunday, October 7, 2012 10:57 PM by stackify

Thanks for creating this simple example. This is really helpful.

# re: Implementing Linked Lists in C#

Thursday, October 11, 2012 4:08 PM by RichardD

Unless you're using .NET 1.0, your linked list should be using generics. If you need inspiration, have a look at the built-in LinkedList<T> / LinkedListNode<T> classes in the System.Collections.Generic namespace.

# re: Implementing Linked Lists in C#

Sunday, October 14, 2012 9:09 AM by nijhawan.saurabh

@Richard. Good point,the post focuses on a simple Implementation of a well known DS in C#.

When you go about using a Linked List in C#, you'd obviously use the built in .Net Classes (Generic or Non- Generic), but my motive here was to just show how we go about implementing it in C# as its quiet different from C++ as we don't have pointers here. I would try adding an implementation which uses Generics, i suppose that'd be good. Thanks for the feedback!

# re: Implementing Linked Lists in C#

Tuesday, June 11, 2013 1:47 AM by adam

it's LIFO implementation.

# re: Implementing Linked Lists in C#

Thursday, January 23, 2014 12:05 AM by Farah

Thanks that's a good start

Leave a Comment

(required) 
(required) 
(optional)
(required)