1.6.3.2 Implementation as a Linked List1.6.3.1 Implementation as an Array1.6.3 Queues2 Java with Caffeine

1.6.3.2 Implementation as a Linked List

In this section, we investigate the use of a linked list as the underlying representation of a queue. Here the main problem is that a list only provides access to its head, while in a queue elements have to be added at the tail. We can overcome this problem by maintaining, in addition to the pointer head, a pointer tail which references the last element of the list; whenever a new element is to be added, we link it to the last element and update the tail pointer. This idea is illustrated in the following diagram:


List

List Representation of a Queue
 


The following Java class implements this idea:

  class ListQueue implements Queue
  {
    Node head;
    Node tail;

    public boolean isEmpty()
    {
      return head == null;
    }

    public void enqueue(int e)
    {
      Node node = new Node(e);
      if (head == null)
        head = node;
      else
        tail.next = node;
      tail = node;
    }

    public int dequeue()
    {
      int value = head.value;
      head = head.next;
      if (head == null) tail = null;
      return value;
    }

    public int peek()
    {
      return head.value;
    }
  }

In method enqueue, we set, if the list is empty, the head pointer to the new node. Otherwise, we link the last element with the new node. In both cases, the tail pointer is updated to refer to the new node. In dequeue, we remove the head element by updating the head pointer to point to the next node. If the list becomes empty, we also set the tail pointer to null.

When comparing both queue implementations, the implementation by linked lists seems a bit simpler and has the advantage that there is no a priory bound on the number of elements. However, the array implementation is a bit faster since it does not require the allocation of a new list cell on every enqueue operation; it is therefore preferred if utmost efficiency is required.


© Wolfgang Schreiner; February 3, 2005

1.6.3.2 Implementation as a Linked List1.6.3.1 Implementation as an Array1.6.3 Queues2 Java with Caffeine