using System;

using System.Collections.Generic;

public class Program

{

    public static void Main()

    {

        Console.WriteLine("Hello World");

        var first = new Node(3);

        var middle = new Node(5);

        first.Next = middle;

        var last = new Node(7);

        middle.Next = last;

        PrintNodes(first);

    }

    public static void PrintNodes(Node node){

        while(node != null){

            Console.WriteLine(node.Value);

            node = node.Next;

        }

    }

}

​

public class LinkedList<T> : ICollection<T>{

    public LinkedListNode<T> Head {get; private set;}

    public LinkedListNode<T> Tail {get; private set;}

    public void AddFirst(T val){

        AddFirst(new LinkedListNode<T>(val));

    }

    public void AddFirst(LinkedListNode<T> node){

        var temp = Head;

        Head = node;

        Head.Next = temp;

        Count++;

        if(Count == 1) Tail = Head;

    }

    public void AddLast(T val){

        AddLast(new LinkedListNode<T>(val));

    }

    public void AddLast(LinkedListNode<T> node){

        if(Count == 0) Head = node;

        else Tail.Next = node;

        Tail = node;

        Count++;

    }

    public void RemoveFirst(){

        if(Count != 0){

            Head = Head.Next;

            Count--;

            if(Count ==0)Tail = null;

        }

    }

    public void RemoveLast(){

        if(Count !=0 ){

            if(Count == 1){

                Head = null;

                Tail = null;

            } else {

                var current = Head;

                while(current.Next != Tail){

                    current = current.Next;

                }

                current.Next = null;

                Tail = current;

            }

        }

    }

    public int Count{get; private set; }

    public void Add(T item){

        AddFirst(item);

    }

    public bool Contains(T item){

        var current = Head;

        while(current != null){

            if(current.Value.Equals(item)) return true;

            current = current.Next;

        }

        return false;

    }

    public void CopyTo(T[] array, int arrayIndex){

        var current = Head;

        while(current != null){

            array[arrayIndex++] = current.Value;

            current = current.Next;

        }

    }

    public bool IsReadOnly { get{return false; }}

    public bool Remove(T item){

        LinkedListNode<T> previous = null;

        var current = Head;

        while(current != null){

            if(current.Value.Equals(item)){

                if(previous != null){

                    previous.Next = current.Next;

                    if(current.Next == null){

                        Tail = previous;

                    }

                    Count--;

                } else {

                    RemoveFirst();

                }

                return true;

            }

            previous = current;

            current = current.Next;

        }

        return false;

    }

    System.Collections.Generic.IEnumerator<T> System.Collections.Generic.IEnumerable<T>.GetEnumerator(){

        var current = Head;

        while(current != null){

            yield return current.Value;

            current = current.Next;

        }

    }

    System.Collections.IEnumerator System.Collections.IEnumerable.GetEnumerator(){

        return ((System.Collections.Generic.IEnumerable<T>)this).GetEnumerator();

    }

    public void Clear(){

        Head = null;

        Tail = null;

        Count = 0;

    }

}

public class DoublyLinkedList<T> : ICollection<T>{

    public DoublyLinkedListNode<T> Head {get; private set;}

    public DoublyLinkedListNode<T> Tail {get; private set;}

    public void AddFirst(T val){

        AddFirst(new DoublyLinkedListNode<T>(val));

    }

    public void AddFirst(DoublyLinkedListNode<T> node){

        var temp = Head;

        Head = node;

        Head.Next = temp;

        Count++;

        if(Count == 1) Tail = Head;

        else temp.Previous = Head;

    }

    public void AddLast(T val){

        AddLast(new DoublyLinkedListNode<T>(val));

    }

    public void AddLast(DoublyLinkedListNode<T> node){

        if(Count == 0) Head = node;

        else { 

            Tail.Next = node;

            node.Previous = Tail;

        }

        Tail = node;

        Count++;

    }

    public void RemoveFirst(){

        if(Count != 0){

            Head = Head.Next;

            Count--;

            if(Count ==0)Tail = null;

            else Head.Previous = null;

        }

    }

    public void RemoveLast(){

        if(Count !=0 ){

            if(Count == 1){

                Head = null;

                Tail = null;

            } else {

                Tail.Previous.Next = null;

                Tail = Tail.Previous;

            }

        }

    }

    public int Count{get; private set; }

    public void Add(T item){

        AddFirst(item);

    }

    public bool Contains(T item){

        var current = Head;

        while(current != null){

            if(current.Value.Equals(item)) return true;

            current = current.Next;

        }

        return false;

    }

    public void CopyTo(T[] array, int arrayIndex){

        var current = Head;

        while(current != null){

            array[arrayIndex++] = current.Value;

            current = current.Next;

        }

    }

    public bool IsReadOnly { get{return false; }}

    public bool Remove(T item){

        DoublyLinkedListNode<T> previous = null;

        var current = Head;

        while(current != null){

            if(current.Value.Equals(item)){

                if(previous != null){

                    previous.Next = current.Next;

                    if(current.Next == null){

                        Tail = previous;

                    } else {

                        current.Next.Previous = previous;

                    }

                    Count--;

                } else {

                    RemoveFirst();

                }

                return true;

            }

            previous = current;

            current = current.Next;

        }

        return false;

    }

    System.Collections.Generic.IEnumerator<T> System.Collections.Generic.IEnumerable<T>.GetEnumerator(){

        var current = Head;

        while(current != null){

            yield return current.Value;

            current = current.Next;

        }

    }

    System.Collections.IEnumerator System.Collections.IEnumerable.GetEnumerator(){

        return ((System.Collections.Generic.IEnumerable<T>)this).GetEnumerator();

    }

    public void Clear(){

        Head = null;

        Tail = null;

        Count = 0;

    }

}

public class DoublyLinkedListNode<T>

{

    public DoublyLinkedListNode(T val) {

        Value = val;

    }

    public T Value { get; set; }

    public DoublyLinkedListNode<T> Next {get; set;}

    public DoublyLinkedListNode<T> Previous { get; set; }

}

public class LinkedListNode<T>{

    public LinkedListNode(T val){

        Value = val;

    }

    public T Value {get; set;}

    public LinkedListNode<T> Next {get; set;}

}

​

​

public class Node{

    public int Value{get; set;}

    public Node Next {get; set; }

    public Node(int val, Node next){

        Value = val;

        Next = next;

    }

    public Node (int val){

        Value = val;

    }

}