require complete traversal to find the end of the list figure illustrates sample linked list with the two external references size qtail qhead queue (linkedfigure an instance of the queue adt implemented as linked list the complete implementation of the queue adt using linked list with tail reference is provided in listing rememberthe individual nodes in the list contain the individual items in the queue when dequeueing an itemwe must unlink the node from the list but return the item stored in that node and not the node itself an evaluation of the time-complexities is left as an exercise listing the llistqueue py module implementation of the queue adt using linked list class queue creates an empty queue def __init__self )self _qhead none self _qtail none self _count returns true if the queue is empty def isemptyself )return self _qhead is none returns the number of items in the queue def __len__self )return self _count adds the given item to the queue def enqueueselfitem )node _queuenodeitem if self isempty(self _qhead node else self _qtail next node self _qtail node self _count + removes and returns the first item in the queue def dequeueself )assert not self isempty()"cannot dequeue from an empty queue node self _qhead if self _qhead is self _qtail self _qtail none (listing continued