This program implements a deque - a double-ended queue. It uses a doubly-linked list and provides the following methods:

  • PushLeft
  • PushRight
  • PopLeft - remove an item from the left end
  • PopRight - remove an item from the right end
using System;

namespace ConsoleTest
{
    class Program
    {
        static void Main(string[] args)
        {
            Deque d = new Deque();

            Console.WriteLine("*** PushLeft A B C ***");
            d.PushLeft("A");
            d.ShowItems();
            d.PushLeft("B");
            d.ShowItems();
            d.PushLeft("C");
            d.ShowItems();

            Console.WriteLine("*** PopLeft ***");
            d.PopLeft();
            d.ShowItems();

            Console.WriteLine("*** PopRight ***");
            d.PopRight();
            d.ShowItems();

            Console.WriteLine("*** PushRight D E ***");
            d.PushRight("D");
            d.ShowItems();
            d.PushRight("E");
            d.ShowItems();

            Console.WriteLine("*** PopLeft ***");
            d.PopLeft();
            d.ShowItems();

            Console.WriteLine("*** PopLeft ***");
            d.PopLeft();
            d.ShowItems();

            Console.WriteLine("*** PopLeft ***");
            d.PopLeft();
            d.ShowItems();

            Console.ReadKey();
        }

        class Deque where T : class
        {
            private DoubleNode first; 
            private DoubleNode last;  
            private int N; // the size of deque

            public bool IsEmpty { get { return first == null; } } // the same as N == 0
            public int Size { get { return N; } }

            // Add an item to the left end.
            public void PushLeft(T item)
            {
                DoubleNode oldFirst = first;
                first = new DoubleNode();
                first.Item = item;
                first.Next = oldFirst;
                first.Prev = null;

                // Adjust the last item if necessary.
                if (oldFirst == null) // check if this is the first item pushed
                    last = first;
                else
                    oldFirst.Prev = first; // otherwise, update the former first node

                ++N;
            }

            // Add an item to the right end.
            public void PushRight(T item)
            {
                DoubleNode oldLast = last;
                last = new DoubleNode();
                last.Item = item;
                last.Next = null;
                last.Prev = oldLast;

                // Adjust the first item if necessary.
                if (oldLast == null) // check if this is the first item pushed
                    first = last;
                else
                    oldLast.Next = last; // otherwise, update the former last node

                ++N;
            }

            // Remove an item from the left end.
            public T PopLeft()
            {
                if (first == null)
                    return default(T);

                T item = first.Item;

                first = first.Next;

                if (first != null)
                    first.Prev = null;
                else
                    last = null; // there are no more nodes in the list

                return item;
            }

            // Remove an item from the right end.
            public T PopRight()
            {
                if (first == null)
                    return default(T);

                T item = last.Item;

                last = last.Prev;

                if (last != null)
                    last.Next = null;
                else
                    first = null; // there are no more nodes in the list

                return item;
            }

            // ShowItems traverses all the items in the list.
            public void ShowItems()
            {
                for (DoubleNode node = first; node != null; node = node.Next)
                {
                    Console.WriteLine("{0}: {1}-{0}-{2}",
                        node.Item.ToString(),
                        (node.Prev != null ? node.Prev.Item.ToString() : "."),
                        (node.Next != null ? node.Next.Item.ToString() : ".")
                    );
                }
                Console.WriteLine("First = {0}->{1}", (first != null ? first.Item.ToString() : "null"), (first != null && first.Next != null ? first.Next.Item.ToString() : "null"));
                Console.WriteLine("Last  = {0}->{1}", (last != null ? last.Item.ToString() : "null"), (last != null && last.Next != null ? last.Next.Item.ToString() : "null")); // last.Next should always be null
                Console.WriteLine();
            }

            private class DoubleNode
            {
                public T Item { get; set; }
                public DoubleNode Prev { get; set; }
                public DoubleNode Next { get; set; }

                public override string ToString() { return (Item == null ? "null" : Item.ToString()); }
            }
        }
    }
}

Output:

*** PushLeft A B C ***
A: .-A-.
First = A->null
Last  = A->null

B: .-B-A
A: B-A-.
First = B->A
Last  = A->null

C: .-C-B
B: C-B-A
A: B-A-.
First = C->B
Last  = A->null

*** PopLeft ***
B: .-B-A
A: B-A-.
First = B->A
Last  = A->null

*** PopRight ***
B: .-B-.
First = B->null
Last  = B->null

*** PushRight D E ***
B: .-B-D
D: B-D-.
First = B->D
Last  = D->null

B: .-B-D
D: B-D-E
E: D-E-.
First = B->D
Last  = E->null

*** PopLeft ***
D: .-D-E
E: D-E-.
First = D->E
Last  = E->null

*** PopLeft ***
E: .-E-.
First = E->null
Last  = E->null

*** PopLeft ***
First = null->null
Last  = null->null