Chapter ListsConsider Every Day ListsListLIST ADTBuilding a List classImplementation of the ListStatic Array basedStatic Array basedSlide 9Slide 10Slide 11Slide 12Slide 13Slide 14Slide 15Slide 16Slide 17List Implantation by Linked listLinked ListDesign the list classConstructionEmptyTraverseSlide 24InsertionSlide 26Slide 27DeletionSlide 29DeletionLinked Lists - AdvantagesLinked Lists - DisadvantagesOutlinePointer Based NodeSlide 35Array-Based Implementation of Linked ListsHow to do it???Slide 38Slide 39How to do Insertion???Slide 41How to do Deletion???Implementation DetailsChapter ListsDr. Bernard Chen Ph.D.University of Central ArkansasSpring 2009Consider 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 sequentiallyLIST 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 itBuilding a List class It consists of two steps:Design the classImplement the classImplementation of the ListIn this chapter, two approaches to implement List:Array BasedStatic arrayDynamic arrayPointer (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 after the element 48: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: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: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 bestList 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 nullInsertion at the beginning of the listpredptr must be set to firstpointer member of newptr set to that value (Where first points to)first set to value of newptrIn all cases, no shifting of list elements is required !Deletion For deletion, there are also two cases to consider:Deleting an element that has a predecessorDelete the first element in the listDeletionDelete node containing 22 from list.Suppose ptr points to the node to be deletedpredptr points to its predecessor (the 17)Do a
View Full Document