ZuoTi.Pro
Question

Design and implement your own linked list class to hold a sorted list of integers in ascending order. The class should h...

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 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).

#ifndef LIST_H
#define LINKEDLIST_H

template <class T>
class ListNode
{
public:
   //Node value
   T value;
   //Pointer to the next node
   ListNode<T> *next;
   //Constructor
   ListNode(T nodeValue)
   {
       value = nodeValue
           next = nullptr;
   }
};
//LinkedList class
template <class T>
class LinkedList
{
private:
   //List head pointer
   ListNode<T> *head;
public:
   //Constructor
   LinkedList()
   {
       head = nullptr;
   }
   //Destructor
   ~LinkedList();

   //Linked list operations
   void appendNode(T);
   void insertNode(T);
   void deleteNode(T);
   void displayList() const;
};
template <class T>
void LinkedList<T>::appendNode(T newValue)
{
   //To point to a new node
   ListNode<T> *newNode;
   //To move through the list
   ListNode<T> *nodePtr;
   //Allocate a new node and store new Value there.
   newNode = new ListNode<T>(newValue);
   if (!head)
       head = newNode;
   else
   {
       //Initialize nodePtr to head of list.
       nodePtr = head;
       //Find the last node in the list
       while (nodePtr->next)
           nodePtr = nodePtr->next;
       //Insert newNode as the last node.
       nodePtr->next = newNode;
   }
}
template <class T>
void LinkedList<T>::displayList() const
{
   //To move through the list
   ListNode<T> *nodePtr;
   //Position nodePtr at the head of the list.
   nodePtr = head;
   //Traverse the list
   while (nodePtr)
   {
       //Value of this node
       cout << nodePtr->value << endl;
       //Move to the next node.
       nodePtr = nodePtr->next;
   }
}
template <class T>
void LinkedList<T>::insertNode(T newValue)
{
   ListNode<T> *newNode;
   //traverse the list
   ListNode<T> *nodePtr;

   ListNode<T> *previousNode = nullptr;
   newNode = new ListNode<T>(newValue);

   if (!head)
   {
       head = newNode;
       newNode->next = nullptr;
   }
   else
   {
       nodePtr = head;
       previousNode = nullptr;

       //Skip all nodes whose value is less than newValue.
       while (nodePtr != nullptr && nodePtr && nodePtr->value < newValue)
       {
           previousNode = nodePtr;
           nodePtr = nodePtr->next;
       }
       //If the new node is to be the 1st in the list, then insert it before all other nodes
       if (previousNode == nullptr)
       {
           head = newNode;
           newNode->next = nodePtr;
       }
       else {
           previousNode->next = newNode;
           newNode->next = nodePtr;
       }
   }
}
template <class T>
void LinkedList<T>::deleteNode(T searchValue)
{
   //To traverse the list
   ListNode<T> *nodePtr;
   //To point to the previous node
   ListNode<T> *previousNode;
   //There is no need to do anything if the list is empty
   if (!head)
       return;

   //Determine if the first node is one
   if (head->value == searchValue)
   {
       nodePtr = head->next;
       delete head;
       head = nodePtr;
   }
   else
   {
       //Initialize nodePtr to head of list
       nodePtr = head;

       //Skip all nodes whose value member is not equal to num
       while (nodePtr != nullptr && nodePtr->value != searchValue)
       {
           previousNode = nodePtr;
           nodePtr = nodePtr->next;
       }
       //If nodePtr is not at the end of the list, link the
       //previous node ot the node after nodePtr, then delete nodePtr.
       if (nodePtr)
       {
           previousNode->next = nodePtr->next;
           delete nodePtr;
       }
   }
}
//Destructor
//This function will delete every node on the list

template <class T>
LinkedList<T>::~LinkedList()
ListNode<T> *nodePtr;
ListNode<T> *nextNode;

//Position nodePtr at the head of the list.
nodePtr = head;
//While nodePtr is not at the end of teh list...
while (nodePtr != nullptr)
{
   //Save a pointer to the next node.
   nextNode = nodePtr->next;

   delete nodePtr;

   nodePtr = nextNode;
}
}
#endif

