Write a C++ program with three files for each linked list : Implement double lin

Question

Write a C++ program with three files for each linked list

: Implement double linked list ADT to store a collection of integers.

Make sure to provide an interactive user interface to test these new functions in the main() for grader .

Your ADT will include the following member functions: --- a default constructor --- the "big-3": destructor, copy constructor and overloaded assignment operator

1. a member function pushFront(data) that inserts a node with data at the front of the list

2. a member function pushBack(data) that appends a node with data at the back of the list

3. a member function popFront() that removes first node of the list.

4. a member function popBack() that removes last node of the list.

5. a member function insert(index, val) that inserts a new node with value "val" at a specific position mentioned by the index argument.

6. a member function deleteDuplicates(val) that deletes a node with that number and all its copies from the list, where these copies can be located anywhere in the list.

7. a member function mtoLastElement(M) that returns Mth to the last element of a list such that when M = 0, the last element of the list is returned.

8. a member function size() that returns the size of the list.

9. an overloaded put operator (<<) to print out all the data items stored in a linked list. Note that you are recommended to overload this operator as a friend function of the LinkedList class.

10. a member function reverseList() that reverses a linked list without recreating a temporary copy of this linked list. In other words, your function CAN NOT use the 'new' operator. Here is an example, if a list contains the following data items, 3 -> 5 -> 1 -> 7; this reverse() function will change the list to 7 -> 1 -> 5 -> 3.

Explanation / Answer

#include <iostream>

using namespace std;

class DoubleLinkedList{
    private:
        struct Node{
            int data;
            Node* next;
            Node* prev;

            Node(int item=0, Node* n=NULL, Node* p=NULL):data(item), next(n), prev(p){}

        };

    public:
        int theSize;
        Node* head;
        Node* tail;
        //Default Constructor
        DoubleLinkedList(){
            theSize = 0;
            head= NULL;
            tail = NULL;
        }

        //copy constructor
        DoubleLinkedList(DoubleLinkedList &List){
            Node* n = List.head;
            while(n != NULL){
                pushBack(n->data);
                n = n->next;
            }
        }

        //Destructor
        ~DoubleLinkedList(){
            Node* n = head;
            while(n != NULL){
                oldn = n;
                n = n->next;
                delete oldn;
            }
        }
        //overloaded assignment operator
        DoubleLinkedList & operator=(const DoubleLinkedList& List){
            DoubleLinkedList Copy = List;
            swap(*this, Copy);
            return *this;
        }

        void pushFront(int data){
            Node* n = new Node(data);
            n->next = head->next;
            head->next->prev = n;
            head = n;
        }

        void pushBack(int data){
            Node* n = new Node(data);
            n->prev = tail;
            tail->next = n;
            tail = n;
        }

        int popFront(){
            if (theSize == 0)
                return 0;
            int item = head->data;
            Node* oldhead = head;
            head = head->next;
            delete oldhead;
            return item;
        }

        int popBack(){
            if(theSize == 0)
                return 0;
            int item = tail->data;
            if(theSize==1){
                delete head;
                head = tail = NULL;
                return item;
                }
            oldtail = tail;
            tail = tail->prev;
            delete oldtail;
            tail->next = NULL;
            return item;
        }

};

Related Questions

Navigate

• Browse (All)
• Browse W
• Subjects

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