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...
In C++, Implement the queue ADT with a singly linked list
In C++, Implement the queue ADT with a singly linked list
(Write a C# program DO NOT USE CLASS)Implement the merge sort algorithm using a linked list...
(Write a C# program DO NOT USE CLASS)Implement the merge sort algorithm using a linked list instead of arrays. You can use any kind of a linked structure, such as single, double, circular lists, stacks and/or queues. You can populate your list from an explicitly defined array in your program. HINT: You will not be using low, middle and high anymore. For finding the middle point, traverse through the linked list while keeping count of the number of nodes. Break...
you are asked to implement a C++ class to model a sorted array of unsigned integers....
you are asked to implement a C++ class to model a sorted array of unsigned integers. The class is to be used in an embedded application that cannot assume the presence of the STL. The array has to be dynamically allocated in such a way that allows programmers using it to specify the required size. Class will provide (1) provide the appropriate constructors and destructor; (2) provide methods for updating, and showing numbers in/to the array (e.g., to be used...
C++ Using an appropriate definition of ListNode, design a simple linked list class with only two...
C++ Using an appropriate definition of ListNode, design a simple linked list class with only two member functions and a default constructor: void add(double x); boolean isMember(double x); LinkedList( ); The add function adds a new node containing x to the front (head) of the list, while the isMember function tests to see if the list contains a node with the value x. Test your linked list class by adding various numbers to the list and then testing for membership....
Purpose Purpose is to implement some single linked list methods. Add methods to the List class...
Purpose Purpose is to implement some single linked list methods. Add methods to the List class In the ‘Implementation of linked lists’ lecture, review the ‘Dynamic implementation of single linked list’ section. You will be adding new methods to the List class. Eight new methods are required: new constructor – creates a new single linked list from an array of integers e.g. int a[] = {1, 2, 3, 4}; List list = new List(a); toString() – returns a string representing...
Implement the ADT character string as the class LinkedString by using a linked list of characters....
Implement the ADT character string as the class LinkedString by using a linked list of characters. Include the following LinkedString constructors and methods: LinkedString(char[] value) Allocates a new character linked list so that it represents the sequence of characters currently contained in the character array argument. LinkedString(String original) Initializes a new character linked list so that it represents the same sequence of characters as the argument. char charAt(int index) Returns the char value at the specified index. The first character...
In this Java program you will implement your own doubly linked lists. Implement the following operations...
In this Java program you will implement your own doubly linked lists. Implement the following operations that Java7 LinkedLists have. 1. public DList() This creates the empty list 2. public void addFirst(String element) adds the element to the front of the list 3. public void addLast(String element) adds the element to the end of the list 4. public String getFirst() 5. public String getLast() 6. public String removeLast() removes & returns the last element of the list. 7. public String...
ADVERTISEMENT
ADVERTISEMENT
ADVERTISEMENT