Create custom Queue class with O(1) Enqueue and O(1) Dequeue I am implementing a Queue class in C# using a Node/LinkedList class that I also implemented, and I wonder if there is a way to implement the enqueue and the dequeue methods, both in algorithmic efficiency of \$O(1)\$.

In the Queue class I have a field of the tail and the head, and I managed to implement the enqueue method in \$O(1)\$, but the dequeue is \$O(n)\$.

This is the code for the Node and the Queue classes:

public class Node&lt;T&gt;
{
    #region Fields

    private Node&lt;T&gt; next;
    private T data;

    #endregion Fields


    #region Constructors

    public Node(T data, Node&lt;T&gt; next)
    {
        this.data = data;
        this.next = next;
    }

    public Node(T data) : this(data, null)
    {

    }

    #endregion Constructors


    #region Properties

    public Node&lt;T&gt; Next
    {
        get { return next; }
        set { next = value; }
    }

    public T Data
    {
        get { return data; }
        set { data = value; }
    }

    #endregion Properties


    #region Methods

    public bool HasNext()
    {
        return next != null;
    }

    #endregion Methods
}




public class Queue&lt;T&gt;
{
    private Node&lt;T&gt; head;
    private Node&lt;T&gt; tail;

    public Queue()
    {
        head = null;
        tail = null;
    }

    public void Enqueue(T data)
    {
        if (IsEmpty())
            head = new Node&lt;T&gt;(data);
        else if (tail == null)  // There is only one element in the queue
            tail = new Node&lt;T&gt;(data, head);
        else
            tail = new Node&lt;T&gt;(data, tail);
    }

    public T Dequeue()
    {
        if (IsEmpty())
            throw new InvalidOperationException("The queue is empty");

        T data = head.Data;

        if (tail == null)  // There is only one element in the queue
        {
            head = null;
            return data;
        }

        Node&lt;T&gt; temp = tail;

        while (temp.Next != head)  // Get the previous Node of the head
            temp = temp.Next;

        temp.Next = null;
        head = temp;

        if (tail == head)
            tail = null;

        return data;
    }

    public T Head()
    {
        if (IsEmpty())
            throw new InvalidOperationException("The queue is empty");

        return head.Data;
    }

    public bool IsEmpty()
    {
        return head == null;
    }
}
This is your bottleneck in retrieving the new head at removal, which can not be avoided in a Singly-Linked structure, so it's \$O(n)\$.


while (temp.Next != head)  // Get the previous Node of the head
    temp = temp.Next;



Doubly-Linked

If you want fast removal \$O(1)\$, you can do so at the cost of slightly slower insertion. You'd need to augment the queue to a doubly linked queue:

var previous = head.Previous;
head.Previous = null;
head = previous;
head.Next = null;


Make sure at insertion, you'll set both Previous as Next references on the relevant nodes.

Circular Doubly-Linked

If you make the queue circular, you don't even need to store the tail, only the head. The tail would be head.Previous; In case of a single element, since it's circular, head.Previous would point to head. Make sure in iterators to terminate at head, instead of at null.