Can a queue be represented by a circular linked list with only one pointer pointing to the tail of the queue?

1 answer

Answer

1272947

2026-08-11 19:15

+ Follow

Yes.

With a linked list, each node in the list points to the next node, except the tail which points to nothing. To maintain the list we must keep track of the head node at all times. In order that all insertions and extractions occur in constant time, all insertions and extractions must occur at the head. Thus when we insert a new node, it simply points to the head and then becomes the head. And to extract the head, the next node from the head becomes the head before we delete the old head. Since all insertions and extractions occur at the head, linked lists can be used to implement a stack (last in, first out). We can also traverse the list from the head and insert at any point in the list in order to maintain a sorted order, however this cannot be done in constant time and there are more efficient ways of maintaining order than by a linked list.

In order to implement a queue (first in, first out) using a linked list, we need to maintain a pointer to the tail as well as the head. Extractions still occur at the head, as before but insertions now occur at the tail, where the tail points to the new node which then becomes the tail. However, rather than maintaining a separate pointer for the head, we can simply point the tail at the head, thus creating a circular linked list. Since the tail always points at the head we have constant time access to both through a single pointer. Insertions are only slightly more complicated in that new nodes must first point at the head node (which they can copy from the tail node) before the tail node points to the new node which then becomes the tail.

ReportLike(0ShareFavorite

Copyright © 2026 eLLeNow.com All Rights Reserved.