Linked List Implementation in C#

CodeProject In this article I'll explain about linked list. What is pros and cons of using linked list and then implementation of linked list in C#. However microsoft provide strongly typed linked list LinkedList(T) in System.Collections.Generic namespace, I'll explain here core implementation of Linked List.

What is Linked List?
Linked list is a linear data structure. Its a collection of elements. Element called as Node.
Each element have value(data) and reference of next node.Very first node  called as Head and last element have reference to null value.

Types of Linked List

Basically there are 3 types of linked list.

1. Singly Linked List  : A singly linked list is a list which has a value(data) and a reference to next node.In this last node's next reference will be null.
2. Doubly Linked List : A doubly linked list is a list which has a data and 2 references, one for next node and another for previous node and last node's next reference will be null
3. Circular Linked List: In circular linked list last node's next reference will be head or first element. Circular linked list can be singly linked list or doubly linked list.

In this article I'll explain implementation of only singly linked list.

Pros and Cons

Main advantage of linked list is that Its a dynamic data structure.Unlike in array where length of array is predefined, we can add dynamic number of data in linked list without worrying about size of linked list. So linked list can be used where there is unknown number of data need to be stored at run time.

Disadvantage of linked list is that it takes more space than array. Because it stores reference of next/previous nodes.

Implementation of linked list

Node Class:

Here is the node class which have 2 properties.

 public class Node
 {
     public Node Next;
     public object Value;
 }

One property is 'Next', which will have reference of next node and another is 'Value', which will have data in this node.

LinkedList Class:
Now implement linked list class as follows:

public class LinkedList
{
   private Node head;
   private Node current;//This will have latest node
   public int Count;
}

'head' will have head node. 'current' will have latest node i.e. tail node and 'Count' will return total number of nodes in linked list.

Constructor: 
Initially head and current value will be same and will have empty node, so we will create constructor for that settings.

public LinkedList()
{
  head = new Node();
  current = head;
}

Operations in Linked list:
Now we will create  some operations on linked list.

1.Add node after last element

public void AddAtLast(object data)
{
   Node newNode = new Node();
   newNode.Value = data;
   current.Next = newNode;
   current = newNode;
   Count++;
}

This method will add node after tail node and it will increase count by one.Similarly you can add node as fist node.

2.Add node as fist element

 public void AddAtStart(object data)
 {
   Node newNode = new Node() { Value = data};
   newNode.Next = head.Next;//new node will have reference of head's next reference
   head.Next = newNode;//and now head will refer to new node
   Count++;
 }

3.Remove node from start:

public void RemoveFromStart()
{
   if (Count > 0)
   {
     head.Next = head.Next.Next;
     Count--;
   }
   else
   {
     Console.WriteLine("No element exist in this linked list.");
   }
}

Similarly you can write method to remove node from last or from any index.You have to do traverse from head to that particular index and remove node as above by changing the reference.

4.Traverse whole linked list

/// 

/// Traverse from head and print all nodes value
/// 
public void PrintAllNodes()
{
    //Traverse from head 
    Console.Write("Head ->");
    Node curr = head;
    while (curr.Next != null)
    {
        curr = curr.Next;
        Console.Write(curr.Value);
        Console.Write("->");
    }
    Console.Write("NULL");
}

Start from head and traverse until you get next node is null.

Note: Similarly you can write code for deleting node of specific index , inserting node on specific position etc.

Time to celebrate...
Now its time to test our code.To test our code we will write main method and call linked list and its operations in that.

class Program
{
    static void Main(string[] args)
    {
           
        LinkedList lnklist = new LinkedList();
        lnklist.PrintAllNodes();
        Console.WriteLine();

        lnklist.AddAtLast(12);
        lnklist.AddAtLast("John");
        lnklist.AddAtLast("Peter");
        lnklist.AddAtLast(34);
        lnklist.PrintAllNodes();
        Console.WriteLine();

        lnklist.AddAtStart(55);
        lnklist.PrintAllNodes();
        Console.WriteLine();

        lnklist.RemoveFromStart();
        lnklist.PrintAllNodes();


        Console.ReadKey();
    }
}

Guess what'll be output. Here it is..

You can download this project. To download CLICK HERE.


Did you like this article. Feel free to reach me by comments.