The Basics of linked structures A linked structure is made up of nodes each containing both the information that is to be stored as an entry of the structure and a pointer telling where to find the next node in the structure We shall refer to these nodes making up a linked structure as the nodes of the structure, and the pointers we often call links Since the link in each node tells where to nd the next node of the structure, we shall use the name next to designate this link
The Basics of Linked Structures A linked structure is made up of nodes, each containing both the information that is to be stored as an entry of the structure and a pointer telling where to find the next node in the structure. We shall refer to these nodes making up a linked structure as the nodes of the structure, and the pointers we often call links. Since the link in each node tells where to nd the next node of the structure, we shall use the name next to designate this link
We shall use a struct rather than a class to implement nodes struct node i Node entry entry; //data members Node米next; Node; / constructors Node(node entry item, Node*add on=NULL); constructors Node∷Node() next = NULL i Node Node(node entry item, Node * add on=NULL fentry =item; next= add on; 1
We shall use a struct rather than a class to implement nodes. struct Node { Node_entry entry; // data members Node *next; Node( ); // constructors Node(Node_entry item, Node *add_on = NULL); // constructors }; Node :: Node( ) { next = NULL ; } Node :: Node(Node_entry item, Node *add_on = NULL ) { entry = item ; next = add_on; }
Example: Node First nodea); // Node First node stores data Node *p0=& First node; //p0 points to First Node Node *p1= new Node b );//A second node storing"b'is created p0->next=p1; / The second Node is linked after First node Node*p2= new Node('c, po);// A third Node storing ' is created // The third Node links back to the First node, * p0 p1->next= p2; //The third Node is linked after the second Node p125 Figure 4.8
Example: Node First_node ('a'); // Node First_ node stores data 'a' . Node *p0 = & First_ node; // p0 points to First_ Node . Node *p1 = new Node('b'); // A second node storing 'b' is created. p0->next = p1; // The second Node is linked after First_ node . Node *p2 = new Node('c', p0); // A third Node storing 'c' is created. // The third Node links back to the First_ node,*p0 . p1->next = p2; // The third Node is linked after the second Node . p125 Figure 4.8
4.2 Linked Stacks p129 Figure 4.10 e Class Declaration for Linked stack class stack i public Stack(; bool empty)const; Error code push(const Stack_ entry &item); Error code pop(; Error code top(Stack entry &item)const protected: Node top node; }
4.2 Linked Stacks p129 Figure 4.10 Class Declaration for Linked Stack class Stack { public: Stack( ); bool empty( ) const; Error_code push(const Stack_entry &item); Error_code pop( ); Error_code top(Stack_entry &item) const; protected: Node *top_node; };
Benefits of Class Implementation Maintain encapsulation: If we do not use a class to contain our stack, we lose the ability to set up methods for the stack Maintain the logical distinction between the stack itself, made up of all of its entries each in a node) and the top of the stack, which is a pointer to a single node. o Maintain consistency with other data structures and other implementations, where structures are needed to collect severa methods and pieces of information
Benefits of Class Implementation Maintain encapsulation: If we do not use a class to contain our stack, we lose the ability to set up methods for the stack. Maintain the logical distinction between the stack itself, made up of all of its entries (each in a node), and the top of the stack,which is a pointer to a single node. Maintain consistency with other data structures and other implementations,where structures are needed to collect several methods and pieces of information