#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 was empty " << newNode->value;
cout << "is part of list's first node.\n";
head = newNode;
}
else {
while((nodePtr != NULL) && (nodePtr->value < num))
{
prevNodePtr = nodePtr;
nodePtr = nodePtr->next;
}
if(prevNodePtr==NULL)
newNode->next = head;
else
newNode->next = nodePtr; prevNodePtr->next = newNode;
}
return 0;
}
// The deleteNode function searches for a node with searchValue as
its value.
// The node, if found,is deleted from the list and from memory.
*
void LinkedList::deleteNode(float num)
{
struct ListNode *nodePtr = head, *prevNodePtr = NULL;
if(head==NULL) {
cout << "The list was empty\n";
return;
}
if(head->value == num) {
head = nodePtr->next;
delete [] nodePtr;
}
else {
while((nodePtr!= NULL)&&(nodePtr->value != num)) {
prevNodePtr = nodePtr;
nodePtr = nodePtr->next;
}
if(nodePtr==NULL)
cout << "The value " << num << " is not in this
list!\n";
else {
prevNodePtr->next = nodePtr->next;
delete [] nodePtr;
}
}
}
void LinkedList::destroyList()
{
struct ListNode *nodePtr = head, *nextNode = nodePtr;
if(head==NULL) {
cout << "The list is empty\n";
return;
}
while (nodePtr != NULL) {
nextNode = nodePtr->next;
delete [] nodePtr;
nodePtr = nextNode;
}
}
// displayList shows the value stored in each node
// of the linked list pointed to by head.
void LinkedList::displayList()
{
struct ListNode *nodePtr = head;
if (nodePtr == NULL)
cout << "The list is empty\n";
else {
while (nodePtr != NULL) {
cout << nodePtr->value << endl;
nodePtr = nodePtr->next;
}
}
}
int main()
{
int num;
char answer, choice;
LinkedList temp;
do {
cout << "Please enter a value to put in the list ->
";
cin >> num;
temp.insertNode(num);
cout << endl;
cout << "Would you like to put another value into your list?
";
cin >> answer;
} while(toupper(answer)=='Y');
cout << "I will now display your list\n";
cout << endl;
temp.displayList();
}
Purpose: Adapt a doubly linked list to behave like a stack and a queue.
1. Modify the singly linked list from lab1 into a doubly linked
list by adding a PREV node. Update the insert algorithm as shown in
section 2.7 and also update the delete algorithm
2. Implement the PREPEND and APPEND functions listed
3. Implement the standard interface for the doubly linked list as a queue.
4. Adapt your doubly linked list to behave like a STACK
5. Adapt your doubly linked list to behave like a QUEUE
Create a test case to validate your doubly linked list behaves like a queue and a stack. See the common Stack and Queue operations listed in the book for the Stack and Queue interface.
Homework Answers
// C++ program to implement LinkedList , Queue and Stack
#include <iostream>
using namespace std;
struct ListNode {
float value;
ListNode *next;
ListNode *prev;
};
class LinkedList {
ListNode *head; // make head private variable of linkedlist
public:
int insertNode(float num);
void deleteNode(float num);
void destroyList();
void displayList();
int prepend(float num);
int append(float num);
LinkedList(void) {head = NULL;}
~LinkedList(void) {destroyList();}
ListNode *getHead() {return head;} // return the head node of the list
};
int LinkedList::insertNode(float num)
{
struct ListNode *newNode, *nodePtr = head;
newNode = new ListNode;
if(newNode == NULL) {
cout << "Error allocating memory for new list member!\n";
return 1;
}
newNode->value = num;
newNode->next = NULL;
newNode->prev = NULL;
if(head==NULL) {
cout << "List was empty " << newNode->value;
cout << " is part of list's first node.\n";
head = newNode;
}else if(head->value > num)
{
newNode->next = head;
head->prev = newNode;
head = newNode;
}
else {
while((nodePtr->next != NULL) && (nodePtr->value < num)) {
nodePtr = nodePtr->next;
}
if(nodePtr->value < num)
{
newNode->prev = nodePtr;
nodePtr->next = newNode;
}else{
newNode->prev = nodePtr->prev;
nodePtr->prev->next = newNode;
newNode->next = nodePtr;
nodePtr->prev = newNode;
}
}
return 0;
}
// prepend function to add the node at the head of the linked list
int LinkedList:: prepend(float num)
{
ListNode *newNode = new ListNode;
if(newNode == NULL) {
cout << "Error allocating memory for new list member!\n";
return 1;
}
newNode->value = num;
newNode->next = NULL;
newNode->prev = NULL;
if(head == NULL)
{
head = newNode;
}
else
{
newNode->next = head;
head->prev = newNode;
head = newNode;
}
return 0;
}
int LinkedList:: append(float num)
{
ListNode *newNode = new ListNode;
if(newNode == NULL) {
cout << "Error allocating memory for new list member!\n";
return 1;
}
newNode->value = num;
newNode->next = NULL;
newNode->prev = NULL;
if(head == NULL)
head = newNode;
else
{
ListNode *curr = head;
while(curr->next != NULL)
curr = curr->next;
newNode->prev = curr;
curr->next = newNode;
}
return 0;
}
// The deleteNode function searches for a node with searchValue as its value.
// The node, if found,is deleted from the list and from memory. *
void LinkedList::deleteNode(float num)
{
struct ListNode *nodePtr = head;
if(head==NULL) {
cout << "The list was empty\n";
return;
}
if(head->value == num) {
head = head->next;
head->prev = NULL;
delete [] nodePtr;
}
else {
while((nodePtr != NULL)&&(nodePtr->value != num)) {
nodePtr = nodePtr->next;
}
if(nodePtr==NULL)
cout << "The value " << num << " is not in this list!\n";
else {
nodePtr->prev->next = nodePtr->next;
if(nodePtr->next != NULL)
nodePtr->next->prev = nodePtr->prev;
delete [] nodePtr;
}
}
}
void LinkedList::destroyList()
{
struct ListNode *nodePtr = head, *nextNode = nodePtr;
if(head==NULL) {
cout << "The list is empty\n";
return;
}
while (nodePtr != NULL) {
nextNode = nodePtr->next;
delete [] nodePtr;
nodePtr = nextNode;
}
}
// displayList shows the value stored in each node
// of the linked list pointed to by head.
void LinkedList::displayList()
{
struct ListNode *nodePtr = head;
if (nodePtr == NULL)
cout << "The list is empty\n";
else {
while (nodePtr != NULL) {
cout << nodePtr->value << endl;
nodePtr = nodePtr->next;
}
}
}
class Queue :public LinkedList
{
public:
int enqueue(float num);
void dequeue();
};
int Queue::enqueue(float num)
{
return(LinkedList::append(num));
}
void Queue::dequeue()
{
LinkedList::deleteNode(getHead()->value);
}
class Stack : public LinkedList
{
public:
int push(float num);
void pop();
};
int Stack::push(float num)
{
return(LinkedList::prepend(num));
}
void Stack::pop()
{
LinkedList::deleteNode(getHead()->value);
}
int main() {
//int num;
//char answer, choice;
LinkedList temp;
temp.insertNode(35);
temp.insertNode(12);
temp.insertNode(24);
temp.insertNode(32);
cout <<"Initial Linked List : "<< endl;
temp.displayList();
temp.deleteNode(24);
temp.deleteNode(25);
cout <<"Linked List after deletion: "<< endl;
temp.displayList();
// test stack
Stack stack;
for(float i=1;i<5;i++)
stack.push(i);
cout<<"Initial Stack : "<<endl;
stack.displayList();
stack.pop();
stack.pop();
cout<<"After popping 2 elements Stack : "<<endl;
stack.displayList();
// test queue
Queue queue;
for(float i=1;i<5;i++)
queue.enqueue(i);
cout<<"Initial Queue : "<<endl;
queue.displayList();
queue.dequeue();
queue.dequeue();
cout<<"After deleting 2 elements Queue : "<<endl;
queue.displayList();
return 0;
}
//end of program
Output:
Add Answer to:
#include <iostream> using namespace std; struct ListNode { float value; ListNode *next; }; ...
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;...
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...
Please rewrite this function using recursive function #include using namespace std; struct Node { char ch;...
Please rewrite this function using recursive function #include using namespace std; struct Node { char ch; Node* next; }; class LinkedList { Node* head; public: LinkedList(); ~LinkedList(); void add(char ch); bool find(char ch); bool del(char ch); friend std::ostream& operator<<(std::ostream& out, LinkedList& list); }; LinkedList::LinkedList() { head = NULL; } LinkedList::~LinkedList() { Node* cur = head, * tmp; while (cur != NULL) { tmp = cur->next; delete cur; cur = tmp; } } void LinkedList::add(char ch) { Node* cur = head,...
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++ 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) {...
Your task is to complete the following function/functions: 1. Given a position in the linked list,...
Your task is to complete the following function/functions: 1. Given a position in the linked list, delete the node at that position.(Silver problem - Mandatory ) 2. Print the sum of all negative elements in the linked list.(Gold problem) If you want, you can refer to the the previous recitation manual (which was on Linked Lists) to implement node deletion. #include <iostream> using namespace std; //----------- Define Node --------------------------------------------------- struct Node{ int key; Node *next; }; //----------- Define Linked List...
C++ Assignment Project 1 - NodeList Building upon the the ListNode/List code I would like you...
C++ Assignment Project 1 - NodeList Building upon the the ListNode/List code I would like you to extend the interface of a list to have these member functions as well. struct ListNode { int element; ListNode *next; } Write a function to concatenate two linked lists. Given lists l1 = (2, 3, 1)and l2 = (4, 5), after return from l1.concatenate(l2)the list l1should be changed to be l1 = (2, 3, 1, 4, 5). Your function should not change l2and...
C++ Assignment Project 1 - NodeList Building upon the the ListNode/List code I would like you to extend the interface of...
C++ Assignment Project 1 - NodeList Building upon the the ListNode/List code I would like you to extend the interface of a list to have these member functions as well. struct ListNode { int element; ListNode *next; } Write a function to concatenate two linked lists. Given lists l1 = (2, 3, 1)and l2 = (4, 5), after return from l1.concatenate(l2)the list l1should be changed to be l1 = (2, 3, 1, 4, 5). Your function should not change l2and...
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;...
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...
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;...
Most questions answered within 3 hours.
-
The financial statements of Apple Inc. show the following
numbers for fiscal year 2017 ($000,000):
Revenue...
asked 1 minute ago -
Suppose that you are given the following results. Find the
correlation coefficient of the data.
sx...
asked 10 minutes ago -
The width of a tool used for semiconductor manufacturing
is assumed to be normally distributed with...
asked 12 minutes ago -
A
runaway train car that has a mass of 1,400 kg travels at a speed of...
asked 16 minutes ago -
The expected abnormal earnings of a firm that has earnings of
$40,000 with a required equity...
asked 14 minutes ago -
A spherical surface completely surrounds a collection of
charges. Find the electric flux through the surface...
asked 30 minutes ago -
Two capacitors with capacitances of 12 and 18.1 µF,
respectively, are connected in parallel. The system...
asked 16 minutes ago -
Let's say you are a small business owner that provides
business-to-business software-as-a-service to non-profit
organizations. Your...
asked 21 minutes ago -
A circuit is constructed with five resistors and a battery as
shown. The battery voltage is...
asked 29 minutes ago -
A. What is the U.S.
economic system and what do you think are the advantages and...
asked 29 minutes ago -
A student measures the following data in a calorimetry
experiment designed to determine the specific heat...
asked 44 minutes ago -
1) 2H2O(g) → 2H2 (g) + O2 (g) DH = 483.6 kJ
If 5 moles of...
asked 49 minutes ago