Question

In: Computer Science

In C++ please: In this lab we will creating two linked list classes: one that is...

In C++ please:

In this lab we will creating two linked list classes: one that is a singly linked list, and another that is a doubly linked list ( This will be good practice for your next homework assignment where you will build your own string class using arrays and linked list ) .

These LinkedList classes should both be generic classes. and should contain the following methods:

  • Print

  • Add - Adds element to the end of the linked list.

  • IsEmpty

  • Push - Adds element to the beginning of the linked list

  • InsertAt - Inserts an element at a given position

  • Clear - Removes all elements from the linked list

  • Contains - Returns true if element is in the linked list

  • Get - Returns a value at a specific position

  • IndexOf - Returns the first position where an element occurs, -1 if not

  • LastOf - Returns the last position where an element occurs, -1 if not

  • Remove - Removes the last item added to the list

  • RemoveAt - Removes an element at a specific position

  • RemoveElement - Removes the first occurrence of a specific element

  • Size

  • Slice - Returns a subset of this linked list given a beginning position start and end position stop.

You will also count the number of operations that is performed in each method and will calculate the RUN-TIME of each method, as well as calculating the BIG O, OMEGA and THETA notation of each method. This information should be written in a comment block before each method ( you may count the number of operations on each line if you want ).

Solutions

Expert Solution

SINGLY LINKED LIST PROGRAM

#include <iostream>
using namespace std;

template<typename T>
struct node {
        node<T>* next;
        T data;
};

template<typename T>
class SinglyLinkedList
{
public:
        node<T>* first;
        SinglyLinkedList<T>() {
                first = NULL;
        }
        
        // OMEGA = Ω(n)
        // THETA = Θ(n)
        // BIG O = O(n)
        void Print(){
                node<T>* curr = this->first;
                while(curr != NULL){
                        cout<<curr->data<<" ";
                        curr = curr->next;
                }
                cout<<endl;
        }
        
        // OMEGA = Ω(1)
        // THETA = Θ(n)
        // BIG O = O(n)
        void Add(T data) {
                if(first == NULL) {
                        // The list is empty
                        first = new node<T>;
                        first->data = data;
                        first->next = NULL;
                } 
                else {
                        // The list isn't empty
                        node<T>* curr = first;
                        while(curr->next != NULL){
                                curr = curr->next;
                        }
                        node<T>* temp = new node<T>;
                        temp->data = data;
                        temp->next = NULL;
                        curr->next = temp;
                }
        }
        
        // OMEGA = Ω(1)
        // THETA = Θ(1)
        // BIG O = O(1)
        
        bool isEmpty(){
                if(this->first == NULL){
                        return true;
                }
                return false;
        }
        
        // OMEGA = Ω(1)
        // THETA = Θ(1)
        // BIG O = O(1)
        
        void Push(T data){
                if(first == NULL) {
                        // The list is empty
                        first = new node<T>;
                        first->data = data;
                        first->next = NULL;
                } 
                else{
                        node<T>* temp = new node<T>;
                        temp->data = data;
                        temp->next = first;
                        first = temp;
                }
        }
        
        // OMEGA = Ω(1)
        // THETA = Θ(n)
        // BIG O = O(n)
        
        void InsertAt(T data, int pos){
                if(pos==0){
                        Push(data);
                }
                else{
                        node<T>* curr = first;
                        for(int i=1;i<pos-1;i++){
                                curr = curr->next;
                        }
                        node<T>* temp = new node<T>;
                        temp->data = data;
                        temp->next = curr->next;
                        curr->next = temp;
                }
        }
        
        // OMEGA = Ω(1)
        // THETA = Θ(1)
        // BIG O = O(1)
        
        void Clear(){
                this->first = NULL;
        }
        
        // OMEGA = Ω(1)
        // THETA = Θ(n)
        // BIG O = O(n)
        
        bool Contains(T data){
                node<T>* curr = first;
                while(curr != NULL){
                        if(curr->data == data){
                                return true;
                        }
                        curr = curr->next;
                }
                return false;
        }
        
        // OMEGA = Ω(1)
        // THETA = Θ(n)
        // BIG O = O(n)

