Linked List using C#

In this section, we will learn the overview of the linked list & basic implementation of linkedlist using C#. 

What is a Linked List?

Linked List is one of the most commonly used Data structure. It is a linear data structure that overcomes the limitation of an array. Arrays are stored in memory as a contiguous. So once an array gets declared we cannot increase the size. But in case of a linked list implementation, the nodes are stored in heap memory and it needs not to be contiguous blocks hence we can easily increase the size dynamically.

Node: This where we have the Data & Links to the next element in the List.

The above figure depicts a sample Node in a Single linked list. The data part holds the data (here integer data type) & Next will hold an address of the next link.

We can create a Class for Node having two public properties

1. Data
2. Next

public class Node
   {
       public int data;
       public Node next;

       public Node(int data)
       {
           this.data = data;
           this.next = null;
       }
       public Node() { }
   };

public class Linkedlist
    {
        Node head;
        public Node GetHeadNode
        {
            get
            {
                return head;
            }
        }
        public Linkedlist()
        {

        }
    }

public void AddAt(int data, int position)
{
    if (head != null)
    {
        Node temp = head;
        Node current = null;
        Node next = null;
        for (int i = 0; i < position - 2; i++)
        {
            temp = temp.next;
        }
        current = temp;
        next = temp.next;

        Node newNode = new Node(data);
        current.next = newNode;
        newNode.next = next;
    }
}

//This receives data as the argument
public void AddFirst(int data)
{
    Node newNode = new Node(data); //creating a new node by calling the constructor
    
    //below code will insert the Node at the beginning of the linkedlist
    newNode.next = head;   
    head = newNode;
}

public void AddLast(int data)
{
    Node temp = head;
    Node newNode = new Node(data);
    
    //if the linkedlist is empty head will be the newly created node
    if (head == null)
    {
        head = new Node();
        head.next = newNode;
        head = newNode;
    }
    else
    {
        //iterate through the list until we get  lastnode
        while (temp.next != null)
        {
            temp = temp.next;
        }
        
        //insert the new node at the last
        temp.next = newNode;
    }
}

public void PrintAll()
{
    Console.WriteLine("The Linked List Contents");
    Node temp = head;
    //iterate through all the nodes & print data
    while (temp != null)
    {
        Console.Write(temp.data + "--> ");
        temp = temp.next;

    }
    Console.WriteLine();
}

public void PrintAllRecursively(Node temp)
{
    //this is the exiting condition
    //this will true after last is printed in a linked list
    if (temp == null)
        return;
    Console.Write(temp.data + "-->");
    PrintAllRecursively(temp.next); //this is the recursive call to the fucntion
}

public void ReverseLinkedList()
{
    Node current = head;
    Node previous = null;
    Node next = current.next;

    while (next != null)
    {
        current.next = previous;
        previous = current;
        current = next;
        next = next.next;
    }
    current.next = previous;
    head = current;

}

public class Linkedlist
{
    Node head;
    public Node GetHeadNode
    {
        get
        {
            return head;
        }
    }
    public Linkedlist()
    {

    }

    public void PrintAll()
    {
        Console.WriteLine("The Linked List Contents");
        Node temp = head;
        while (temp != null)
        {
            Console.Write(temp.data + "--> ");
            temp = temp.next;

        }
        Console.WriteLine();
    }

    public void AddFirst(int data)
    {
        Node newNode = new Node(data);
        newNode.next = head;
        head = newNode;
    }

    public void AddLast(int data)
    {
        Node temp = head;
        Node newNode = new Node(data);
        if (head == null)
        {
            head = new Node();
            head.next = newNode;
            head = newNode;
        }
        else
        {
            while (temp.next != null)
            {
                temp = temp.next;
            }
            temp.next = newNode;


        }



    }

    public void AddAt(int data, int position)
    {
        if (head != null)
        {
            Node temp = head;
            Node current = null;
            Node next = null;
            for (int i = 0; i < position - 2; i++)
            {
                temp = temp.next;
            }
            current = temp;
            next = temp.next;

            Node newNode = new Node(data);
            current.next = newNode;
            newNode.next = next;
        }
    }

    public void ReverseLinkedList()
    {
        Node current = head;
        Node previous = null;
        Node next = current.next;

        while (next != null)
        {
            current.next = previous;
            previous = current;
            current = next;
            next = next.next;
        }
        current.next = previous;
        head = current;

    }

   
    public void PrintAllRecursively(Node temp)
    {
        if (temp == null)
            return;
        Console.Write(temp.data + "-->");
        PrintAllRecursively(temp.next);
    }

    public void PrinAllReverseRecursively(Node temp)
    {
        if (temp == null)
            return;
        PrinAllReverseRecursively(temp.next);
        Console.Write(temp.data + "-->");

    }
}

Doubly Linked List using C#

What is a Doubly Linked List ?

This is just similar to Linked List data structure, here the difference is that instead of a single link this will point to both the next node as well as the previous node. So a node will be having three fields one will hold the data & the other two will point to the next and previous nodes.

A Sample Doubly Linked List Node implemented in a class.

    public class Node
    {
        public int data;
        public Node next;
        public Node previous;
        public Node(int data)
        {
            this.data = data;
            this.next = null;
            this.previous = null;

        }
        public Node ()
        {

        }
    }

Implementation of Doubly LinkedList

Here we will see the basic implementation of a doubly-linked list with basic operations such as AddFirst, AddLast & Printing all the Nodes in the list.   Create  a Class give a name to that class as DoubleLinkedList.cs

Here we have one property named head , this will store the starting address of the linked list. We have declared this head as a private variable & we are using getter get the value. We have also provided an constructor.

    public class DoublyLinkedlist
    {
        Node head;
       
        public Node GetHeadNode
        {
            get
            {
                return head;
            }
        }
        public DoublyLinkedlist()
        {
            head = null;
        }
    }

Inserting to a Doubly  Linked List

This is similar to insertion to a single linked list but here we need to take care of previous node also.  

      public void AddFirst(int data)
  {
      Node newNode = new Node(data);
      if (head!=null)
      {
          newNode.next = head;
          head.previous = newNode;
          head = newNode; 
      }
      else
      {
          head = newNode;
      }
  }

  public void AddLast(int data)
  {
      Node temp = head;
      Node newNode = new Node(data);
      if (temp!=null)
      {
          while (temp.next != null)
          {
              temp = temp.next;
          }
          temp.next = newNode;
          newNode.previous = temp;
      }
      else
      {
          head = newNode;
      }
  }

Print All the Nodes in a Doubly Linked List

 This is also similar to Linked List implementation. For Debugging purpose I am here printing previous,current & next nodes

public void PrintAll()
{
    Node temp = head;
    while(temp!=null)
    {
        Console.WriteLine("Previous={0},Current ={1},Next={2}", temp.previous?.data, temp.data, temp.next?.data);
        temp = temp.next;
    }
}

For Detailed reference for linked list you can check here