Lecture Programming in C++ - Chapter 16: Data structures and recursion. On completion of this chapter students will know how to: Create a linked list, create a stack, create a queue, create a binary tree, identify recursive functions. | Chapter 16 – Data Structures and Recursion Data Structures Built-in Array struct User developed linked list stack queue tree Lesson Programmer-defined Linked List Class Data members (could be different types) stored in (usually) contiguous block of memory One of the data members is a pointer variable Address stored points to the next object Data member that has address creates link between objects Each object referred to as a node Lesson Linked List Representation Lesson Head node Object 2 Object 3 Object 4 Objects in linked list link Pointer variable value Fact that address points to next object Actions on Linked List Must go node to node from head node Can delete node by making address that points to one to be deleted to next object Can insert node by changing address stored in pointer variable for node preceding location of insertion Can move node from one location to another Must keep track of current node and head node Lesson Linked List Classes Use two . | Chapter 16 – Data Structures and Recursion Data Structures Built-in Array struct User developed linked list stack queue tree Lesson Programmer-defined Linked List Class Data members (could be different types) stored in (usually) contiguous block of memory One of the data members is a pointer variable Address stored points to the next object Data member that has address creates link between objects Each object referred to as a node Lesson Linked List Representation Lesson Head node Object 2 Object 3 Object 4 Objects in linked list link Pointer variable value Fact that address points to next object Actions on Linked List Must go node to node from head node Can delete node by making address that points to one to be deleted to next object Can insert node by changing address stored in pointer variable for node preceding location of insertion Can move node from one location to another Must keep track of current node and head node Lesson Linked List Classes Use two classes to create linked list Node class Holds only the data All data members public because no function members Second used to manipulate nodes One variable holds address of first object in list Another variable holds current node address Lesson Node Class General form: Lesson class Node { public: type member1; type member2; Node* next_node; }; Class name Data types (not necessarily all the same) Identifiers representing node data Name for storing address of next node in list Second Class Used to manipulate the nodes Data only pointer variables used to hold addresses Lesson class Llist { private: Node* head; Node* current; public: void make_list ( ); void show_list ( ); }; Address of node being manipulated Address of first object Stack Data structure created using linked list model With stack can perform only two fundamental operations Push Insert node immediately after the head Pop Retrieve and delete node immediately after head Only work with nodes at top Lesson .
