Data StructuresWhat You Will LearnIntroductionSelf-Referential ClassesSlide 5Dynamic Memory AllocationSlide 7Linked ListsLists and Linked ListsLinked ListSlide 11Slide 12Declaration for a Linked ListDynamic Allocation of List NodesDynamic AllocationLinking Nodes TogetherCharacteristics of Singly Linked ListsConstructing a ListConstructing List (version 2)Constructing a List (Version 2)Slide 21Slide 22Slide 23Traversing a ListRecursive List TraversalSlide 26InsertionsLinked Lists - Removing NodesDeletionsSlide 30Slide 31Disadvantages of Dynamic Linked ListHead NodesDoubly Linked ListsCircular Linked ListsCircular Linked ListStacksSlide 38Stacks -- ApplicationsQueuesQueues -- ApplicationsTreesSlide 43Slide 441Data StructuresChapter 152What You Will LearnListsListsQueuesQueuesTreesTreesStacksStacks3IntroductionPreviously used fixed sized data structuresarraysstructsNow we will use dynamic data structuresthey will grow and shrink during executionExamplesstacksqueuesbinary trees4Self-Referential ClassesA self-referential class contains a pointer member that points to a class object of the same class typeclass Part_node { public: Part_node ( ); … private: char part_num[8], descrip[20]; int qty; float price; Part_node *next_part; } ;class Part_node { public: Part_node ( ); … private: char part_num[8], descrip[20]; int qty; float price; Part_node *next_part; } ;5Self-Referential ClassesThis pointer to an object of the type being declared enables class objects to be linked together in various waysThis is how we get linked lists, stacks, queues0PointervariableLinkPointerMemberNullPointer6Dynamic Memory AllocationIf the data structures are to be dynamic, then dynamic memory allocation is requiredoperators new and delete are essential part_node *newPtr = new part_node; part_node *newPtr = new part_node; Creates thenew pointerAllocates the space fora new part node07Dynamic Memory AllocationThe delete operator deallocates memory allocated with the newNote: newPtr is not itself deleted -- rather the space newPtr points to 0 delete newPtr; delete newPtr;8Linked ListsDefinition <=> A list of self-referential class objectscalled nodesconnected by pointer links (thus, a "linked" list)Subsequent nodes accessed via link-pointer member stored in each memberLink pointer in last node set to null (zero)marks the end of the listNodes created dynamically, as needed9Lists and Linked ListsCriteria for choosing linked listmust be linear, homogeneous datarules out sets & recordsordering does not depend on time of insertionrules out FIFO, LIFOsequential access is sufficientrules out need for arrayfrequent insert, delete and requirement for sorting10Linked ListCollection of structs (called nodes)One member is the data memberAt least one other member of the struct gives location of next member This makes it self referentialhead77-3/-3/4411Linked ListNodes do not necessarily occupy consecutive memory locationsTwo ways to implementDynamic data with pointers (this is what our text is advocating)Also possible to use built in arrays12Linked ListAbstractions that are implemented using built-in typesI m p l e m e n t a t i o n H i e r a r c h y f o r a l i s t A D TB u i l t - i n A r r a yB u i l t - i n D y n a m i cd a t a a n d p o i n t e r sB u i l t - i n A r r a yL i n k e d L i s tL i s t13Declaration for a Linked List// Declarationstruct NodeType;typedef Nodetype* NodePtr;struct NodeType{ SomeDataType data; NodePtr link; };NodePtr head;NodePtr visitPtr;Forward (incomplete)declarationForward (incomplete)declarationCompletedeclarationCompletedeclaration14Dynamic Allocation of List Nodes// Allocate a new dynamic objecthead = new NodeType;(*head).data = 345;Newly allocated object is a struct with 2 members345345headdatalink15Dynamic Allocation(*head).data (*head) is pointer dereferencing .data is struct selectionEquivalent (and easier to use) head ->dataThus we could have said head->data =345;16Linking Nodes TogetherHead->link refers to …Thus head->link = new NodeTypewill allocate a second NodeType struct, pointed to by the link element of the firstThen think what happens ...head->link->data = 12;head->link->link = NULL;345345headdatalink17Characteristics of Singly Linked ListsIn previous slide, head is a pointer only, not a node on the list*head is the struct pointed to by the headhead->link or (*head).link is the address of the second struct*(head->link) or *((*head).link) is the entire second structhead->link->data is the data member of the second struct18Constructing a ListAlgorithmhead = new NodeType;currentPtr = head;do { currentPtr->link = NULL; // do something with currentPtr->data if (! done) { currentPtr->link = new NodeType; currentPtr =currentPtr->link; } } while (! done);19Constructing List (version 2)ReadCities (/*out*/ CityPtr& cityList){CityPtr inNode;CityName tempName;cityList = Null;while (cin >> tempName) { inNode = new CityNode; strcpy (inNode->name, tempName); cin >> inNode->population; cin >> inNode->numVoters; inNode->next = cityList; cityList = inNode; }}ReadCities (/*out*/ CityPtr& cityList){CityPtr inNode;CityName tempName;cityList = Null;while (cin >> tempName) { inNode = new CityNode; strcpy (inNode->name, tempName); cin >> inNode->population; cin >> inNode->numVoters; inNode->next = cityList; cityList = inNode; }}20Constructing a List (Version 2)inNodeinNodecityListcityListLongview7550NULL21Constructing a List (Version 2)inNodeinNodecityListcityListLongview7550NULLTyler806022Constructing a List (Version 2)inNodeinNodecityListcityListLongview7550NULLTyler8060Dallas100050023Constructing a List (Version 2)inNodeinNodecityListcityListLongview7550NULLTyler8060Dallas1000500Hallsville21(Remember this is a reference parameter)24Traversing a ListGeneral algorithmvisitPtr = head;while (visitPtr != NULL) { // do something with the visitPtr -> data visitPtr = visitPtr -> link;}25Recursive List TraversalRecursive routinevoid visit_list ( /* in */ visit_ptr NodePtr) { if (visit_ptr != NULL) { visit_list (visit_ptr->link); cout << visit_ptr -> data; } }Note that data is printed in reverse order of original inputRecursive CallRecursive Call26Linked ListsManipulate pointers