Question

In: Computer Science

C++ question: Design and implement your own linked list class to hold a sorted list of...

C++ question:

Design and implement your own linked list class to hold a sorted list of integers in ascending order. The class should have member functions for inserting an item in the list, deleting an item from the list, and searching the list for an item. Note: the search function should return the position of the item in the list (first item at position 0) and -1 if not found.

In addition, it should have member functions to display the list, check if the list is empty, and return the length of the list. Be sure to have a class constructor, a class destructor, and a copy constructor for deep copy. Demonstrate your class with a driver program (be sure to include the following cases: insertion at the beginning, end, and inside the list, deletion of first item, last item, and an item inside, searching for an existing/non-existing item, and modifying a list that was initialized to an existing list).

Solutions

Expert Solution

Screenshot

------------------------------------------------------------------------------------------

Program

LinkedList.h

#include<iostream>
#include<string>
#include<cstdlib>
// Create a class linked list
class LinkedList {
   //Instance variable part
private:
   typedef struct node {
       int data;
       node* next;
   }*nodePtr;
   nodePtr head;
   nodePtr curr;
   nodePtr temp;
   //Member functions
public:
   //Constructor
   LinkedList();
   //Destructor
   ~LinkedList()=default;
   //Copy constructor
   LinkedList(const LinkedList& copy);
   //Add a value
   void addNode(int addData);
   //Print list
   void printList();
   //Delete a value using position
   void deleteNode(int position);
   //Search a value
   int searchNode(int data);
};

LinkedList.cpp

#include "LinkedList.h"
using namespace std;
//Constructor
LinkedList::LinkedList() {
   head = NULL;
   temp = NULL;
   curr = NULL;
}
//Copy constructor
LinkedList::LinkedList(const LinkedList& copy) {
   curr = copy.head;
   while (curr != NULL)
   {
       addNode(curr->data);
       curr = curr->next;
   }
}
//Insert an item in linked list
void LinkedList::addNode(int addData) {
   //Create a node
   nodePtr n = new node;
   n->data = addData;
   n->next = NULL;
   //Check any element present or not
   if (head != NULL) {
       //head value check
       if (head->data > n->data) {
           n->next = head;
           head = n;
           return;
       }
       curr = head;
       temp = head;
       while (curr->next!= NULL && curr->data<n->data) {
           temp = curr;
           curr = curr->next;
       }
      
       if (curr->next!= NULL) {
           temp->next = n;
           n->next = curr;
       }
       else if (curr->data > n->data) {
           temp->next = n;
           n->next = curr;
       }
       else {
           curr->next = n;
       }
   }
   //First data
   else {
       head = n;
   }
}

//Print the linked list
void LinkedList::printList() {
   curr = head;
   while (curr != NULL) {
       cout << curr->data << " ";
       curr = curr->next;
   }
   cout << endl;
}

//Delete value at the specified index
void LinkedList::deleteNode(int position) {
   int counter = 0;
   nodePtr delPtr = NULL;
   temp = head;
   curr = head;
   while (curr != NULL && counter != position) {
       temp = curr;
       curr = curr->next;
       counter++;
   }
   if (curr == NULL) {
       cout << "Data not found!!!" << endl;
       delete delPtr;
   }
   else {
       delPtr = curr;
       curr = curr->next;
       temp->next = curr;
       if (delPtr == head) {
           head = head->next;
           temp = NULL;
       }
       delete delPtr;
   }
}
//Search an item
int LinkedList::searchNode(int data) {
   int i = 0;
   curr = head;
   while (curr != NULL) {
       if (curr->data == data) {
           return i;
       }
       curr = curr->next;
       i++;
   }
   return -1;
}

Driver.cpp

#include "LinkedList.h"
using namespace std;
int main()
{
   //Create object of linke list class
   LinkedList ll;
   //Add values
   //Check first last and middle
   ll.addNode(3);
   ll.addNode(5);
   ll.addNode(4);
   ll.addNode(7);
   ll.addNode(2);
   //Print list
   ll.printList();
   //Delete first
   ll.deleteNode(0);
   ll.printList();
   //Delete last
   ll.deleteNode(3);
   ll.printList();
   //Delete middle
   ll.deleteNode(1);
   ll.printList();
   //Search
   cout << "Search 3 in list and found in index of "<<ll.searchNode(3) << endl;
   cout << "Search 7 in list and found in index of " << ll.searchNode(7) << endl;
   //Copy constructor check
   LinkedList copy;
   copy.addNode(3);
   copy.addNode(5);
   copy.addNode(4);
   copy.addNode(7);
   copy.addNode(2);
   ll = copy;
   ll.printList();
}

