lecture4 Linked Lists

《lecture4 Linked Lists》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、ListsCS122AlgorithmsandDataStructures
Alistisavarying-length,linearcollectionofhomogeneouselements.
Linearmeanseachlistelement(exceptthefirst)hasauniquepredecessor,andeachelement(exceptthelast)hasauniqueMW11:00am-12:15pm,MSEC101successorInstructor:XiaoQin
Inalinearstructure,componentscanonlybeacce

2、ssedsequentiallyoneaftertheLecture4:LinkedListsother2Lists(cont.)ListsasADTs
Domain
Itnormallyhastwo"special"named–Acollectionelementsofthesametypeelementscalledheadandtail.They–Animplicitlistcursorintherange1throughn+1wherenisthecurrentlengthofthelist.pointtothefirstandlastelementofthe
Operations

3、list.–create():createanewlist.Shouldbedoneusingconstructors–BooleanIsEmpty()&BooleanIsFull():returnstrueifthelistisemptyandfullrespectively–voidInsertBeginning(v)&voidInsertEnd(v):Insertthevalueveitherintheendorthebeginningofthelist–voidDelete():itematlistcursordeleted–print():PrintthewholelistMor

4、eListOperationsArray-basedclassList
Operations–insertAfter(v,anotherV):insertthevaluevafterthefirstoccurrenceofanotherV.IsEmpty–insertBefore(v,anotherV):InsertthevaluevIsFullPrivatedata:beforethefirstoccurrenceofanotherV.Lengthlength–search(v):searchforthefirstoccurrenceofvinthelistandreturnitspos

5、ition.CouldbeusedtohelptheInsertdata[0]implementationofseveralotheroperations[1]–deleteAll(v):DeletealloccurrencesofvinthelistDelete[2]–reset():Listcursorisatfrontoflist.IsPresent[MAX_LENGTH-1]
Wecanassumethatprivatedatainalistincludesthelistsitself(usinganarrayorlinkedlist),thePrinthead,thetailan

6、dthesizeofthelistSortedList61//ARRAY-BASEDLIST(list.h)constintMAX_LENGTH=50;typedefintItemType;HowtoImplementaListclassSortedList{public://publicmemberfunctions
useabuilt-inarraystoredincontiguousmemorySortedList();//constructorlocations,implementingoperationsInsertandboolIsEmpty()const;Deletebymo

7、vinglistitemsaroundinthearray,boolIsFull()const;intLength()const;//returnslengthoflistasneededvoidInsert(ItemTypeitem);voidDelete(ItemTypeitem);
usealinkedlist(toavoidexcessivedataboolIsPresent(ItemTypeitem)const