Linked Lists Sort using Insertion Sort

Write a program to sort link list using Insertion Sort

Solution:

using System;

namespace LinkedListOpearation
{

    class Program
    {
        public static void Main()
        {
            var linkedList = new LinkedList();
            linkedList.Add(15);
            linkedList.Add(10);
            linkedList.Add(5);
            linkedList.Add(20);
            linkedList.Add(3);
            linkedList.Add(2);

            linkedList.InsertionSort(linkedList.Head);
            Console.WriteLine("Sorted Linked List is:");
            linkedList.Print(linkedList.Head);
            Console.ReadLine();
        }   
    }

    
    public class LinkedList
    {
        public Node Head;
        public Node Sorted;

        public void InsertionSort(Node node)
        {
            Sorted = null;
            var current = node;
            while (current != null)
            {
                var next = current.Next;
                SortedInsert(current);
                current = next;
            }
            Head = Sorted;
        }

        void SortedInsert(Node node)
        {
            if (Sorted == null || Sorted.Data >= node.Data)
            {
                node.Next = Sorted;
                Sorted = node;
            }
            else
            {
                var current = Sorted;
                while (current.Next != null &&
                       current.Next.Data < node.Data)
                {
                    current = current.Next;
                }
                node.Next = current.Next;
                current.Next = node;
            }
        }

        public void Add(int data)
        {
            var node = new Node(data) {Next = Head};
            Head = node;
        }

        public void Print(Node head)
        {
            while (head != null)
            {
                Console.WriteLine(head.Data);
                head = head.Next;
            }
        }
    }

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

        public Node(int data)
        {
            Data = data;
        }
    }
}

Leave a Reply

Your email address will not be published. Required fields are marked *