Singly-linked list queue

Question

I recently learned the core .NET Queue type uses arrays internally, and that this is actually much more efficient. I've had a go at writing a singly-linked list version of a queue, MyQueue.

Running basic stopwatch times against this type and the .NET type shows about 50ms difference when queuing 1 million items and checking the length.

How can it be improved?

MyQueueNode

namespace MyQ.Core
{
    public class MyQueueNode<T> : IMyQueueNode<T>
    {
        private MyQueueNode<T> _nextNode;

        private T _value;

        public MyQueueNode(T value)
        {
            _value = value;
        }

        public void SetNextNode(ref MyQueueNode<T> nextNode)
        {
            _nextNode = nextNode;
        }

        public MyQueueNode<T> GetNextNode()
        {
            return _nextNode;
        }

        public T GetValue()
        {
            return _value;
        }
    }
}

MyQueue

namespace MyQ.Core
{
    public class MyQueue<T> : IMyQueue<T> where T : class
    {
        private volatile MyQueueNode<T> _headNode, _tailNode;

        public void Enqueue(T item)
        {
            MyQueueNode<T> newNode = new MyQueueNode<T>(item);

            if (_headNode == null)
            {
                _headNode = newNode;
                _tailNode = _headNode;
            }
            else
            {
                _tailNode.SetNextNode(ref newNode);
                _tailNode = newNode;
            }

            _length++;
        }

        public T Dequeue()
        {
            if(_headNode == null)
            {
                throw new QueueEmptyException();
            }

            T value = _headNode.GetValue();

            _headNode = _headNode.GetNextNode();

            _length--;

            return value;
        }

        public T Peek()
        {
            if(_headNode == null)
            {
                return null;
            }

            return _headNode.GetValue();
        }

        private long _length = 0;

        public long Length => _length;
    }
}

Answer 1

Don't use volatile in the below line

    private volatile MyQueueNode<T> _headNode, _tailNode;

Link https://www.infoworld.com/article/3229360/application-development/how-to-use-the-volatile-keyword-in-c.html

Answer 2

MyQueueNode:

• where is IMyQueueNode<T>?
• _value can be made readonly
• there is no need for MyQueueNode to be public. You should restrict its access modifier as much as possible. Clients don't need to see your queue internals.
• in SetNextNode there is no need to pass argument by reference

MyQueue:

• QueueEmptyException is not defined.

• Peek method returns null on empty queue. What if there is null as data value? You might consider throwing an exception as seen in Dequeue and let user check queue by checking its length before the Peek is called.

• instead of:

  private long _length = 0;
  public long Length => _length;
  

  you might consider comfortable using auto property (and changing references to _length):

  public long Length { get; private set; }
  

Answer 3

Data Corruption

Your class is not thread-safe. Using the volatile keyword could cause data corruption because of this. Without this keyword, optimizations might occur that read the field only once in a given scope.

Let's have a look at Dequeue. The _headNode is read 3 times into memory, since it's volatile. What if _headNode is not null the 1st read, but gets nullified by another thread before the 2nd read? Exactly, you'll get a NullReferenceException on _headNode.GetValue(); Remove the volatile keyword and gain performance. Your implementation isn't thread-safe anyway.

public T Dequeue()
{
    // atomic read of _headNode 
    if(_headNode == null)
    {
        throw new QueueEmptyException();
    }

    // atomic read of _headNode
    T value = _headNode.GetValue();

    // atomic read of _headNode
    _headNode = _headNode.GetNextNode();

    _length--;

    return value;
}

Collection Compliance

You have provided a custom property Length. It's better to implement ICollection<T> and provide Count. This way, your class is way more reusable.