Queue implementation using linked list

Question

I have implemented a queue data structure using linked list in C#. I have also associated my implementation with unit tests. Is this implementation correct? Any suggestion?

namespace QueueDataStructure
{
 internal class Node
 {
 internal int value;
 internal Node next;
 }
 public class Queue
 {
 private Node head;
 private int size;
 public Queue(){}
 public void Enqueue(int n)
 {
 if(head == null) // queue is empty
 {
 head = new Node{
 value = n,
 next = null
 };
 }
 else // queue has items
 {
 var oldHead = head;
 head = new Node
 {
 value = n,
 next = oldHead
 };
 }
 size++;
 }
 public int? Dequeue()
 {
 if (size == 0)
 return null;
 var node = head;
 Node previous = node;
 while (node.next != null)
 {
 previous = node;
 node = node.next;
 }
 previous.next = null;
 size--;
 return node.value;
 }
 public int Count
 {
 get { return size; }
 }
 public string PrintElements()
 {
 var node = head;
 int[] elements = new int[size];
 int i = 0;
 while (node != null)
 {
 elements[i++] = node.value;
 node = node.next;
 }
 return string.Join(" ", elements);
 }
 }
}

---

using Microsoft.VisualStudio.TestTools.UnitTesting;
using QueueDataStructure;
namespace TestQueue
{
 [TestClass]
 public class Tests
 {
 [TestMethod]
 public void TestQueue()
 {
 var queue = new Queue();
 Assert.AreEqual(0, queue.Count);
 Assert.AreEqual(null, queue.Dequeue());
 queue.Enqueue(1);
 queue.Enqueue(2);
 queue.Enqueue(3);
 Assert.AreEqual(3, queue.Count);
 Assert.AreEqual("3 2 1", queue.PrintElements());
 Assert.AreEqual(1, queue.Dequeue());
 Assert.AreEqual(2, queue.Dequeue());
 Assert.AreEqual(3, queue.Dequeue());
 Assert.AreEqual(0, queue.Count);
 }
 }
}

Answer 1

There is an strong feel of Shlemiel the painter’s algorithm in removing entries from the queue. The longer the queue, the longer it takes. Adding a reference to the tail will prevent this.

Also, this is pretty much a textbook example of something to which we can apply generics.

public class Queue<T>
{
 private readonly static Node<T> HeadNode = new Node<T>(default(T));
 private readonly Node<T> _head;
 private Node<T> _tail;
 public Queue()
 {
 _head = HeadNode;
 _tail = _head;
 }
 public int Count { get; private set; }
 public void Enqueue(T value)
 {
 _tail = _tail.Add(value);
 Count++;
 }
 public T Dequeue()
 {
 Count--;
 return _head.Remove(); 
 }
 public override string ToString()
 {
 return string.Join(" ", GetValues().Select(v => v.ToString()));
 }
 private IEnumerable<T> GetValues()
 {
 var current = _head.Next;
 while(current != null)
 {
 yield return current.Value;
 current = current.Next;
 }
 }
 # region Node
 private class Node<TNode>
 {
 public Node(T value)
 {
 Value = value;
 }
 public T Value { get; }
 public Node<T> Next { get; private set; }
 public Node<T> Add(T value)
 {
 Next = new Node<T>(value);
 return Next;
 }
 public T Remove()
 {
 if(Next == null)
 {
 throw new InvalidOperationException();
 }
 var ret = Next.Value;
 Next = Next.Next;
 return ret;
 }
 }
 #endregion 
}

• There is no need for the Node class to be visible outside the Queue. It is an implementation detail of the Queue.
• Adding the permanent _head removes any need for null checks
• size and Count can be merged.
• Moving the Add() and Remove() operations into the Node defines the interface for the Node in terms of operations one can perform on it, rather than in terms of the visible members. We can't erroneously scribble on either the Value or the Next reference.

• Vogel612: the "permanent _head" is often called "sentinel"

Answer 2

Good

• You are following the .NET Naming Guidelines
• The variables are in the correct scope

Review

Omitting braces {} although they might be optional can lead to hidden and therfore hard to track down bugs. I would like to encourage you to always use them.

---

Regarding public string PrintElements() I would suggest to simply override ToString() which is more idiomatic.

---

If we take a closer look at the Enqueue(int n) method we notice that the difference between the if and the else part is simply the value of next. We can remove this code duplication by adding a variable Node node and assign head like so

public void Enqueue(int n)
{
 Node node = head;
 head = new Node
 {
 value = n,
 next = node
 };
 
 size++;
} 

much better, isn't it ?

---

A C# developer would expect from a Queue that if the Queue is empty (in your case if size == 0) a call to Dequeue() would throw an InvalidOperationException.

Answer 3

In addition to excellent answers above, I'd add interface implementation - a typical .NET/C# generic data structure, such as the System.Collections.Generic.Queue<T> class, can be passed in to functions or stored in other data containers as an IEnumerable<T>. Here's an example implementation of IEnumerable<T> (you'd need to make your queue generic):

public class Queue<T> : IEnumerable<T>
{
 //...
 //Your code
 //...
 public IEnumerator<T> GetEnumerator()
 {
 return new QueueEnumerator(this);
 }
 IEnumerator IEnumerable.GetEnumerator()
 {
 return GetEnumerator();
 }
 //Inner class
 private class QueueEnumerator : IEnumerator<T>
 {
 private Queue<T> queue;
 private Node<T> currentNode;
 public QueueEnumerator(Queue<T> queue)
 {
 this.queue = queue;
 }
 public T Current => currentNode.value;
 object IEnumerator.Current => Current;
 public void Dispose() { }
 public bool MoveNext()
 {
 if(queue.head == null)
 {
 return false;
 }
 if(currentNode == null)
 {
 currentNode = queue.head;
 return true;
 }
 if(currentNode.next == null)
 {
 return false;
 }
 currentNode = currentNode.next;
 return true;
 }
 public void Reset()
 {
 currentNode = null;
 }
 }
}

NOTE: Since your Enqueue method inserts before head, you'd need to modify the enumeration accordingly, or change Enqueue method to insert after head, or make you backing linked list a doubly-linked list (so you can traverse it backwards from tail to head).