// Lista jednokierunkowa, niesortowana, przechowująca wartości int
// (C) Paweł Szulc
// www.algorytm.org

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

namespace ListaJednokierunkowa
{
    class Program
    {
        class Element       // klasa opisująca poszczególny element listy - wartość danego elementu oraz zmienną przechowującą następny element listy
        {
            private int Wartosc;
            private Element Nastepny;

            public Element(int W)
            {
                Wartosc = W;
                Nastepny = null;
            }
            public int ZwrocWartosc() { return Wartosc; }
            public Element ZwrocNastepny() { return Nastepny; }
            public void UstawNastepny(int W)
            {
                Nastepny = new Element(W);
            }
            public void UsunNastepny()
            {
                Nastepny = null;
            }

            public void ZamienNastepny()
            {
                Nastepny = ZwrocNastepny().ZwrocNastepny();     // usuwając n-ty element ze środka listy łaczymy element n-1 z elementem n+1
            }
        }

        class Lista     // klasa implementująca listę jednokierunkową
        {
            private Element Korzen;
            private int LiczbaElementow;

            public Lista() 
            { 
                Korzen = null;
                LiczbaElementow = 0;
            }

            public void Wstaw(int W)
            {
                if (Korzen == null)
                {
                    Korzen = new Element(W);
                }
                else
                {
                    Element Tmp = Korzen;
                    while (Tmp.ZwrocNastepny() != null) Tmp = Tmp.ZwrocNastepny(); // przechodzimy na koniec listy, czyli do elementu, który nie posiada elementu następnego. 
                    Tmp.UstawNastepny(W);                                          // jeżeli Tmp.ZwrocNastepny() zwróci null oznacza to, że jesteśmy na ostatnim elemencie listy  
                }                                           
                ++LiczbaElementow;
            }

            public bool Pusta()
            {
                return (LiczbaElementow == 0) ? true : false; // operator trójargumentowy, jeśli LiczbaElementow == 0 to zwróc true, w przeciwnym razie false
            }

            public bool Usun(int Indeks)
            {
                if ((Indeks < 1) || (Indeks > LiczbaElementow)) return false;

                if (Indeks == 1) Korzen = Korzen.ZwrocNastepny();  // jeśli trzeba usunąć pierwszy element zmieniamy korzeń z "n" na "n+1"
                else if (Indeks == LiczbaElementow)
                {
                    Element Tmp = Korzen;
                    while (Tmp.ZwrocNastepny().ZwrocNastepny() != null) Tmp = Tmp.ZwrocNastepny();  // przejście na przedostatni element listy
                    Tmp.UsunNastepny();                                                             // zmiana ostatniego elementu z "n" na "n-1"
                }
                else
                {
                    Element Tmp = Korzen;
                    for (uint a = 0; a < Indeks; ++a) Tmp = Tmp.ZwrocNastepny(); // przejście do elementu Indeks-1
                    Tmp.ZamienNastepny();
                }
                --LiczbaElementow;
                return true;
            }

            public void Wyswietl()
            {
                Element Tmp = Korzen;
                for (uint a = 1; Tmp != null; ++a)
                {
                    Console.WriteLine("Element {0} listy = {1}", a, Tmp.ZwrocWartosc());
                    Tmp = Tmp.ZwrocNastepny();
                }
            }

            public int Rozmiar()
            {
                return LiczbaElementow;
            }
        }


        static void Main(string[] args)
        {
            Lista List = new Lista();
            if (List.Pusta()) Console.WriteLine("Lista jest pusta");    // sprawdzenie poprawności działania metody Pusta
            List.Wstaw(5);  
            List.Wstaw(1);
            List.Wstaw(58);
            List.Wstaw(7);
            List.Wstaw(0);
            List.Wstaw(-5);
            List.Wstaw(12);
            List.Wstaw(96);
            List.Wstaw(123);
            List.Wstaw(98563);

            Console.WriteLine("Liczba elementów listy: {0}. Pusta ? Odpowiedź: {1}", List.Rozmiar(), List.Pusta());
            Console.WriteLine();

            List.Wyswietl();

            Console.WriteLine();
            Console.WriteLine("Próba usunięcia do elementu Rozmiar+1 listy. Rozmiar = {0}", List.Rozmiar());
            if (List.Usun(List.Rozmiar()+1)) Console.WriteLine("Usunięto nieistniejący element.");
            else Console.WriteLine("Błędny indeks");
            Console.WriteLine();

            if (List.Usun(1)) Console.WriteLine("Usunięto pierwszy element listy.");
            if (List.Usun(List.Rozmiar())) Console.WriteLine("Usunięto ostatni element listy");
            if (List.Usun(List.Rozmiar() / 2)) Console.WriteLine("Usunięto {0} element listy", (List.Rozmiar() + 1) / 2); // należy dodać Rozmiar+1, ponieważ po wykonaniu tej metody rozmiar, jeszcze przed wyświetleniem zostanie zmniejszony o 1
            Console.WriteLine();

            List.Wyswietl();
            Console.ReadKey();
        }
    }
}