数据结构-链表.ppt

《数据结构-链表.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、Chapter3LinkedListsDataStructureSoftwareCollegeNortheasternUniversityOverviewLinkedListsProgrammingdetailsCommonErrorDoublyLinkedListsCircularlyLinkedListsexamplesCursorsImplementationofLinkedListsDataStructureSoftwareCollegeNortheasternUniversityVariable-lengtharrays?Directa

2、ccesstoelement(Byindexing)Arraysizeisfixed-length-Toexpandthem,youcreateanew,longerarray,andcopythecontentsoftheoldarrayintothenewarrayThisisusedbyfunctionrealloc()inCThisisslow!LineartimeInsertion/RemovalduetoshiftelementsduetocontiguousstorageinmemoryHalfofthelistneedstobem

3、ovedforeitheroperationsDataStructureSoftwareCollegeNortheasternUniversityVariable-lengtharrays?Solution:-Thelistisnotneedtostorecontiguously.-Attachapointertoeachiteminthearray,whichpointstothenextitem.-providestheabilitytoaddorremovetheitemsanywhereinthelistinconstanttimeThi

4、sisalinkedlistLinkedlistsareunbounded(maximumnumberofitemslimitedonlybymemory)DataStructureSoftwareCollegeNortheasternUniversityTheLinkedListdatastructure[0][1][2]arrayABCArrayHeadABCLinkedlistAndataitemplusitspointeriscalledanodeAnodecontainsdataitemandoneormorelinks.-Thelin

5、kisareferencetoanode.-ThelinkoflastnodeissettoNULLa“head”whichisapointertothefirstnodeinthelinkedlistnodeDataStructureSoftwareCollegeNortheasternUniversityZHAOQIANSUNLIZHOUWUZHENGWANG^H43131NULL3771925DataItemLinksLIQIANSUNWANGWUZHAOZHENGZHOUAddress1713192531374331HHeaderAsim

6、plesingleLinkedListDataStructureSoftwareCollegeNortheasternUniversityMemoryStorageoflinkedlistWecanaccessallnodesthroughpointer“head”HeapDataStructureSoftwareCollegeNortheasternUniversityLinkedlistsEachnodecontainstheaddressofthenextoneinthelist.Wecanaccessthefirstnodethrough

7、pointer“head”twoimportantpointer:-head:thereferencetothefirstnode-tail:thereferencetothelastnodeDataStructureSoftwareCollegeNortheasternUniversityHowtoimplementate?DataStructureSoftwareCollegeNortheasternUniversityDefinitionoftheclassUsingmulticlassClassofNode(ListNode)Classo

8、fListClassofIteratorTypeofDefinitioncompoundinsideDataStructureSoftw