How to build a queue (linked list implementation)

Queue is a data structure based on first in first out (FIFO) policy. In other words, the order of processing tasks depends on the order in which those tasks are added. A good real-life example is a queue in a store or a queue of people waiting in an airport.

A queue implements two basic operations:

• Enqueue - adds an item to the end of the collection
• Dequeue - removes an item from the beginning of the collection

 

 

Our implementation will be based on a linked list. The main building block in a linked list is a Node. In our case, it's a nested Node class.

    private sealed class Node
    {
        public Node Next;
        public T Value;
    }

We are going to use a queue with head and tail links.

• head points to the first node
• tail points to the last node

The head and tail links make it easy to enqueue a new item to the tail and dequeue an item from the head.

Enqueue method:

    public void Enqueue(T value)
    {
        Node oldTail = _tail;
        _tail = new Node
        {
            Value = value
        };
    
        if (IsEmpty())
        {
            _head = _tail;
        }
        else
        {
            oldTail.Next = _tail;
        }
    }

The queue is empty if there are no nodes in it. In other words, the head points to null:

    private bool IsEmpty()
    {
        return _head == null;
    }

The dequeue method removes an item from the beginning of the queue.

    public T Dequeue()
    {
        T result = _head.Value;
        _head = _head.Next;
        return result;
    }

Full implementation:

    public class Queue<T>
    {
        private Node _head;
        private Node _tail;

        public void Enqueue(T value)
        {
            Node oldTail = _tail;
            _tail = new Node
            {
                Value = value
            };

            if (IsEmpty())
            {
                _head = _tail;
            }
            else
            {
                oldTail.Next = _tail;
            }
        }

        public T Dequeue()
        {
            T result = _head.Value;
            _head = _head.Next;
            return result;
        }

        private bool IsEmpty()
        {
            return _head == null;
        }

        private sealed class Node
        {
            public Node Next;
            public T Value;
        }
    }

Note: The above code is not production ready, it does not check all corner cases. The main goal is to show how Queue can be implemented and what is under the hood.