THIS IS A C++ PROGRAMMING ASSIGNMENT. MUST TAKE USER INPUT AND UTILIZE STRUCTURE

Question

THIS IS A C++ PROGRAMMING ASSIGNMENT. MUST TAKE USER INPUT AND UTILIZE STRUCTURES IN THE PROGRAM. THANKS SO MUCH!

Create a linked list

Print the list

Copy the list

Reverse the list

Search the list (linear search)

Insert into the list

Remove from the list

Include a driver (the main() function) that displays all of the functionality.

1. Your Own Linked List 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 the class by starting with an empty list, adding some elements, and then printing the resulting list out. st Copy Constructor Modify your linked list class of Programming Challenges 1 and 2 to add a copy con structor. Test your class by making a list, making a copy of the list, and then displaying the values in the copy Programming Challenges 1061 4. List Reverse Modify the linked list class you created in the previous programming challenges by adding a member function named reverse that rearranges the nodes in the list so that their order is reversed. Demonstrate the function in a simple driver program 5. List Search Modify the linked list class you created in the previous programming challenges to include a member function named search that returns the position of a specific value in the linked list. The first node in the list is at position 0, the second node is at position 1, and so on. If x is not found on the list, the search should return -1. Test the new member function using an appropriate driver program. 6. Member Insertion by Position Modify the list class you created in the previous programming challenges by adding a member function for inserting a new item at a specified position. A position of 0 means that the value will become the first item on the list, a position of 1 means that the value will become the second item on the list, and so on. A position equal to or greater than the length of the list means that the value is placed at the end of the list 7. Member Removal by Position Modify the list class you created in the previous programming challenges by adding a member function for deleting a node at a specified position. A value of 0 for the posi tion means that the first node in the list (the current head) is deleted. The function does nothing if the specified position is greater than or equal to the length of the list

Explanation / Answer

HI, Please find my implementation of Linked List.

Please let me know in case of any issue.

############### nodeList.h ############

#include <iostream>
#include <string>

using namespace std;

template <typename T>
class List
{
struct Node
{
T data;
Node *next;
Node(T d, Node *n = 0):data(d), next(n) {}
};
Node *head;
  
public:
List(Node *h = 0):head(h){}
~List();
void insert(Node *loc, T d);
void push_back(T d);
void push_front(T d);
T pop_back();
T pop_front();
void erase(Node *loc);
void display();
Node *search(T d);
Node *getFirst();
Node *getLast();
void reverse();
};

// destructor
template <typename T>
List<T>::~List()
{
Node *tmp;
while(head) {
tmp = head;
head = head->next;
delete tmp;
}
}

// insert d before loc
template <typename T>
void List<T>::insert(Node *loc, T d)
{
Node *new_node = new Node(d,0);
if(!head) {
head = new_node;
return;
}
if(loc == head) {
push_front(d);
return;
}
Node *cur = head;
while(cur->next) {
if(cur->next == loc) {
new_node->next = cur->next;
cur->next = new_node;
return ;
}
cur = cur->next;
}
}

template <typename T>
void List<T>::push_back(T d)
{
Node *new_node = new Node(d,0);
if(!head) {
head = new_node;
return;
}
Node *cur = head;
while(cur) {
if(!cur->next) {
cur->next = new_node;
return;
}
cur = cur->next;
}
}

template <typename T>
void List<T>::push_front(T d)
{
Node *new_node = new Node(d,0);
if(!head) {
head = new_node;
return;
}
new_node->next = head;
head = new_node;
return;
}

template <typename T>
T List<T>::pop_back()
{
Node *cur = head;
while(cur) {
if(!cur->next) {
T data (cur->data);
delete cur;
head = NULL;
return data;
}
else {
if(!cur->next->next) {
T data (cur->next->data);
cur->next = NULL;
delete cur->next;
return data;
}
}
cur = cur->next;
}
return NULL;
}

template <typename T>
T List<T>::pop_front()
{
if(!head) return NULL;
Node *tmp = head;
T data (head->data);
if(head->next) {
head = head->next;
delete tmp;
return data;
}
delete tmp;
head = NULL;
return data;
}

template <typename T>
void List<T>::erase(Node *loc)
{
if(loc == head) {
Node *tmp = head;
head = head->next;
delete tmp;
return;
}
Node *cur = head;
while(cur) {
if(cur->next == loc) {
cur->next = loc->next;
delete loc;
}
cur = cur->next;
}
}

template <typename T>
typename List<T>::Node* List<T>::search(T d)
{
if(!head) return NULL;
Node* cur = head;
while(cur) {
if(cur->data == d) return cur;
cur = cur->next;
}
return NULL;
}

template <typename T>
typename List<T>::Node* List<T>::getFirst()
{
return head;
}

template <typename T>
typename List<T>::Node* List<T>::getLast()
{
if(!head) return NULL;
Node* cur = head;
while(cur->next != NULL) {
cur = cur->next;
}
return cur;
}

template <typename T>
void List<T>::display()
{
if(!head) return;
Node *cur = head;
while(cur) {
cout << cur->data << " " << endl;
cur = cur->next;
}
cout << endl;
}

template <typename T>
void List<T>::reverse()
{
Node* prev = NULL;
Node* current = head;
Node* next;
while (current != NULL)
{
next = current->next;
current->next = prev;   
prev = current;
current = next;
}
head = prev;
}

###############   nodeList.cpp ############

#include <iostream>
#include "nodeList.h"
#include <string>

using namespace std;

int main()
{
List<string> *myList = new List<string>(NULL);
  
cout << "push_back() Milk, Eggs, Butter, Cheese ";
myList->push_back("Milk");
myList->push_back("Eggs");
myList->push_back("Butter");
myList->push_back("Cheese");
myList->display();
  
cout << "push_front() Flour, Sugar, Apples, Oranges ";
myList->push_front("Flour");
myList->push_front("Sugar");
myList->push_front("Apples");
myList->push_front("Oranges");
myList->display();
  
cout << "Erase Eggs ";
myList->erase(myList->search("Eggs"));
myList->display();
  
cout << "Insert Eggs before Oranges ";
myList->insert(myList->search("Oranges"),"Eggs");
myList->display();
  
cout << "pop_back() ";
cout << myList->pop_back() << " just back popped ";
myList->display();
  
cout << "pop_front() ";
cout << myList->pop_front() << " just front popped ";
myList->display();

cout<<" First Node content : "<<myList->getFirst()->data<<endl;
cout<<"Last Node content : "<<myList->getLast()->data<<endl;
  
  
  
return 0;
}

######### sample run: ########

thirdweek
thirdweek g++ nodeList.cpp
thirdweek ./a.out
push_back() Milk, Eggs, Butter, Cheese

Milk
Eggs
Butter
Cheese

push_front() Flour, Sugar, Apples, Oranges

Oranges
Apples
Sugar
Flour
Milk
Eggs
Butter
Cheese

Erase Eggs

Oranges
Apples
Sugar
Flour
Milk
Butter
Cheese

Insert Eggs before Oranges

Eggs
Oranges
Apples
Sugar
Flour
Milk
Butter
Cheese

pop_back()
Cheese just back popped

Eggs
Oranges
Apples
Sugar
Flour
Milk
Butter

pop_front()
Eggs just front popped

Oranges
Apples
Sugar
Flour
Milk
Butter

First Node content : Oranges
Last Node content : Butter
thirdweek

Related Questions

Navigate

• Browse (All)
• Browse T
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.