----------------------------------------------------------------------

Output

2 3 4 5 7
3 4 5 7
3 4 5
3 5
Search 3 in list and found in index of 0
Search 7 in list and found in index of -1
2 3 4 5 7


Related Solutions

Make in c++ this Programming Challenge 1. Design your own linked list class to hold a...
Make in c++ this Programming Challenge 1. Design your own linked list class to hold a series of integers. The class should have member functions for appending, inserting, and deleting nodes. Don’t forget to add a destructor that destroys the list. Demonstrate the class with a driver program. 2. List Print Modify the linked list class you created in Programming Challenge 1 to add a print member function. The function should display all the values in the linked list. Test...
Could you check/edit my code? Design and implement your own linked list class to hold a...
Could you check/edit my code? Design and implement your own linked list class to hold a sorted list of integers in ascending order. The class should have member function for inserting an item in the list, deleting an item from the list, and searching the list for an item. Note: the search function should return the position of the item in the list (first item at position 0) and -1 if not found. In addition, it should member functions to...
Develop a C++ "doubly" linked list class of your own that can hold a series of...
Develop a C++ "doubly" linked list class of your own that can hold a series of signed shorts Develop the following functionality: Develop a linked list node struct/class You can use it as a subclass like in the book (Class contained inside a class) You can use it as its own separate class Your choice Maintain a private pointer to a node class pointer (head) Constructor Initialize head pointer to null Destructor Make sure to properly delete every node in...
C++ What Should This Program Do? Linked List Class Design your own linked list class (List.h)...
C++ What Should This Program Do? Linked List Class Design your own linked list class (List.h) to hold a series of strings. The linked list node should be implemented as a struct. The class should have member functions for appending, inserting, and deleting nodes. You should also have a display function that will traverse the list & display each node’s value. Don’t forget to add a destructor that destroys the list. DRIVER – driver.cpp Write a driver program (driver.cpp) that...
C++ Question Design and implement a class that stores a list of students. Each student has...
C++ Question Design and implement a class that stores a list of students. Each student has the list of courses he/she registered for the semester. You will need a container of containers to hold this list of students. Choose the optimal container for this exercise, noting that no duplicates should be permitted. Use STL classes with iterators to navigate the list. Develop a test program, which allows options to add, remove, and list students and their associated course lists. Also...
C++ coding functions Implement the following class using linked lists. Creating a simple linked list class...
C++ coding functions Implement the following class using linked lists. Creating a simple linked list class to use is probably your first step.(Please do not use collections like .push() . pop(), etc.) and instead create the implementation A templated stack class that stores type T with the following public functions: - void Push(T t) - adds t to the top of the stack - T Pop() - asserts that the stack is not empty then removes and returns the item...
write a java code to implement a linked list, called CupList, to hold a list of...
write a java code to implement a linked list, called CupList, to hold a list of Cups. 1.Define and write a Cup node class, called CupNode, to hold the following information about a cup: •number (cup number) •capacity (cup capacity in ml) •Write a method size() that returns the number of elements in the linkedlist CupList. •Write a method getNodeAt() that returns the reference to cup node object at a specific position given as a parameter of the method. •Write...
. Implement your own custom linked list array implementation with the following changes: (a) Fill in...
. Implement your own custom linked list array implementation with the following changes: (a) Fill in the public E get(int index) method (b) Also add code to the get method to print out a message for each time an element in the list is checked while searching for the element You may want to study how the toString method goes from element to element in the list Java
In C++, Implement the queue ADT with a singly linked list
In C++, Implement the queue ADT with a singly linked list
Given two sorted linked lists, merge them into a third sorted linked list. If an element...
Given two sorted linked lists, merge them into a third sorted linked list. If an element is present in both the lists, it should occur only once in the third list. Code needed in java.
ADVERTISEMENT
ADVERTISEMENT
ADVERTISEMENT