engineering   Computer-Science   
0 0
Add a comment Improve this question Transcribed image text
Next > < Previous
Sort answers by oldest

Homework Answers

Answer #1

.Thire ere no bugs in your Code bat they asked fo write Aeethad hichCould add/delete elenient in the beginning and in the end

#ifndef LIST_H
#define LINKEDLIST_H

template <class T>
class ListNode
{
public:
//Node value
T value;
//Pointer to the next node
ListNode<T> *next;
//Constructor
ListNode(T nodeValue)
{
value = nodeValue
next = nullptr;
}
};
//LinkedList class
template <class T>
class LinkedList
{
private:
//List head pointer
ListNode<T> *head;
public:
//Constructor
LinkedList()
{
head = nullptr;
}
//Destructor
~LinkedList();

//Linked list operations
void appendNode(T);
void insertAtBeginning(T);
void insertNode(T);
void deleteNode(T);
void deleteAtBeginning();
void deleteAtEnd();
int findNode(T);
void displayList() const;
};
template <class T>
void LinkedList<T>::appendNode(T newValue)
{
//To point to a new node
ListNode<T> *newNode;
//To move through the list
ListNode<T> *nodePtr;
//Allocate a new node and store new Value there.
newNode = new ListNode<T>(newValue);
if (!head)
head = newNode;
else
{
//Initialize nodePtr to head of list.
nodePtr = head;
//Find the last node in the list
while (nodePtr->next)
nodePtr = nodePtr->next;
//Insert newNode as the last node.
nodePtr->next = newNode;
}
}

template <class T>
void LinkedList<T>::insertAtBeginning(T newValue)
{
//To point to a new node
ListNode<T> *newNode;
//Allocate a new node and store new Value there.
newNode = new ListNode<T>(newValue);
if (!head)
head = newNode;
else
{
//Add at the beginning
newNode->next = head;
head = newNode;
}
}

template <class T>
void LinkedList<T>::displayList() const
{
//To move through the list
ListNode<T> *nodePtr;
//Position nodePtr at the head of the list.
nodePtr = head;
//Traverse the list
while (nodePtr)
{
//Value of this node
cout << nodePtr->value << endl;
//Move to the next node.
nodePtr = nodePtr->next;
}
}
template <class T>
void LinkedList<T>::insertNode(T newValue)
{
ListNode<T> *newNode;
//traverse the list
ListNode<T> *nodePtr;

ListNode<T> *previousNode = nullptr;
newNode = new ListNode<T>(newValue);

if (!head)
{
head = newNode;
newNode->next = nullptr;
}
else
{
nodePtr = head;
previousNode = nullptr;

//Skip all nodes whose value is less than newValue.
while (nodePtr != nullptr && nodePtr && nodePtr->value < newValue)
{
previousNode = nodePtr;
nodePtr = nodePtr->next;
}
//If the new node is to be the 1st in the list, then insert it before all other nodes
if (previousNode == nullptr)
{
head = newNode;
newNode->next = nodePtr;
}
else {
previousNode->next = newNode;
newNode->next = nodePtr;
}
}
}
template <class T>
void LinkedList<T>::deleteNode(T searchValue)
{
//To traverse the list
ListNode<T> *nodePtr;
//To point to the previous node
ListNode<T> *previousNode;
//There is no need to do anything if the list is empty
if (!head)
return;

//Determine if the first node is one
if (head->value == searchValue)
{
nodePtr = head->next;
delete head;
head = nodePtr;
}
else
{
//Initialize nodePtr to head of list
nodePtr = head;

//Skip all nodes whose value member is not equal to num
while (nodePtr != nullptr && nodePtr->value != searchValue)
{
previousNode = nodePtr;
nodePtr = nodePtr->next;
}
//If nodePtr is not at the end of the list, link the
//previous node ot the node after nodePtr, then delete nodePtr.
if (nodePtr)
{
previousNode->next = nodePtr->next;
delete nodePtr;
}
}
}

