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;
 }
}

• Lee: This is the complete code, I'm just quite anal about organisation and use those comments to separate methods from member fields and to group methods by functionality, like others might use #region I've removed them so there's no confusion.

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

• t3chb0t: A short explanation why it is bad to use volatile here would be better than just a link.
• Lee: Vishnu are you suggesting I should make the _value field within the node volatile instead of the class that it's contained within? That's what I gather from the article.

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.