using System;

using System.Collections.Generic;

​

public class Deque<T>

{

    private class ListNode

    {

        public T Element

        { get; set; }

​

        public ListNode NextNode

        { get; set; }

​

        public ListNode PreviousNode

        { get; set; }

​

        public ListNode(T element)

        {

            this.Element = element;

            NextNode = null;

            PreviousNode = null;

        }

        public ListNode(T element, ListNode prevNode)

        {

            this.Element = element;

            prevNode.NextNode = this;

            this.PreviousNode = prevNode;

        }

        public ListNode(ListNode nextNode, T element)

        {

            this.Element = element;

            nextNode.PreviousNode = this;

            this.NextNode = nextNode;

        }

    }

    private ListNode head;

    private ListNode tail;

    private int count;

    public Deque()

    {

        this.head = null;

        this.tail = null;

        this.count = 0;

    }

    public void AddLast(T item)

    {

        if (this.head == null)

        {

            this.head = new ListNode(item);

            this.tail = this.head;

        }

        else

        {

            ListNode newNode = new ListNode(item, this.tail);

            //this.tail.NextNode = newNode;

            this.tail = newNode;

        }

        this.count++;

    }

    public void AddFirst(T item)

    {

        if (this.head == null)

        {

            this.head = new ListNode(item);

            this.tail = this.head;

        }

        else

        {

            ListNode newNode = new ListNode(this.head, item);

            //this.tail.NextNode = newNode;

            this.head = newNode;

        }

        this.count++;

    }

    public T RemoveFirst()

    {

        ListNode removedNode = this.head;

        if (this.head == null)

        {

            throw new ArgumentNullException("Deque is empty");

        }

        this.head = this.head.NextNode; 

        count--;

        return removedNode.Element;

    }

    public T RemoveLast()

    {

        ListNode removedNode = this.tail;

        if (this.head == null)

        {

            throw new ArgumentNullException("Deque is empty");

        }

        this.tail = this.tail.PreviousNode; 

        count--;

        return removedNode.Element;

    }

    public int Count

        {

            get {return this.count;}

        }

}

​

public class DoublyLinkedListTest

{

    public static void Main()

    {

        Deque<string> shoppingList = new Deque<string>();

        shoppingList.AddFirst("Milk");

        shoppingList.AddFirst("Honey");

        shoppingList.AddFirst("Olives");

        shoppingList.AddFirst("Water");

        shoppingList.AddLast("Fruits");

        shoppingList.AddLast("Juice");

        Console.WriteLine(shoppingList.RemoveFirst());

        Console.WriteLine(shoppingList.RemoveLast());

        shoppingList.AddLast("Beer");

        shoppingList.RemoveFirst();

​

    }

}

​

/*Implement the data structure "Deque". This is a specific list-like

structure, similar to stack and queue, allowing to add elements at the

beginning and at the end of the structure. Implement the operations

for adding and removing elements, as well as clearing the deque. If an

operation is invalid, throw an appropriate exception.*/