0
\$\begingroup\$

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<T>
{
    #region Fields

    private Node<T> next;
    private T data;

    #endregion Fields


    #region Constructors

    public Node(T data, Node<T> next)
    {
        this.data = data;
        this.next = next;
    }

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

    }

    #endregion Constructors


    #region Properties

    public Node<T> 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<T>
{
    private Node<T> head;
    private Node<T> tail;

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

    public void Enqueue(T data)
    {
        if (IsEmpty())
            head = new Node<T>(data);
        else if (tail == null)  // There is only one element in the queue
            tail = new Node<T>(data, head);
        else
            tail = new Node<T>(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<T> 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;
    }
}
\$\endgroup\$

closed as off-topic by Peter Taylor, VisualMelon, Dannnno, ferada, Vogel612 Sep 3 at 12:13

This question appears to be off-topic. The users who voted to close gave these specific reasons:

  • "Code not implemented or not working as intended: Code Review is a community where programmers peer-review your working code to address issues such as security, maintainability, performance, and scalability. We require that the code be working correctly, to the best of the author's knowledge, before proceeding with a review." – Dannnno, ferada, Vogel612
  • "Lacks concrete context: Code Review requires concrete code from a project, with sufficient context for reviewers to understand how that code is used. Pseudocode, stub code, hypothetical code, obfuscated code, and generic best practices are outside the scope of this site." – Peter Taylor, VisualMelon
If this question can be reworded to fit the rules in the help center, please edit the question.

  • \$\begingroup\$ Have you tested this? Does it actually do something yet? \$\endgroup\$ – Mast Aug 29 at 18:28
  • \$\begingroup\$ @Mast yes, it works, but I want to find out if there is a way for the Dequeue method to be \$O(1)\$ instead of \$O(n)\$. \$\endgroup\$ – Dani Aug 31 at 17:19
  • \$\begingroup\$ Welcome to Code Review! I'm afraid this question does not match what this site is about. Code Review is about improving existing, working code. Code Review is not the site to ask for help in fixing or changing what your code does. Once the code does what you want, we would love to help you do the same thing in a cleaner way! Please see our help center for more information. \$\endgroup\$ – Vogel612 Sep 3 at 12:12
2
\$\begingroup\$

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.

\$\endgroup\$
  • 2
    \$\begingroup\$ Cheater! Writing off-topic reviews and restoring them when the question is fixed :-P \$\endgroup\$ – t3chb0t Aug 28 at 10:44
  • \$\begingroup\$ Who could have seen that missing Node class? :p \$\endgroup\$ – dfhwze Aug 28 at 10:57
  • \$\begingroup\$ @dfhwze Why the line head.Previous = null; is needed? The line head.Next = null; won't delete the reference to the old head? (so the garbage collector will delete it anyway, even if I didn't set the previous to null). \$\endgroup\$ – Dani Aug 28 at 18:47
  • \$\begingroup\$ You are right, it's just a proper way to clean references. By not clearing the previous reference on the former head, you'd might want to reuse that head later on. There is a thing called 'cloacking' in which a 'removed' node could put itself back in the list. \$\endgroup\$ – dfhwze Aug 28 at 18:49
  • \$\begingroup\$ Be careful though by asserting it will be garbage collected. Even though the queue no longer references the old head, a consumer may still hold a reference to it. So removing the reference to Previous is required. \$\endgroup\$ – dfhwze Aug 28 at 19:31

Not the answer you're looking for? Browse other questions tagged or ask your own question.