        T get(int index) {
                if(index == 0) {
                        // Get the first element
                        return this->first->data;
                } else {
                        // Get the index'th element
                        node<T>* curr = this->first;
                        for(int i = 0; i < index; ++i) {
                                curr = curr->next;
                        }
                        return curr->data;
                }
        }
        
        // OMEGA = Ω(1)
        // THETA = Θ(n)
        // BIG O = O(n)
        
        int IndexOf(T data){
                int index = -1;
                node<T>* curr = this->first;
                while(curr != NULL){
                        if(curr->data == data){
                                return index+1;
                        }
                        curr = curr->next;
                        index++;
                }
                return -1;
        }
        
        // OMEGA = Ω(n)
        // THETA = Θ(n)
        // BIG O = O(n)
        
        int LastOf(T data){
                int index = 0;
                int ans = -1;
                
                node<T>* curr = this->first;
                while(curr != NULL){
                        if(curr->data == data){
                                ans = index;
                        }
                        index++;
                        curr = curr->next;
                }
                return ans;
        }
        
        // OMEGA = Ω(n)
        // THETA = Θ(n)
        // BIG O = O(n)
        
        void Remove(){
                node<T>* prev = NULL;
                node<T>* curr = first;
                while(curr->next != NULL){
                        prev = curr;
                        curr = curr->next;
                }
                prev->next = NULL;
        }
        
        // OMEGA = Ω(1)
        // THETA = Θ(n)
        // BIG O = O(n)
        
        void RemoveAt(int pos){
                node<T>* curr = this->first;
                node<T>* prev = NULL;
                if(pos==0){
                        first = first->next;
                }
                else{
                        for(int i=1;i<pos;i++){
                                prev = curr;
                                curr = curr->next;
                        }
                        prev->next = curr->next;
                        curr->next = NULL;
                }
        }
        
        // OMEGA = Ω(1)
        // THETA = Θ(n)
        // BIG O = O(n)
        
        void RemoveElement(T data){
                if(first->data == data){
                        first = first->next;
                }
                else{
                        node<T>* curr = this->first;
                        node<T>* prev = NULL;
                        while(curr != NULL){
                                prev = curr;
                                curr = curr->next;
                                if(curr->data == data){
                                        prev->next = curr->next;
                                        break;
                                }
                        }
                }
                
        }
        
        // OMEGA = Ω(n)
        // THETA = Θ(n)
        // BIG O = O(n)
        
        int Size(){
                int cnt = 0;
                node<T>* curr = this->first;
                while(curr != NULL){
                        cnt++;
                        curr = curr->next;
                }
                return cnt;
        }
        
        // OMEGA = Ω(n)
        // THETA = Θ(n)
        // BIG O = O(n)
        
        node<T>* Slice(int start,int end){
                int l = end - start + 1;
                node<T>* curr = this->first;
                for(int i=1;i<start;i++){
                        curr = curr->next;
                }
                return curr;
        }

};


int main() {
        SinglyLinkedList<std::string> list;
        list.Add("Hello");
        list.Print();
        list.Push("Hi");
        list.Print();
        list.InsertAt("Bye",1);
        list.Print();
        list.Add("Akash");
        list.Print();
        if(list.isEmpty()){
                cout<<"List is Empty "<<endl;
        }
        else{
                cout<<"List is not empty"<<endl;
        }
        cout<<"Size = "<<list.Size()<<endl;
        cout<<"Element at position 1 is "<<list.get(1)<<endl;
        if(list.Contains("X")){
                cout<<"List contains X"<<endl;
        }
        else{
                cout<<"List does not contain X"<<endl;
        }
        cout<<"Position of the word Akash is "<<list.IndexOf("Akash")<<endl;
        cout<<"Last Position of the word Akash is "<<list.LastOf("Akash")<<endl;
        list.RemoveElement("Akash");
        cout<<"After removing Akash from the list "<<endl;
        list.Print();
        return 0;
}

SAMPLE OUTPUT

Hello 
Hi Hello 
Hi Bye Hello 
Hi Bye Hello Akash 
List is not empty
Size = 4
Element at position 1 is Bye
List does not contain X
Position of the word Akash is 3
Last Position of the word Akash is 3
After removing Akash from the list 
Hi Bye Hello 