template <class T>
int LinkedList<T>::findNode(T searchValue)
{
int ans = 0;
//To move through the list
ListNode<T> *nodePtr;
//Position nodePtr at the head of the list.
nodePtr = head;
//Traverse the list
while (nodePtr != nullptr && nodePtr -> value != searchValue) {
nodePtr = nodePtr->next;
ans++;
}
//If we didn't find the value;
if (nodePtr == nullptr) {
return -1;
}
return ans;
}

template <class T>
void LinkedList<T>::deleteAtBeginning()
{
if (!head)
return;
//To point to a new node
ListNode<T> *newNode;
newNode = head->next;
delete head;
head = newNode;
}

template <class T>
void LinkedList<T>::deleteAtEnd()
{
if (!head)
return;
//To point to a new node
ListNode<T> *newNode;
//To move through the list
ListNode<T> *nodePtr;
while (nodePtr -> next != nullptr) {
nodePtr = nodePtr -> next;
}
delete nodePtr -> next;
}

//Destructor
//This function will delete every node on the list

template <class T>
LinkedList<T>::~LinkedList() {
ListNode<T> *nodePtr;
ListNode<T> *nextNode;

//Position nodePtr at the head of the list.
nodePtr = head;
//While nodePtr is not at the end of teh list...
while (nodePtr != nullptr)
{
//Save a pointer to the next node.
nextNode = nodePtr->next;

delete nodePtr;

nodePtr = nextNode;
}
}
#endif


0 0
Add a comment
Know the answer?
Add Answer to:
Design and implement your own linked list class to hold a sorted list of integers in ascending order. The class should h...
Your Answer:

Post as a guest

Your Name:

What's your source?

Earn Coins

Coins can be redeemed for fabulous gifts.

Log In

Sign Up

