_bagiterator curnode bag size head figure sample bag and bagiterator objects at the beginning of the for loop more ways to build linked list earlier in the we saw that new nodes can be easily added to linked list by prepending them to the linked structure this is sufficient when the linked list is used to implement basic container in which linear order is not neededsuch as with the bag adt but linked list can also be used to implement container abstract data type that requires specific linear ordering of its elementssuch as with vector adt in additionsome implementationssuch as in the case of the set adtcan be improved if we have access to the end of the list or if the nodes are sorted by element value using tail reference the use of single external reference to point to the head of linked list is sufficient for many applications in some instanceshoweverwe may need to append items to the end of the list instead appending new node to the list using only head reference requires linear time since complete traversal is required to reach the end of the list instead of single external head referencewe can use two external referencesone for the head and one for the tail figure illustrates sample linked list with both head and tail reference head tail figure sample linked list using both head and tail external references appending nodes adding the external tail reference to the linked list requires that we manage both references as nodes are added and removed consider the process of appending new node to non-empty listas illustrated in figure (afirsta new node is created to store the value to be appended to the list thenthe node is linked