Write the implementation file of the following interface file for a Linked List

Question

Write the implementation file of the following interface file for a Linked List template declared as a Node class template. (Using C++)

//This is the header file which contains type definitions and

//function declarations for manipulating a linked list to store //data of any type T.

//The linked list is given as a pointer of type Node<T>* which //points to the head (first) node of the list.

#ifndef Node_H

#define Node_H

    template<class T>

    class Node

    {

    public:

        Node(const T& theData, Node<T>* theLink) : data(theData), link(theLink){}

        Node<T>* getLink( ) const { return link; }

        const T& getData( ) const { return data; }

        void setData(const T& theData) { data = theData; }

        void setLink(Node<T>* pointer) { link = pointer; }

    private:

        T data;

        Node<T> *link;

    };

    template<class T>

    void headInsert(Node<T>*& head, const T& theData);

    //Precondition: The pointer variable head points to

    //the head of a linked list.

    //Postcondition: A new node containing theData

    //has been added at the head of the linked list.

    template<class T>

    void insert(Node<T>* afterMe, const T& theData);

    //Precondition: afterMe points to a node in a linked list.

    //Postcondition: A new node containing theData

    //has been added after the node pointed to by afterMe.

    template<class T>

    void deleteNode(Node<T>* before);

    //Precondition: The pointers before point to nodes that has

    //at least one node after it in the linked list.

    //Postcondition: The node after the node pointed to by      //before

    //has been removed from the linked list and its storage

    //returned to the freestore.

    template<class T>

    void deleteFirstNode(Node<T>*& head);

    //Precondition: The pointers head points to the first

    //node in a linked list; with at least one node.

    //Postcondition: The node pointed to by head has been removed

    //for the linked list and its storage returned to the freestore.

    template<class T>

    Node<T>* search(Node<T>* head, const T& target);

    //Precondition: The pointer head points to the head of a linked list.

    //The pointer variable in the last node is nullptr. head (first) node

    //head (first) node has been defined for type T.

    //(== is used as the criterion for being equal).

    //If the list is empty, then head is nullptr.

    //Returns a pointer that points to the first node that

    //is equal to the target. If no node equals the target,

    //the function returns nullptr.

}

#endif //Node_H

Explanation / Answer

void headInsert(Node<T>*& head, const T& theData)

{

Node * temp = new Node;

new_node -> data = theData

new_node -> link = Node *head

}

void insert(Node<T>* afterMe, const T& theData)

{

Node * new_node = new Node;

new Node -> theData;

Node *temp = afterMe;

afterMe -> link = new_node;

new_node -> link = temp -> link;

}

void deleteNode(Node<T>* before)

{

Node *temp = before ->link;

before->link = NULL;

before->link = temp -> link;

}

void deleteFirstNode(Node<T>*& head)

{

Node * temp = head->link

head = NULL;

head = temp;

}

Node<T>* search(Node<T>* head, const T& target)

{

Node *target_node = head;

while( target_node -> data != target)

{

target_node = target_node -> link

}

return target_node

Related Questions

Navigate

• Browse (All)
• Browse W
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.