chap listsstacksand queues lists we all have an intuitive understanding of what we mean by "list,so our first step is to define precisely what is meant so that this intuitive understanding can eventually be converted into concrete data structure and its operations perhaps the most important concept related to lists is that of position in other wordswe perceive that there is first element in the lista second elementand so on thuswe should view list as embodying the mathematical concepts of sequenceas defined in section we define list to be finiteordered sequence of data items known as elements "orderedin this definition means that each element has position in the list (we will not use "orderedin this context to mean that the list is sorted each list element has data type in the simple list implementations discussed in this all elements of the list have the same data typealthough there is no conceptual objection to lists whose elements have differing data types if the application requires it (see section the operations defined as part of the list adt do not depend on the elemental data type for examplethe list adt can be used for lists of integerslists of characterslists of payroll recordseven lists of lists list is said to be empty when it contains no elements the number of elements currently stored is called the length of the list the beginning of the list is called the headthe end of the list is called the tail there might or might not be some relationship between the value of an element and its position in the list for examplesorted lists have their elements positioned in ascending order of valuewhile unsorted lists have no particular relationship between element values and positions this section will consider only unsorted lists and treat the problems of how to create and search sorted lists efficiently when presenting the contents of listwe use the same notation as was introduced for sequences in section to be consistent with java array indexingthe first position on the list is denoted as thusif there are elements in the listthey are given positions through as ha an- the subscript indicates an element' position within the list using this notationthe empty list would appear as hi before selecting list implementationa program designer should first consider what basic operations the implementation must support our common intuition about lists tells us that list should be able to grow and shrink in size as we insert and remove elements we should be able to insert and remove elements from anywhere in the list we should be able to gain access to any element' valueeither to read it or to change it we must be able to create and clear (or reinitializelists it is also convenient to access the next or previous element from the "currentone