Doubly Linked List in C# – Data Structure

Doubly Linked List is a dynamic data Structure which can grow or shrink in size at runtime. It have 2 pointers to navigate forward and in direction in the list unlike Singly Linked List where we have only 1 pointer to move only in forward direction in the list.

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

namespace DoublyLinkedList
{

    class Node
    {
        public int Data;
        public Node Next;
        public Node prev;
    }

    class List
    {
        Node Start;
        public List() 
        {
            Start = null;
        }

        /// <summary>
        /// Traversing through the List
        /// </summary>
        public void Traverse()
        {
            Node current;
            current = Start;

            if (current == null)
            {
                Console.WriteLine("List is Empty");
            }
            while (current != null)
            {
                Console.Write(current.Data + " - ");
                current = current.Next;
            }
        }

        /// <summary>
        /// Adding a node in List
        /// </summary>
        public void Add()
        {
            int num;
            Console.WriteLine("Enter value to Enter");
            num = Convert.ToInt32(Console.ReadLine());

                Node newNode = new Node();
                newNode.Data = num;

                if (Start == null)
                {
                    newNode.Next = null;
                    newNode.prev = null;
                    Start = newNode;
                }

                else
                {
                    Node current = Start;

                    while ((current.Next != null) && (current.Data < newNode.Data))
                    {
                        current = current.Next;
                    }

                    if ((current.Next == null) && (newNode.Data>current.Data))
                    {
                        //Insertion at the end of list
                        newNode.Next = null;
                        current.Next = newNode;
                        newNode.prev = current;
                    }

                    else if (current == Start)
                    {
                        //Insertion in the beginning of list
                        newNode.prev = null;
                        newNode.Next = Start;
                        Start.prev = newNode;
                        Start = newNode;
                    }

                    else if (current.Next != null)
                    {
                        //Insertion somewhere in the middle of List
                        newNode.Next = current;
                        newNode.prev = current.prev;
                        current.prev.Next = newNode;
                        current.prev = newNode;
                    }
                }
         }

        /// <summary>
        /// Delete a node from List
        /// </summary>
        public void Delete()
        {
            Console.WriteLine("Enter Item to Delete");
            int num = Convert.ToInt32(Console.ReadLine());

            Node current = Start;

            if (current == null)
            {
                Console.WriteLine("List is Empty");
            }

            else
            {
                while ((current != null) && (current.Data != num))
                {
                    current = current.Next;
                }

                if (current == null)
                { Console.WriteLine("Not Found"); }

                else if ((current == Start) && (current.Next==null))
                {
                    //Deletion of the only node of the list
                    Start = null;
                }

                else if (current == Start)
                {
                    //Deletion from the beginning of list
                    Start = Start.Next;
                    Start.prev = null;
                }

                else if ((current != Start) && (current.Next == null))
                {
                    //Deletion from the end of list
                    current = current.prev;
                    current.Next = null;
                }

                else
                {
                    //somewhere from the middle of list
                    current.prev.Next = current.Next;
                    current.Next.prev = current.prev;
                }
            }

            Console.WriteLine("-----------------------------------------");
            Traverse();
        }
    } 

    class Program
    {
        static void Main(string[] args)
        {

            List MyList = new List();
            while (true)
            {
                Console.WriteLine("\nMenu");
                Console.WriteLine("1. Add a Record");
                Console.WriteLine("2. Traverse");
                Console.WriteLine("3. Delete");
                Console.WriteLine("4. Exit");
                Console.Write("Your Option :: ");
                char ch = Convert.ToChar(Console.ReadLine());

                switch (ch)
                {
                    case '1':
                        MyList.Add();
                        break;

                    case '2':
                        MyList.Traverse();
                        break;

                    case '3':
                        MyList.Delete();
                        break;

                    case '4':
                        return;
                    default:
                        Console.WriteLine("Invalid Option");
                        break;
                }

            }
        
        }
    }
}