Not the answer you're looking for? Ask your own homework help question. Our experts will answer your question WITHIN MINUTES for Free.
Similar Homework Help Questions

  • In C++, for the provided template linked list class create a derived class of it which...

    In C++, for the provided template linked list class create a derived class of it which adds the functionality to it to find the high and low value of any given data stored in the list. The derived class must be a template. LinkedList.h #pragma once #include <iostream> using namespace std; template <class T> class ListNode {    public:        T data;        ListNode<T>* next;        ListNode(T data)        {            this->data = data;...

  • linked list operation /*************************************************************************************** This function creates a new node with the information give as a...

    linked list operation /*************************************************************************************** This function creates a new node with the information give as a parameter and looks for the right place to insert it in order to keep the list organized ****************************************************************************************/ void insertNode(string first_name, string last_name, string phoneNumber) { ContactNode *newNode; ContactNode *nodePtr; ContactNode *previousNode = nullptr; newNode = new ContactNode; /***** assign new contact info to the new node here *****/ if (!head) // head points to nullptr meaning list is empty { head = newNode;...

  • #include <iostream> using namespace std; struct ListNode { float value; ListNode *next; }; ...

    #include <iostream> using namespace std; struct ListNode { float value; ListNode *next; }; ListNode *head; class LinkedList { public: int insertNode(float num); void deleteNode(float num); void destroyList(); void displayList(); LinkedList(void) {head = NULL;} ~LinkedList(void) {destroyList();} }; int LinkedList::insertNode(float num) { struct ListNode *newNode, *nodePtr = head, *prevNodePtr = NULL; newNode = new ListNode; if(newNode == NULL) { cout << "Error allocating memory for new list member!\n"; return 1; } newNode->value = num; newNode->next = NULL; if(head==NULL) { cout << "List...

  • What is the Big O notation of our destructor function SLinkedList<T>: :-SLinkedlist) SListNode<T> *nodePtr; // To...

    What is the Big O notation of our destructor function SLinkedList<T>: :-SLinkedlist) SListNode<T> *nodePtr; // To traverse the list SListNode<T> nextNode; II To point to the next node Position nodePtr at the head of the list. nodePtr-head; /I while nodePtr is not at the end of the list... while (nodePtr !- nullptr) // Save a pointer to the next node. nextNode nodePtr->getNextNodeO; Delete the current node. delete nodePtr; f Position nodePtr at the next node nodePtr nextNode; 0 0(1) O...

  • can someone please double check my code here are the requirements please help me fulfill the...

    can someone please double check my code here are the requirements please help me fulfill the requirements Using the material in the textbook (NumberList) as a sample, design your own dynamic linked list class (using pointers) to hold a series of capital letters. The class should have the following member functions: append, insert (at a specific position, return -1 if that position doesn't exist), delete (at a specific position, return -1 if that position doesn't exist), print, reverse (which rearranges...

  • C++ Create a class that implements a sorted, doubly-linked list: Start with a copy of the...

    C++ Create a class that implements a sorted, doubly-linked list: Start with a copy of the sortedList class. Call your new class doublyLinkedList. Convert the baseline code into a doubly linkedlist, and thoroughly test all existing operations (make sure to check all edge conditions), and then implement the new operations below. The class should have the following additional class methods: • A reverse method: this method will reverse the order of the doubly linked list. This method takes no parameters,...

  • Double linked list implementation of PutItem function. How to fix my code to get desired output b...

    Double linked list implementation of PutItem function. How to fix my code to get desired output below: Output: 2 5 8 #ifndef ITEMTYPE_H #define ITEMTYPE_H enum RelationType { LESS, GREATER, EQUAL}; class ItemType { public:     ItemType();     void setValue(int newValue);     int getValue() const;     RelationType ComparedTo(ItemType newItem); private:     int value; }; #endif // ITEMTYPE_H // ItemType.cpp #include "ItemType.h" ItemType::ItemType() {     value = 0; } void ItemType::setValue(int newValue) {     value = newValue; } int ItemType::getValue() const {     return value; } RelationType ItemType::ComparedTo(ItemType newItem)...

  • C++ program: Convert the classes to template classes #include <iostream> #include <string> using namespace std; class Node { private: int data; Node* next; public: Node(int...

    C++ program: Convert the classes to template classes #include <iostream> #include <string> using namespace std; class Node { private: int data; Node* next; public: Node(int data) { this->data=data; this->next = 0; } int getData(){return data;} Node* getNext(){return next;} void setNext(Node* next){this->next=next;} }; class LinkedList { private: Node* head = 0; public: int isEmpty() {return head == 0;} void print() { Node* currNode = head; while(currNode!=0) { cout << currNode->getData() << endl; currNode = currNode->getNext(); } } void append(int data) {...

  • c++ modify the attached unsorted linked list class into a sorted linked list class #include <iostream>...

    c++ modify the attached unsorted linked list class into a sorted linked list class #include <iostream> using namespace std; template<class T> struct Node {     T data;//data field     Node * next;//link field     Node(T data) {       this->data = data;     } }; template<class T> class linked_list{ private:       Node<T> *head,*current; public:       linked_list(){//constructor, empty linked list         head = NULL;         current = NULL;       }       ~linked_list(){         current = head;         while(current != NULL) {          ...

  • LAB: Inserting an integer in descending order (doubly-linked list) Given main() and an IntNode class, complete...

    LAB: Inserting an integer in descending order (doubly-linked list) Given main() and an IntNode class, complete the IntList class (a linked list of IntNodes) by writing the insertInDescendingOrder() method to insert new IntNodes into the IntList in descending order. Ex. If the input is: 3 4 2 5 1 6 7 9 8 -1 the output is: 9 8 7 6 5 4 3 2 1 ___________________________________________________________________________________________________________________________________________________ SortedList.java (READ ONLY!!!) import java.util.Scanner; public class SortedList { public static void main...

ADVERTISEMENT
Free Homework Help App
Download From Google Play
Scan Your Homework
to Get Instant Free Answers
Need Online Homework Help?
Ask a Question
Get Answers For Free
Most questions answered within 3 hours.
ADVERTISEMENT
ADVERTISEMENT
ADVERTISEMENT