using System;

public class Program

{

    public static void Main()

    {

        LinkedListMethods list = new LinkedListMethods();

        list.DisplayList();

        Console.WriteLine("=======================");

        list.BubbleSortExNode();

        Console.WriteLine("=======================");

        list.DisplayList();

        Console.WriteLine("=======================");

        Console.ReadLine();

    }

}

​

public class Node{

    public Node link;

    public int data;

    public Node(int data){

        this.data = data;

        link = null;

    }

}

​

public class LinkedListMethods{

    private Node start;

    public LinkedListMethods(){

        var node5 = new Node(20);

        var node4 = new Node(67); node4.link = node5;

        var node3 = new Node(17); node3.link = node4;

        var node2 = new Node(89); node2.link = node3;

        var node1 = new Node(21); node1.link = node2;

        start = node1;      

    }

    public void DisplayList(){

        if(start == null) Console.WriteLine("Empty List ");

        Node p = start;

        Console.WriteLine("List :");

         while(p != null){

            Console.WriteLine(p.data);

             p = p.link;

         }

    }

    public void BubbleSortExNode(){

        Node p, q, r, temp, end;

        for(end = null; end != start.link; end = p){

            for(r = p = start; p.link != end; r = p, p = p.link){

                q = p.link;

                if(p.data > q.data){

                    p.link = q.link;

                    q.link = p;

                    if(p != start){

                        r.link = q;

                    }else{

                        start = q;

                    }

                }

                temp = p;

                p = q;

                q = temp;

            }

        }

    }

}