Question

In: Computer Science

The List method addAll(i,c) inserts all elements of the Collection c into the list at position...

The List method addAll(i,c) inserts all elements of the Collection c into the list at position i. (The add(i,x) method is a special case where c = {x}.) Explain why, for the data structures in this chapter, it is not efficient to implement addAll(i,c) by repeated calls to add(i,x). Design and implement a more efficient implementation.

Solutions

Expert Solution

PLEASE GIVE IT A THUMBS UP, I SERIOUSLY NEED ONE, IF YOU NEED ANY MODIFICATION THEN LET ME KNOW, I WILL DO IT FOR YOU

List.h

#ifndef LIST_H
#define LIST_H

#include <iostream>
#include <stdlib.h>
#include <stdio.h>
#include <set>

using namespace std;

template <typename T>
struct LinkNode
{
    T val;
    LinkNode *link;
};

template <class T>
class List
{
private:
    typedef LinkNode<T> Node;
    Node *head;
    int count;

public:
    List();
    ~List();
    bool isEmpty() const;
    int size() const;

    bool add(int i, T x);
    bool addALL(int i, set<T> c);

    T get(int i) const;
    void printList() const;
};

#endif

Main.cpp

#include "List.h"

template <typename T>
List<T>::List()
{
        head = nullptr;
        count = 0;
}

template <typename T>
List<T>::~List()
{
        Node *tmp0;
        Node *tmp1 = head;

        while (tmp1 != nullptr)
        {
                tmp0 = tmp1;
                tmp1 = tmp1->link;
                delete tmp0;
        }
}

template <typename T>
bool List<T>::isEmpty() const
{
        if (count == 0)
                return true;
        else
                return false;
}

template <typename T>
int List<T>::size() const
{
        return count;
}

template <typename T>
bool List<T>::add(int idx, T x)
{
        if (idx == 0)
        {
                Node *newNode = new Node();
                newNode->val = x;
                newNode->link = head;
                head = newNode;
                count += 1;
                return true;
        }

        if (idx < count)
        {

                Node *prevNode = nullptr;
                Node *curNode = head;
                Node *newNode = new Node();
                newNode->val = x;
                int i;
                for (i = 0; (i < idx) & (curNode != nullptr); i++)
                {
                        prevNode = curNode;
                        curNode = curNode->link;
                }

                if ((i == idx) & (prevNode != nullptr))
                {
                        prevNode->link = newNode;
                        newNode->link = curNode;
                }
                else
                {
                        newNode->link = head;
                        head = newNode;
                }
                count += 1;
        }
        else
        {
                cout << "Index out of bounds \n";
                return false;
        }
}

template <typename T>
bool List<T>::addALL(int idx, set<T> c)
{
        if (idx < count)
        {
                int i;
                Node *prevNode = nullptr;
                Node *nextNode = head;
                Node *newNode = new Node();
                // find the Link where to insert given idx
                for (i = 0; (i < idx) & (nextNode != nullptr); ++i)
                {
                        //cout << "Inside Loop - prev " << prevNode << " nextNode " << nextNode << " I : " << i << "\n";
                        prevNode = nextNode;
                        nextNode = nextNode->link;
                }

                //cout << "Inserting After " << prevNode->val << " At " << i << " , given idx : " << idx << " Node \n";

                // start inserting the
                for (auto itr = c.crbegin(); itr != c.crend(); ++itr)
                {
                        newNode = new Node();
                        newNode->val = *itr;
                        // If inserting first node check if its head node
                        if (itr == c.crbegin())
                        {
                                if ((i == idx) & (prevNode != nullptr))
                                {
                                        prevNode->link = newNode;
                                        //cout << " Non head node \n";
                                }
                                else
                                {
                                        newNode->link = head;
                                        head = newNode;
                                }
                                prevNode = newNode;
                                //cout << "Setting the prev Node \n";
                        }
                        else
                        {

                                //cout << "Setting prev_link to new node " << prevNode->val << " to " << newNode->val << "\n";
                                prevNode->link = newNode;
                                prevNode = newNode;
                        }
                        count += 1;
                }
                // set the last inserted node link to nextNode from the top
                //cout <<" Setting the last node" << prevNode->val << " to " << nextNode->val << " \n";
                prevNode->link = nextNode;
        }
        else
        {
                cout << "Index out of bounds \n";
                return false;
        }
}

template <typename T>
T List<T>::get(int idx) const
{
        Node *curNode = head;
        int i;

        if (idx < count)
        {
                for (i = 0; (i < idx) & (curNode != nullptr); i++)
                {
                        curNode = curNode->link;
                }

                if ((i == idx) && (curNode != nullptr))
                        return curNode->val;

                else
                        return NULL;
        }
        else
        {
                cout << "GET:: Index out of range \n";
                return NULL;
        }
}

template <typename T>
void List<T>::printList() const
{
        Node *curNode = this->head;

        cout << " List : ( ";
        for (int i = 0; (i < this->count) & (curNode->link != nullptr); i++)
        {
                cout << curNode->val << ", ";
                curNode = curNode->link;
        }
        cout << curNode->val << " ) \n";
}

