Farey

Farey.cs

using System;
using System.Collections.Generic;
using System.Linq;

namespace AlgorithmsAndDataStructures
{
    struct Rational
    {
        public int Numerator;
        public int Denominator;
        public override string ToString()=>$"{Numerator}/{Denominator}"; 
    }

    class Program
    {
        private class Node
        {
            public Rational Info;
            public Node Next;
        }
        static IEnumerable<Rational> FareyLinkedList(int k)
        {
            var last = new Node {Info = new Rational{Numerator = 1, Denominator = 1}};
            var first=new Node { Info= new Rational { Numerator = 0, Denominator = 1},Next=last };

            for(int i=2; i<=k; i++)
            {
                var cur = first;
                while(cur!=last)
                {
                    int b = cur.Info.Denominator;
                    int d = cur.Next.Info.Denominator;
                    if(b+d==i)
                    {
                        var n = new Node
                        {
                            Info = new Rational
                            {
                                Numerator = cur.Info.Numerator + cur.Next.Info.Numerator,
                                Denominator = b + d
                            },
                            Next=cur.Next
                        };
                        cur.Next = n;
                    }
                    cur = cur.Next;
                }    
            }
            for (Node n = first; n != null; n = n.Next)
                yield return n.Info;      
        }

        public static IEnumerable<Rational> FareyList(int k)
        {
            var list = new List<Rational>
            {
                new Rational {Numerator = 0, Denominator = 1},
                new Rational {Numerator = 1, Denominator = 1}
            };
            for (int i = 2; i <= k; i++)
                for (int j = 0; j < list.Count - 1; j++)
                {
                    int b = list[j].Denominator;
                    int d = list[j + 1].Denominator;
                    if (b + d == i)
                        list.Insert(j + 1,
                            new Rational
                            {
                                Numerator = list[j].Numerator + list[j + 1].Numerator,
                                Denominator = b + d
                            });
                }
            return list;
        }

        static void Main(string[] args)
        {
            var farey = FareyLinkedList(8);
            foreach (var item in farey)
                Console.Write(item + " ");
            Console.WriteLine();

            farey = FareyList(8);
            foreach (var item in farey)
                Console.Write(item + " ");
            Console.WriteLine();

            var sw = new System.Diagnostics.Stopwatch();
            sw.Start();
            FareyList(1000).ToList();
            sw.Stop();
            Console.WriteLine($"F_1000 using List: {sw.Elapsed.TotalMilliseconds}ms");

            sw.Restart();
            FareyLinkedList(1000).ToList();
            sw.Stop();
            Console.WriteLine($"F_1000 using LinkedList: {sw.Elapsed.TotalMilliseconds}ms");
        }
    }
}