Chapter ListsConsider Every Day ListsListBuilding a List classDesign the list classLIST ADTImplementation of the ListStatic Array basedStatic Array basedSlide 10Slide 11Slide 12Slide 13Slide 14Slide 15Slide 16Slide 17Slide 18OutlineList Implantation by Linked listLinked ListSlide 22ConstructionEmptyTraverseSlide 26InsertionSlide 28Slide 29DeletionSlide 31DeletionLinked Lists - AdvantagesLinked Lists - DisadvantagesSlide 35Pointer Based NodeSlide 37Array-Based Implementation of Linked ListsHow to do it???Slide 40Slide 41How to do Insertion???Slide 43How to do Deletion???Chapter ListsDr. Bernard Chen Ph.D.University of Central ArkansasFall 2010Consider Every Day ListsGroceries to be purchasedJob to-do listList of assignments for a courseDean's listCan you name some others??ListList is a collection of things It is homogeneous --- the elements are all of the same typeIt has finite lengthThe elements are arranged sequentiallyBuilding a List class It consists of two steps:Design the classImplement the classDesign the list classDesigning a class to implement an ADT consist of identifying “functions” members that are need to be carry outIt is important that we describe the function members independently of how the class will be implementedFunction members must be describe in some manner that does not depend on any particular representation of the objectsLIST ADTCollection of data elementsA sequence with a finite number of data items, all of the same typeBasic operationsConstruction---create a empty list Empty---check if the list is emptyInsert---insert an itemDelete---remove a itemTraverse---go through the list or part of itImplementation of the ListIn this chapter, two approaches to implement List:Array BasedPointer (Link list) BasedStatic Array based An array is a common choice for storing list elementsElement are sequentialMost languages support arrayAlgorithm development is easyAn array thus seems to be a natural storage structure for implementing a listStatic Array basedNormally sequential orderings of list elements match with array elementsOf course, the array must be large enough to hold all of the list elementsIt means we need to chose carefullyStatic Array basedThree variables we use to tract array:Array--the array that stores the listCapacity--array’s capacitySize--the number of list elements that are stored in the arrayConstructor: Since we use static array, we can let the complier handle the memory allocation, and our constructor only need to set size to 0Empty: only need to check whether size is 0Static Array basedTraverse: Lists are easy traversed using a loop:for index i ranging from 0 to size-1:process array[i]Static Array basedInsert: it’s more complicated For example: if we wish to insert the new value 56 (item) after the element 48 (position):Original--- 23, 25, 34, 48, 61, 79, 82, 89, 91, 99Produce---23, 25, 34, 48, 56, 61, 79, 82, 89, 91, 99Static Array basedInsert: we need to doCheck the capacityNeed to move array elements to make room for the new elementStatic Array basedAlgorithm for insert Given variable: pos (where to insert), item (value to insert):If size is equal to capacity: display error due to limit spaceIf pos < 0 or pos > size: display error due to error positionElse: for i in rangeing from size to pos+1:array[i]=array[i-1] //C++ starts index from 0array[pos]=itemsize++Static Array basedThe efficiency of this insert algorithm obviously depends on the number of array elements that must be shifted to make room for the new itemIn worst case, the new item must be inserted at the beginning of the list O(n)The best case occurs when the new item is inserted at the end of it O(1)Two important special kinds of lists for which are stacks and queuesStatic Array basedDelete: also requires shifting array elementsFor example, to delete the second item in:23, 25, 34, 48, 56, 61, 79, 82, 89, 91, 99Static Array basedAlgorithm for delete:Given variable: pos (where to delete),If size is zero:issue a error messageIf pos <0 or pos >=size:issue an error message Otherwise:for index i ranging from pos to size-2:array[i]=array[i+1]size--Static Array basedThe computing time of such a function is easily seen to be the same as insert function --- O(n) in the worst case and O(1) for the bestOutlinelinked lists implementation An Array-Based Implementation of Linked ListsList Implantation by Linked listIn any structure used to store the elements of a list, it must be possible to perform at least the following operation:1. Locate the First element2. Given the location of any list element, find its successor3. Locate the end of the listLinked ListLinked list nodes containData part – stores an element of the listNext part – stores link/pointer to next element (when no next element, null value)Design the list classShould contain at least the following function membersConstructorempty()insert()delete()display()ConstructionTo construct an empty list, we simply make first a null link to indicate that it does not refer to any node:first = null_value;EmptyWe can then perform the Empty operation--- determining whether a list is empty, simply by checking whether first is null:first == null_value?TraverseWe begin by initializing an auxiliary variable ptr to point to the first node:Initialize a variable ptr to point to first nodeProcess data where ptr pointsTraverseTraverse (ctd)set ptr = ptr->next, process ptr->dataContinue until ptr == nullInsertionTo insert a new data value into a linked list, we must first obtain a new node and store the value in its data partThe second step is to connect this new node to existing listTwo cases in this situation: (1) insertion after some element in the list and (2) insertion at the beginning of the listInsertionInsertion To insert 20 after 17Need address of item before point of insertionpredptr points to the node containing 17Get a new node pointed to by newptr and store 20 in itSet the next pointer of this new node equal to the next pointer in its predecessor, thus making it point to its successor. Reset the next pointer of its predecessor to point to this new node20newptrpredptrInsertionNote: insertion also works at end of listpointer member of new node set to
View Full Document