int main()
{
        List<int> ll;
        set<int> s1 = {3, 4, 5, 6, 9, 10, 12, 15};

        set<int> s2 = {351, 45};
        set<int> s3 = {450, 345};

        ll.add(0, 25);
        cout << "Size : " << ll.size() << " ; ";
        ll.printList();
        ll.add(0, 35);
        cout << "Size : " << ll.size() << " ; ";
        ll.printList();

        cout << "Trying to insert add(2,390) \n";
        ll.add(2, 390);
        cout << "Size : " << ll.size() << " ; ";
        ll.printList();

        ll.addALL(1, s2);
        cout << "Size : " << ll.size() << " ; ";
        ll.printList();

        ll.addALL(3, s1);
        cout << "Size : " << ll.size() << " ; ";
        ll.printList();

        cout << "Tyring to insert addAll(12,s3) \n";
        ll.addALL(12, s3);
        cout << "Size : " << ll.size() << " ; ";
        ll.printList();
}

venereology answered 1 month ago
Next > < Previous

Related Solutions

Complete the code(in C) that inserts elements into a list. The list should always be in...
Complete the code(in C) that inserts elements into a list. The list should always be in an ordered state. #include <stdio.h> #include <stdlib.h> /* list of nodes, each with a single integer */ struct element { struct element *next; int value; }; /* protypes for functions defined after main */ struct element *elementalloc(void); struct element *listinitialize(); struct element *insertelement(struct element *, int); void printlist(struct element *); /* main * Creates an ordered list * Elements added to the list must...
Complete the code that inserts elements into a list. The list should always be in an...
Complete the code that inserts elements into a list. The list should always be in an ordered state. #include <stdio.h> #include <stdlib.h> /* list of nodes, each with a single integer */ struct element { struct element *next; int value; }; /* protypes for functions defined after main */ struct element *elementalloc(void); struct element *listinitialize(); struct element *insertelement(struct element *, int); void printlist(struct element *); /* main * Creates an ordered list * Elements added to the list must be...
Complete the code that inserts elements into a list. The list should always be in an...
Complete the code that inserts elements into a list. The list should always be in an ordered state. #include <stdio.h> #include <stdlib.h> /* list of nodes, each with a single integer */ struct element { struct element *next; int value; }; /* protypes for functions defined after main */ struct element *elementalloc(void); struct element *listinitialize(); struct element *insertelement(struct element *, int); void printlist(struct element *); /* main * Creates an ordered list * Elements added to the list must be...
Complete the code that inserts elements into a list. The list should always be in an...
Complete the code that inserts elements into a list. The list should always be in an ordered state. #include <stdio.h> #include <stdlib.h> /* list of nodes, each with a single integer */ struct element { struct element *next; int value; }; /* protypes for functions defined after main */ struct element *elementalloc(void); struct element *listinitialize(); struct element *insertelement(struct element *, int); void printlist(struct element *); /* main * Creates an ordered list * Elements added to the list must be...
Complete the code that inserts elements into a list. The list should always be in an...
Complete the code that inserts elements into a list. The list should always be in an ordered state. #include <stdio.h> #include <stdlib.h> /* list of nodes, each with a single integer */ struct element { struct element *next; int value; }; /* protypes for functions defined after main */ struct element *elementalloc(void); struct element *listinitialize(); struct element *insertelement(struct element *, int); void printlist(struct element *); /* main * Creates an ordered list * Elements added to the list must be...
Complete the code that inserts elements into a list. The list should always be in an...
Complete the code that inserts elements into a list. The list should always be in an ordered state. ----------------------------------------------------------------------------------------------------------------- #include <stdio.h> #include <stdlib.h> /* list of nodes, each with a single integer */ struct element { struct element *next; int value; }; /* protypes for functions defined after main */ struct element *elementalloc(void); struct element *listinitialize(); struct element *insertelement(struct element *, int); void printlist(struct element *); /* main * Creates an ordered list * Elements added to the list must...
In C++ please. 3. splice() is a specialized method that inserts one list into another in...
In C++ please. 3. splice() is a specialized method that inserts one list into another in constant time but destroys the first list. Explain why this may be implemented for the list but not for any other sequential container. Give an example usage of splice()
method to remove all elements frrom my linked list (java)
method to remove all elements frrom my linked list (java)
write a recursive method that returns the product of all elements in java linked list
write a recursive method that returns the product of all elements in java linked list
Let A be a collection of sets, then We defined A’ = Union of all elements...
Let A be a collection of sets, then We defined A’ = Union of all elements of A. Definition: If A = NOT the union of C and D , where C and D are non empty sub-collection, such that C’ intersect D’ = empty Then A is coherent. Prove: if A is coherent then A’ is connected (i.e A’ is not the union of two separated sets in standard topology)
ADVERTISEMENT
Subjects
ADVERTISEMENT
Latest Questions
ADVERTISEMENT