(C++) Write the single linked list using the following information. LINKED_LIST.
ID: 3730907 • Letter: #
Question
(C++) Write the single linked list using the following information.
LINKED_LIST.H
#ifndef LINKED_LIST_H
#define LINKED_LIST_H
#include "node.h"
#include <iostream>
namespace lab0 {
class linked_list {
node *head, *tail;
public:
linked_list();
explicit linked_list(std::string &data);
linked_list(const linked_list &original);
virtual ~linked_list();
linked_list &operator=(const linked_list &RHS);
friend std::ostream& operator<<(std::ostream& stream, linked_list& RHS);
friend std::istream& operator>>(std::istream& stream, linked_list& RHS);
bool isEmpty() const;
unsigned listSize() const; //Note that you do **not** have a size variable in your linked list. You *MUST* count the nodes.
std::string get_value_at(unsigned location);
void insert(const std::string input, unsigned location = 0 ); //create a node from the input string and put it into the linked list at the given location
void append(const std::string input); //create a new node and put it at the end/tail of the linked list
void remove(unsigned location = 0); //Remove the node at the given location
void sort(); //Perform selection sort on the linked list
};
}
#endif
LINKED_LIST.CPP
#include <linked_list.h>
namespace lab0 {
linked_list::linked_list() { }
linked_list::linked_list(std::string &data) { }
linked_list::linked_list(const linked_list &original) { }
linked_list::~linked_list() { }
linked_list &lab5::linked_list::operator=(const linked_list &RHS) { }
bool linked_list::isEmpty() const { return false; }
unsigned linked_list::listSize() const { return 0; } //Note that you do **not** have a size variable in your linked list. You *MUST* count the nodes.
void linked_list::insert(const std::string input, unsigned int location) { //create a node from the input string and put it into the linked list at the given location
node *prev; node *current; node *temp = new node (input); current = head; }
void linked_list::append(const std::string input) { } //create a new node and put it at the end/tail of the linked list
void linked_list::remove(unsigned location) { } //Remove the node at the given location
std::ostream& operator<<(std::ostream &stream, linked_list &RHS) { return stream; }
std::istream& operator>>(std::istream &stream, linked_list &RHS) { return stream; }
void linked_list::sort() { } //Perform selection sort on the linked list
std::string linked_list::get_value_at(unsigned location) { }
}
Explanation / Answer
// node.h
#ifndef NODE_H
#define NODE_H
#include <string>
namespace lab0 {
class node
{
public:
std::string name_;
node* next_;
node(std::string name);
~node();
};
}
#endif
//node.cpp
#include "node.h"
using namespace lab0;
node::node(std::string name) : name_(name)
{}
node::~node()
{}
//linked_list.h
#ifndef LINKED_LIST_H
#define LINKED_LIST_H
#include "node.h"
#include <iostream>
namespace lab0 {
class linked_list {
node *head, *tail;
public:
linked_list();
explicit linked_list(std::string &data);
linked_list(const linked_list &original);
virtual ~linked_list();
linked_list &operator=(const linked_list &RHS);
friend std::ostream& operator<<(std::ostream& stream, linked_list& RHS);
friend std::istream& operator >> (std::istream& stream, linked_list& RHS);
bool isEmpty() const;
unsigned listSize() const; //Note that you do **not** have a size variable in your linked list. You *MUST* count the nodes.
std::string get_value_at(unsigned location);
void insert(const std::string input, unsigned location = 0); //create a node from the input string and put it into the linked list at the given location
void append(const std::string input); //create a new node and put it at the end/tail of the linked list
void remove(unsigned location = 0); //Remove the node at the given location
void sort(); //Perform selection sort on the linked list
};
}
#endif
//linked_list.cpp
#include "linked_list.h"
#include <algorithm>
using lab0::node;
using lab0::linked_list;
linked_list::linked_list() { }
linked_list::linked_list(std::string &data)
{
// Initializing the linked list
head = new node(data);
tail = head;
}
linked_list::linked_list(const linked_list &original)
{
this->head = original.head;
this->tail = original.tail;
}
linked_list::~linked_list()
{
if (!head) return;
node* next;
while (head->next_)
{
next = head->next_;
delete head;
head = next;
}
if (head)
delete head;
if (tail)
delete tail;
}
linked_list &linked_list::operator=(const linked_list &RHS)
{
if (this != &RHS)
{
this->head = RHS.head;
this->tail = RHS.tail;
}
return *this;
}
bool linked_list::isEmpty() const
{
return head ? false : true;
}
unsigned linked_list::listSize() const
{
if (!head) return 0;
unsigned count = 1;
node* temp = head;
while (temp->next_)
{
count++;
}
return count;
} //Note that you do **not** have a size variable in your linked list. You *MUST* count the nodes.
void linked_list::insert(const std::string input, unsigned int location)
{
//create a node from the input string and put it into the linked list at the given location
node *current = head;
node *temp = new node(input);
current = head;
unsigned int count = 0;
for (unsigned int i = 0; i < location; i++)
{
current = current->next_;
}
temp->next_ = current->next_;
current->next_ = temp;
}
void linked_list::append(const std::string input)
{
node* temp = new node(input);
tail->next_ = temp;
tail = temp;
} //create a new node and put it at the end/tail of the linked list
void linked_list::remove(unsigned location)
{
node *prev;
node *current = head;
current = head;
for (unsigned int i = 0; i < location; i++)
{
prev = current;
current = current->next_;
}
prev->next_ = current->next_;
} //Remove the node at the given location
std::ostream& lab0::operator<<(std::ostream &stream, linked_list &RHS)
{
node* temp = RHS.head;
if (!temp) return stream;
do
{
stream << temp->name_ << std::endl;
temp = temp->next_;
} while (temp->next_);
return stream;
}
std::istream& operator >> (std::istream &stream, linked_list &RHS)
{
std::string name;
stream >> name;
RHS.append(name);
return stream;
}
void linked_list::sort()
{
if (!head)
return;
node* outer_temp = head;
node* inner_temp;
std::string temp;
while (outer_temp->next_)
{
inner_temp = outer_temp->next_;
while (inner_temp->next_)
{
if (std::min(outer_temp->name_, inner_temp->next_->name_) != outer_temp->name_)
{
temp = inner_temp->name_;
inner_temp->name_ = outer_temp->name_;
outer_temp->name_ = temp;
}
inner_temp = inner_temp->next_;
}
outer_temp = outer_temp->next_;
}
} //Perform selection sort on the linked list
std::string linked_list::get_value_at(unsigned location)
{
node* temp = head;
for (unsigned int i = 0; i < location; i++)
{
temp = temp->next_;
}
return temp->name_;
}
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.