DOUBLY LINKED LIST PROGRAM

#include <iostream>
using namespace std;

template<typename T>
struct node {
        node<T>* next;
        node<T>* prev;
        T data;
};

template<typename T>
class DoublyLinkedList
{
public:
        node<T>* first;
        node<T>* last;
        DoublyLinkedList<T>() {
                first = NULL;
                last = NULL;
        }
        
        // OMEGA = Ω(n)
        // THETA = Θ(n)
        // BIG O = O(n)
        void Print(){
                node<T>* curr = this->first;
                while(curr != NULL){
                        cout<<curr->data<<" ";
                        curr = curr->next;
                }
                cout<<endl;
        }
        
        // OMEGA = Ω(1)
        // THETA = Θ(1)
        // BIG O = O(1)
        void Add(T data) {
                if(first == NULL) {
                        // The list is empty
                        first = new node<T>;
                        first->data = data;
                        first->next = NULL;
                        first->prev = NULL;
                        last = first;
                } 
                else {
                        // The list isn't empty
                        if(last == first) {
                                // The list has one element
                                last = new node<T>;
                                last->data = data;
                                last->next = NULL;
                                last->prev = first;
                                first->next = last;
                        } else {
                                // The list has more than one element
                                node<T>* temp = new node<T>;
                                temp->data = data;
                                temp->next = NULL;
                                temp->prev = last;
                                last->next = temp;
                                last = temp;
                        }
                }
        }
        
        // OMEGA = Ω(1)
        // THETA = Θ(1)
        // BIG O = O(1)
        
        bool isEmpty(){
                if(this->first == NULL){
                        return true;
                }
                return false;
        }
        
        // OMEGA = Ω(1)
        // THETA = Θ(1)
        // BIG O = O(1)
        
        void Push(T data){
                if(first == NULL) {
                        // The list is empty
                        first = new node<T>;
                        first->data = data;
                        first->next = NULL;
                        first->prev = NULL;
                } 
                else{
                        node<T>* temp = new node<T>;
                        temp->data = data;
                        temp->next = first;
                        temp->prev = NULL;
                        first->prev = temp;
                        first = temp;
                }
        }
        
        // OMEGA = Ω(1)
        // THETA = Θ(n)
        // BIG O = O(n)
        
        void InsertAt(T data, int pos){
                if(pos==0){
                        Push(data);
                }
                else{
                        node<T>* curr = first;
                        for(int i=1;i<pos-1;i++){
                                curr = curr->next;
                        }
                        node<T>* temp = new node<T>;
                        temp->data = data;
                        temp->next = curr->next;
                        temp->prev = curr;
                        curr->next->prev = temp;
                        curr->next = temp;
                }
        }
        
        // OMEGA = Ω(1)
        // THETA = Θ(1)
        // BIG O = O(1)
        
        void Clear(){
                this->first = NULL;
        }
        
        // OMEGA = Ω(1)
        // THETA = Θ(n)
        // BIG O = O(n)
        
        bool Contains(T data){
                node<T>* curr = first;
                while(curr != NULL){
                        if(curr->data == data){
                                return true;
                        }
                        curr = curr->next;
                }
                return false;
        }
        
        // OMEGA = Ω(1)
        // THETA = Θ(n)
        // BIG O = O(n)

        T get(int index) {
                if(index == 0) {
                        // Get the first element
                        return this->first->data;
                } else {
                        // Get the index'th element
                        node<T>* curr = this->first;
                        for(int i = 0; i < index; ++i) {
                                curr = curr->next;
                        }
                        return curr->data;
                }
        }
        
        // OMEGA = Ω(1)
        // THETA = Θ(n)
        // BIG O = O(n)
        
        int IndexOf(T data){
                int index = -1;
                node<T>* curr = this->first;
                while(curr != NULL){
                        if(curr->data == data){
                                return index+1;
                        }
                        curr = curr->next;
                        index++;
                }
                return -1;
        }
        
        // OMEGA = Ω(1)
        // THETA = Θ(n)
        // BIG O = O(n)
        
