Simply Linked Implementation template <class Node entry> struct Node //Node declaration: i Node_ entry entry Node<Node entry> *next Node // constructors Node(Node entry, Node<Node entry> *link=NULL); //constructors }; template <class List_ entry>class List / List declaration: i public // Specifications for the methods of the list adt go here // The following methods replace compiler-generated defaults
Simply Linked Implementation template <class Node_entry> struct Node // Node declaration: { Node_entry entry; Node<Node_entry> *next; Node( ); // constructors Node(Node_entry, Node<Node_entry> *link=NULL); // constructors }; template <class List_entry>class List // List declaration: { public: // Specifications for the methods of the list ADT go here. // The following methods replace compiler-generated defaults
CList(; List(const List<List entry> © void operator=(const List<List entry> ©); protected: // Data members for the linked list implementation now follow. nt count Node<List entry> *head; // The following auxiliary function is used to locate list positions Node<List entry> set_position(int position)const;
~List( ); List(const List<List_entry> ©); void operator=(const List<List_entry> ©); protected: // Data members for the linked list implementation now follow. int count; Node<List_entry> *head; // The following auxiliary function is used to locate list positions Node<List_entry> *set_position(int position) const; };
Actions on a Linked List (a)Stacks 仁- stacks 仁间仁 (sTacks 仁-闻 m--- Eu (d) Stack 闻仁-仁阳 仁可仁
Actions on a Linked List
Finding a List Position Function set position takes an integer parameter position and returns a pointer to the corresponding node of the list Declare the visibility of set position as protected, since set position returns a pointer to, and therefore gives access to, a Node in the list. To maintain an encapsulated data structure, we must restrict the visibility of set position Protected visibility ensures that it is only available as a tool for constructing other methods of the list To construct set position, we start at the beginning of the list and traverse it until we reach the desired node
Finding a List Position ◆Function set position takes an integer parameter position and returns a pointer to the corresponding node of the list. ◆Declare the visibility of set position as protected, since set position returns a pointer to, and therefore gives access to, a Node in the List. To maintain an encapsulated data structure, we must restrict the visibility of set position. Protected visibility ensures that it is only available as a tool for constructing other methods of the List. ◆ To construct set position, we start at the beginning of the List and traverse it until we reach the desired node:
template <class List entry> Node<List entry> *List<List_ entry>: set_position(int position) const /Pre: position is a valid position in the List 0 s position<count Post: Returns a pointer to the Node in position. * i Node<List entry>*q= head; for (int i=0; i<position; i++)q=q->next return g; If all nodes are equally likely then, on average, the set position function must move halfway through the list to find a given position. Hence, on average, its time requirement is approximately proportional to n, the size of the list
template <class List_entry> Node<List_entry> *List<List_entry>::set_position(int position) const /* Pre: position is a valid position in the List ;0 ≤ position<count . Post: Returns a pointer to the Node in position . */ { Node<List_entry> *q = head; for (int i=0; i<position; i++) q=q->next; return q; } ◆If all nodes are equally likely, then, on average, the set position function must move halfway through the List to find a given position. Hence, on average, its time requirement is approximately proportional to n, the size of the List