DOC PREVIEW
GSU CSC 2320 - CSCI2320 LISTS

This preview shows page 1-2-3-20-21-22-41-42-43 out of 43 pages.

Save
View full document
View full document
Premium Document
Do you want full access? Go Premium and unlock all 43 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 43 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 43 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 43 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 43 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 43 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 43 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 43 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 43 pages.
Access to all documents
Download any document
Ad free experience
Premium Document
Do you want full access? Go Premium and unlock all 43 pages.
Access to all documents
Download any document
Ad free experience

Unformatted text preview:

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 ListsGroceries to be purchasedJob to-do listList of assignments for a courseDean's listCan you name some others??ListList is a collection of things It is homogeneous --- the elements are all of the same typeIt has finite lengthThe elements are arranged sequentiallyLIST ADTCollection of data elementsA sequence with a finite number of data items, all of the same typeBasic operationsConstruction---create a empty list Empty---check if the list is emptyInsert---insert an itemDelete---remove a itemTraverse---go through the list or part of itBuilding a List class It consists of two steps:Design the classImplement the classImplementation of the ListIn this chapter, two approaches to implement List:Array BasedStatic arrayDynamic arrayPointer (Link list) BasedStatic Array based An array is a common choice for storing list elementsElement are sequentialMost languages support arrayAlgorithm development is easyAn array thus seems to be a natural storage structure for implementing a listStatic Array basedNormally sequential orderings of list elements match with array elementsOf course, the array must be large enough to hold all of the list elementsIt means we need to chose carefullyStatic Array basedThree variables we use to tract array:Array--the array that stores the listCapacity--array’s capacitySize--the number of list elements that are stored in the arrayConstructor: Since we use static array, we can let the complier handle the memory allocation, and our constructor only need to set size to 0Empty: only need to check whether size is 0Static Array basedTraverse: Lists are easy traversed using a loop:for index i ranging from 0 to size-1:process array[i]Static Array basedInsert: 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 basedInsert: we need to doCheck the capacityNeed to move array elements to make room for the new elementStatic Array basedAlgorithm 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 basedThe efficiency of this insert algorithm obviously depends on the number of array elements that must be shifted to make room for the new itemIn 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 basedDelete: also requires shifting array elementsFor example, to delete the second item in:23, 25, 34, 48, 56, 61, 79, 82, 89, 91, 99Static Array basedAlgorithm 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 basedThe 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 listIn 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 ListLinked list nodes containData part – stores an element of the listNext part – stores link/pointer to next element (when no next element, null value)Design the list classShould contain at least the following function membersConstructorempty()insert()delete()display()ConstructionTo construct an empty list, we simply make first a null link to indicate that it does not refer to any node:first = null_value;EmptyWe can then perform the Empty operation--- determining whether a list is empty, simply by checking whether first is null:first == null_value?TraverseWe begin by initializing an auxiliary variable ptr to point to the first node:Initialize a variable ptr to point to first nodeProcess data where ptr pointsTraverseTraverse (ctd)set ptr = ptr->next, process ptr->dataContinue until ptr == nullInsertionTo insert a new data value into a linked list, we must first obtain a new node and store the value in its data partThe second step is to connect this new node to existing listTwo cases in this situation: (1) insertion after some element in the list and (2) insertion at the beginning of the listInsertionInsertion To insert 20 after 17Need address of item before point of insertionpredptr points to the node containing 17Get a new node pointed to by newptr and store 20 in itSet 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 node20newptrpredptrInsertionNote: insertion also works at end of listpointer member of new node set to nullInsertion at the beginning of the listpredptr must be set to firstpointer 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 predecessorDelete the first element in the listDeletionDelete node containing 22 from list.Suppose ptr points to the node to be deletedpredptr points to its predecessor (the 17)Do a


View Full Document

GSU CSC 2320 - CSCI2320 LISTS

Download CSCI2320 LISTS
Our administrator received your request to download this document. We will send you the file to your email shortly.
Loading Unlocking...
Login

Join to view CSCI2320 LISTS and access 3M+ class-specific study document.

or
We will never post anything without your permission.
Don't have an account?
Sign Up

Join to view CSCI2320 LISTS 2 2 and access 3M+ class-specific study document.

or

By creating an account you agree to our Privacy Policy and Terms Of Use

Already a member?