        int LastOf(T data){
                int index = 0;
                int ans = -1;
                
                node<T>* curr = this->first;
                while(curr != NULL){
                        if(curr->data == data){
                                ans = index;
                        }
                        index++;
                        curr = curr->next;
                }
                return ans;
        }
        
        // OMEGA = Ω(1)
        // THETA = Θ(1)
        // BIG O = O(1)
        
        void Remove(){
                this->last = last->prev;
                last->next = NULL;
        }
        
        // OMEGA = Ω(1)
        // THETA = Θ(n)
        // BIG O = O(n)
        
        void RemoveAt(int pos){
                node<T>* curr = this->first;
                node<T>* prev = NULL;
                if(pos==0){
                        first = first->next;
                }
                else{
                        for(int i=1;i<pos;i++){
                                prev = curr;
                                curr = curr->next;
                        }
                        if(curr->next==NULL){
                                last = last->prev;
                                last->next = NULL;
                        }
                        else{
                                curr->next->prev = prev;
                                prev->next = curr->next;
                        }
                        
                }
        }
        
        // OMEGA = Ω(1)
        // THETA = Θ(n)
        // BIG O = O(n)
        
        void RemoveElement(T data){
                if(first->data == data){
                        first = first->next;
                }
                else{
                        node<T>* curr = this->first;
                        node<T>* prev = NULL;
                        while(curr != NULL){
                                prev = curr;
                                curr = curr->next;
                                if(curr->data == data){
                                        if(curr->next==NULL){
                                                last = last->prev;
                                                last->next = NULL;
                                        }
                                        else{
                                                curr->next->prev = prev;
                                                prev->next = curr->next;
                                        }
                                        
                                        break;
                                }
                        }
                }
                
        }
        
        // OMEGA = Ω(n)
        // THETA = Θ(n)
        // BIG O = O(n)
        
        int Size(){
                int cnt = 0;
                node<T>* curr = this->first;
                while(curr != NULL){
                        cnt++;
                        curr = curr->next;
                }
                return cnt;
        }
        
        // OMEGA = Ω(n)
        // THETA = Θ(n)
        // BIG O = O(n)
        
        node<T>* Slice(int start,int end){
                int l = end - start + 1;
                node<T>* curr = this->first;
                for(int i=1;i<start;i++){
                        curr = curr->next;
                }
                return curr;
        }

};


int main() {
        DoublyLinkedList<std::string> list;
        list.Add("Hello");
        list.Print();
        list.Add("Hi");
        list.Print();
        list.InsertAt("Bye",1);
        list.Print();
        list.Add("Akash");
        list.Print();
        if(list.isEmpty()){
                cout<<"List is Empty "<<endl;
        }
        else{
                cout<<"List is not empty"<<endl;
        }
        cout<<"Size = "<<list.Size()<<endl;
        cout<<"Element at position 1 is "<<list.get(1)<<endl;
        if(list.Contains("X")){
                cout<<"List contains X"<<endl;
        }
        else{
                cout<<"List does not contain X"<<endl;
        }
        cout<<"Position of the word Akash is "<<list.IndexOf("Akash")<<endl;
        cout<<"Last Position of the word Akash is "<<list.LastOf("Akash")<<endl;
        list.RemoveElement("Akash");
        cout<<"After removing Akash from the list "<<endl;
        list.Print();
        return 0;
}

SAMPLE OUTPUT

Hello 
Hello Hi 
Hello Bye Hi 
Hello Bye Hi Akash 
List is not empty
Size = 4
Element at position 1 is Bye
List does not contain X
Position of the word Akash is 3
Last Position of the word Akash is 3
After removing Akash from the list 
Hello Bye Hi

Related Solutions

