table summarizes the speeds of the various general-purpose data storage structures using big notation table general-purpose data storage structures data structure search insertion deletion traversal array (no( ( -ordered array (logno(no(no(nlinked list (no( ( -ordered linked list (no(no(no(nbinary tree (averageo(logno(logno(logno(nbinary tree (worst caseo(no(no(no(nbalanced tree (averageand worst caseo(logno(logno(logno(nhash table ( ( ( -insertion in an unordered array is assumed to be at the end of the array the ordered array uses binary searchwhich is fastbut insertion and deletion require moving half the items on the averagewhich is slow traversal implies visiting the data items in order of ascending or descending keysthe -means this operation is not supported special-purpose data structures the special-purpose data structures discussed in this book are the stackthe queueand the priority queue these structuresinstead of supporting database of user-accessible dataare usually used by computer program to aid in carrying out some algorithm we've seen examples of this throughout this booksuch as in "graphs,and "weighted graphs,where stacksqueuesand priority queues are all used in graph algorithms stacksqueuesand priority queues are abstract data types (adtsthat are implemented by more fundamental structure such as an arraylinked listor (in the case of the priority queuea heap these adts present simple interface to the usertypically allowing only insertion and the ability to access or delete only one data item these items are for stacksthe last item inserted for queuesthe first item inserted