In C++ In this lab we will creating two linked list classes: one that is a...
In C++ In this lab we will creating two linked list classes: one that is a singly linked list, and another that is a doubly linked list ( This will be good practice for your next homework assignment where you will build your own string class using arrays and linked list ) . These LinkedList classes should both be generic classes. and should contain the following methods: Print Add - Adds element to the end of the linked list. IsEmpty...
In Java In this lab we will creating two linked list classes: one that is a...
In Java In this lab we will creating two linked list classes: one that is a singly linked list, and another that is a doubly linked list ( This will be good practice for your next homework assignment where you will build your own string class using arrays and linked list ) . These LinkedList classes should both be generic classes. and should contain the following methods: Print Add - Adds element to the end of the linked list. IsEmpty...
C++ Linked Lists Practice your understanding of linked lists in C++ by creating a list of...
C++ Linked Lists Practice your understanding of linked lists in C++ by creating a list of songs/artist pairs. Allow your user to add song / artist pairs to the list, remove songs (and associated artist) from the list and be sure to also write a function to print the list! Have fun! Make sure you show your implementation of the use of vectors in this lab (You can use them too ) You MUST modularize your code ( meaning, there...
In C++ In this lab we will be creating a stack class and a queue class,...
In C++ In this lab we will be creating a stack class and a queue class, both with a hybrid method combining linked list and arrays in addition to the Stack methods(push, pop, peek, isEmpty, size, print) and Queue methods (enqueue, deque, peek, isEmpty, size, print). DO NOT USE ANY LIBRARY, implement each method from scratch. Both the Stack and Queue classes should be generic classes. Don't forget to comment your code.
C++ Only Please 10.15 LAB: Warm up: Contacts You will be building a linked list. Make...
C++ Only Please 10.15 LAB: Warm up: Contacts You will be building a linked list. Make sure to keep track of both the head and tail nodes. (1) Create three files to submit. ContactNode.h - Class declaration ContactNode.cpp - Class definition main.cpp - main() function (2) Build the ContactNode class per the following specifications: Parameterized constructor. Parameters are name followed by phone number. Public member functions InsertAfter() (2 pts) GetName() - Accessor (1 pt) GetPhoneNumber - Accessor (1 pt) GetNext()...
Please use C++ and linked list to solve this problem Linked list 1 -> 3 ->...
Please use C++ and linked list to solve this problem Linked list 1 -> 3 -> 4 -> 5-> 6 ->7 replaceNode( 5 , 6) // Replace 5 with 6     result 1 -> 3 -> 4 -> 6 -> 6 ->7 Base code #include <iostream> using namespace std; class Node { public:     int data;     Node *next;     Node(int da = 0, Node *p = NULL) {         this->data = da;         this->next = p;     } };...
Please use C++ and linked list to solve this problem Linked list 1 -> 2 ->...
Please use C++ and linked list to solve this problem Linked list 1 -> 2 -> 3 -> 4 -> 5-> 6 ->7 replaceNode( 5 , 6) // Replace 5 with 6     result 1 -> 2 -> 3 -> 4 -> 6 -> 6 ->7 Base code #include <iostream> using namespace std; class Node { public:     int data;     Node *next;     Node(int da = 0, Node *p = NULL) {         this->data = da;         this->next =...
In this lab, we will build a couple of classes, where one will be composed into...
In this lab, we will build a couple of classes, where one will be composed into the other. Work in pairs if you wish. Problem We saw Point.java in class last week. Do the following, one step at a time, making sure it works before you go on to the next step. Be sure to get help if you have any difficulties. You may use Point.java from last week or build a new one of your own. If you are...
C++ Data Structures: Implement a Stack and a Queue using Linked list In this lab you...
C++ Data Structures: Implement a Stack and a Queue using Linked list In this lab you will implement the functionality of a stack and a queue using a linked list. Your program must use of the declaration of the Stack and Queue class in Stack.h and Queue.h You have to implement the functionalities of queue (enq, deq, displayQueue) in a file called Queue.cpp. All the functions in Queue.cpp should follow the prototypes declared in Queue.h. Your code should make use...
*In C++ Please! This problem uses the concept of linked list What is a C++ structure?...
*In C++ Please! This problem uses the concept of linked list What is a C++ structure? Store product-id, product-name, and price per unit in a C++ structure. Use a C++ class with a member variable of that structure and provide read and write member functions for the product details. Suppose the product names are stored in alphabetical order, Write the C++ insert function to insert a new product ‘tooth brush’ in that linked list. Suppose the product names are stored...
ADVERTISEMENT
ADVERTISEMENT
ADVERTISEMENT