Take the linked list program (provided) and write a linked list implementation o
ID: 3735678 • Letter: T
Question
Take the linked list program (provided) and write a linked list implementation of the stack data structure. You can refer to the web but you must use the supplied code as a starting point and evolve it to work as a stack. Test the code and present your changes and the testing.(Please use the following linked list code)
// declaring functions prototypes
#include <iostream>
#include <stdlib.h>
using namespace std;
struct node {
int data;
struct node *next;
};
struct node *start = NULL;
struct node *create_ll(struct node *);
struct node *display(struct node *);
struct node *remove_beg(struct node *);
struct node *remove_list(struct node *);
struct node *remove_end(struct node *);
struct node *sort_list(struct node *);
struct node *remove_sorted(struct node *);
struct node *insert_sorted(struct node *);
int main (){
int option;
do {
cout << " Main Menu: ";
cout << " 1: Create a List";
cout << " 2: Display a List";
cout << " 3: Remove from the beginning of the List";
cout << " 4: Remove the whole list";
cout << " 5: Remove from the end of the list";
cout << " 6: Sort List";
cout << " 7: Remove from a Sorted List";
cout << " 8: Insert into a Sorted List";
cout << " 9: Exit";
cout << " Enter your option : ";
cin >> option;
switch (option) {
case 1:
start = create_ll(start);
cout << " LINKED LIST CREATED";
break;
case 2:
start = display(start);
break;
case 3:
start = remove_beg(start);
break;
case 4:
start = remove_list(start);
break;
case 5:
start = remove_end(start);
break;
case 6:
start = sort_list(start);
break;
case 7:
start = remove_sorted(start);
break;
case 8:
start = insert_sorted(start);
break;
}
}while (option != 9);
return 0;
}
struct node *create_ll(struct node *start) {
struct node *new_node;
int num;
cout << " Enter -1 to end";
cout << " Enter the data : ";
cin >> num;
while (num != -1) {
new_node = (node *) operator new (sizeof (node));
new_node->data=num;
if (start==NULL) {
new_node->next = NULL;
start = new_node;
} else {
new_node->next = start;
start = new_node;
}
cout << " Enter the data : ";
cin >> num;
}
return start;
}
struct node *display(struct node *start) {
struct node *ptr;
ptr = start;
cout << " ";
while (ptr != NULL) {
cout << ptr->data << " ";
ptr = ptr->next;
}
return start;
}
struct node *remove_beg(struct node *start) {
struct node *ptr;
if (start != NULL) {
ptr = start;
start = start->next;
delete ptr;
}
return start;
}
struct node *remove_list (struct node *start) {
struct node *ptr;
if (start != NULL ) {
ptr=start;
while(ptr != NULL) {
cout << " " << ptr->data << " is removed ";
start = remove_beg(ptr);
ptr = start;
}
}
return start;
}
struct node *remove_end(struct node *start){
struct node *ptr, *preptr;
if (start != NULL) {
ptr=start;
preptr=NULL;
while (ptr->next != NULL) {
preptr = ptr;
ptr = ptr->next;
}
if (preptr != NULL) {
preptr->next = NULL;
delete ptr;
} else {
start = remove_beg(ptr);
}
}
return start;
}
struct node *sort_list (struct node *start) {
struct node *ptr1, *ptr2;
int temp;
if (start != NULL) {
ptr1 = start;
while (ptr1->next != NULL) {
ptr2 = ptr1->next;
while(ptr2 != NULL) {
if (ptr1->data > ptr2->data){
temp = ptr1->data;
ptr1->data = ptr2->data;
ptr2->data = temp;
}
ptr2=ptr2->next;
}
ptr1=ptr1->next;
}
}
return start;
}
struct node *remove_sorted(struct node *start) {
struct node *ptr, *preptr;
int val;
bool matched;
cout << " Enter the value of the node which has to be deleted : ";
cin >> val;
if (start != NULL) {
ptr = start;
preptr=NULL;
while (ptr->data != val && ptr->next != NULL) {
preptr=ptr;
ptr = ptr->next;
}
if (ptr->data == val) {
if (preptr != NULL){
preptr->next = ptr->next;
delete ptr;
} else {
start = remove_beg(ptr);
}
}else {
cout << " no match ";
}
}
return start;
}
struct node *insert_sorted(struct node *start){
struct node *new_node, *ptr, *preptr;
int num;
cout << " Enter the data : ";
cin >> num;
new_node = (node *) operator new (sizeof (node));
new_node->data = num;
if (start != NULL ) {
ptr= start;
while (ptr->data < num) {
preptr = ptr;
ptr = ptr->next;
if (ptr == NULL) {
break;
}
}
if (ptr == NULL) {
preptr->next = new_node;
new_node->next = NULL;
} else if (ptr == start) {
new_node->next = start;
start = new_node;
} else {
new_node->next = ptr;
preptr->next = new_node;
}
} else {
start = new_node;
start->next=NULL;
}
return start;
}
Explanation / Answer
//main.cpp
#include <iostream>
#include "linked_list.h"
void Test_PushFront()
{
std::cout << "can insert at the beginning of the list...";
LinkedList<char> list;
list.PushFront('a');
bool condition1 = !list.Empty();
bool condition2 = list.First() == 'a';
std::cout << ((condition1 && condition2) ? "OK " : "NOK ");
}
void Test_PopFront()
{
std::cout << "can remove from the beginning of the list...";
LinkedList<char> list;
list.PushFront('a');
list.PushFront('b');
bool condition1 = list.PopFront() == 'b';
bool condition2 = list.PopFront() == 'a';
bool condition3 = false;
try
{
// Try to pop from empty list:
list.PopFront();
}catch(EmptyList& e)
{
condition3 = true;
}
bool condition = condition1 && condition2 && condition3;
std::cout << ((condition) ? "OK " : "NOK ");
}
void Test_PushBack()
{
std::cout << "can insert at the end of the list...";
LinkedList<char> list;
list.PushBack('a');
bool condition1 = !list.Empty();
bool condition2 = list.Last() == 'a';
std::cout << ((condition1 && condition2) ? "OK " : "NOK ");
}
void Test_CopyConstructor()
{
std::cout << "can create an instance from another one...";
LinkedList<int> list;
for(int i = 0; i < 10; i++)
{
list.PushBack(i);
}
LinkedList<int> other(list);
bool condition = true;
for(int i = 0; i < 10; i++)
{
if(other.PopFront() != i) condition = false;
}
std::cout << ( condition ? "OK " : "NOK ");
}
void Test_OperatorEqual()
{
std::cout << "can create an instance from another one using operator=...";
LinkedList<int> list;
for(int i = 0; i < 10; i++)
{
list.PushBack(i);
}
LinkedList<int> other;
other = list;
bool condition = true;
for(int i = 0; i < 10; i++)
{
if(other.PopFront() != i) condition = false;
}
std::cout << ( condition ? "OK " : "NOK ");
}
void Test_Iterator()
{
std::cout << "can iterate throught the list via iterator object...";
LinkedList<int> list;
for(int i = 0; i < 10; i++)
{
list.PushBack(i);
}
bool condition1 = true;
int j;
Iterator<int> i = list.ForwardIterator();
for(j = 0; !i.End() && j<10; i.Next(), j++)
{
if(i.Get() != j) condition1 = false;
}
bool condition2 = false;
try
{
i.Next();
}catch(EmptyList& e)
{
condition2 = true;
}
std::cout << ((condition1 && condition2) ? "OK " : "NOK ");
}
void Test_Compare()
{
std::cout << "can compare two linked lists...";
LinkedList<int> first;
first.PushBack(1);
first.PushBack(2);
LinkedList<int> second;
second.PushBack(1);
second.PushBack(2);
bool condition1 = first == second;
bool condition2 = first == first;
second.PushBack(3);
bool condition3 = first != second;
bool condition = condition1 && condition2 && condition3;
std::cout << (condition ? "OK " : "NOK ");
}
int main()
{
std::cout << "Class LinkedList: ";
Test_PushFront();
Test_PopFront();
Test_PushBack();
Test_CopyConstructor();
Test_OperatorEqual();
Test_Iterator();
Test_Compare();
return 0;
}
--------------------------------------------------
//exceptions.h
#pragma once
#include <exception>
class EmptyList: public std::exception
{
public:
virtual const char * what() const throw()
{
return "List is empty";
}
};
--------------------------------------------
//iterator.h
#pragma once
#include "node.h"
#include "exceptions.h"
template<class T>
class Iterator
{
private:
Node<T> * start;
Node<T> * current;
public:
Iterator(Node<T> * start) { this->start = this->current = start; }
void Next()
{
if(current) current = current->GetNext();
else throw EmptyList();
}
T Get() const
{
if(current) return current->GetData();
else throw EmptyList();
}
void Set(const T& data)
{
if(current) current->SetData(data);
else throw EmptyList();
}
bool End() const { return current == NULL; }
};
-------------------------------------------------------------
//linked_list.h
#pragma once
#include "node.h"
#include "exceptions.h"
#include "iterator.h"
template<class T>
class LinkedList
{
private:
Node<T> * first;
Node<T> * last;
size_t size;
public:
LinkedList() { Initialize(); };
~LinkedList();
LinkedList(const LinkedList&);
LinkedList& operator=(const LinkedList&);
public:
void PushFront(const T&);
void PushBack(const T&);
bool Empty() const { return size == 0; }
void Print() const;
T First() const
{
if(Empty()) throw EmptyList();
else return first->GetData();
}
T Last() const
{
if(Empty()) throw EmptyList();
else return last->GetData();
}
T PopFront();
size_t GetSize() const { return size; }
public:
bool operator==(const LinkedList& other) const
{
if(this==&other) return true;
if(size != other.size) return false;
// Traverse the two linked list and check
// whether they have the same elements:
Iterator<T> i = this->ForwardIterator();
Iterator<T> j = other.ForwardIterator();
for(; !i.End() && !j.End(); i.Next(), j.Next() )
if(i.Get() != j.Get()) return false;
return true;
}
bool operator!=(const LinkedList& other) const { return !(*this==other); }
public:
Iterator<T> ForwardIterator() const { return Iterator<T>(this->first); }
private:
void Initialize();
void Free();
void CopyFrom(const LinkedList&);
};
template<class T>
void LinkedList<T>::Initialize()
{
first = NULL;
last = NULL;
size = 0;
}
template<class T>
void LinkedList<T>::Free()
{
Node<T> * next = first;
Node<T> * current = first;
while(next)
{
current = next;
next = current->GetNext();
delete current;
}
}
template<class T>
void LinkedList<T>::CopyFrom(const LinkedList& other)
{
Node<T> * temp = other.first;
T data;
while(temp)
{
data = temp->GetData();
temp = temp->GetNext();
PushBack(data);
}
}
template<class T>
LinkedList<T>::LinkedList(const LinkedList& other)
{
Initialize();
CopyFrom(other);
}
template<class T>
LinkedList<T>& LinkedList<T>::operator=(const LinkedList& other)
{
if(this == &other) return *this;
else
{
Free();
Initialize();
CopyFrom(other);
return *this;
}
}
template<class T>
LinkedList<T>::~LinkedList()
{
Free();
}
template<class T>
void LinkedList<T>::PushFront(const T& data)
{
if(Empty())
{
first = new Node<T>(data,NULL);
last = first;
}
else
{
Node<T> * old_first = first;
first = new Node<T>(data, old_first);
}
++size;
}
template<class T>
T LinkedList<T>::PopFront()
{
if(Empty() || !first) throw EmptyList();
else
{
Node<T> * old = first;
T data = first->GetData();
first = first->GetNext();
// If there are no elements:
if(first == NULL) last = NULL;
--size;
delete old;
return data;
}
}
template<class T>
void LinkedList<T>::PushBack(const T& data)
{
if(Empty())
{
first = new Node<T>(data, NULL);
last = first;
}
else
{
Node<T> * old_last = last;
last = new Node<T>(data, NULL);
old_last->SetNext(last);
}
++size;
}
template<class T>
void LinkedList<T>::Print() const
{
std::cout << "List contents: ";
for(Iterator<T> i = ForwardIterator(); !i.End(); i.Next())
std::cout << "|" << i.Get() << "|->";
std::cout << "NULL ";
}
-----------------------------------------------------------------------
//node.h
#pragma once
#include <iostream>
template<class T>
class Node
{
private:
T data;
Node * next;
public:
Node(const T& data, Node * next)
{
this->data = data;
this->next = next;
}
public:
T GetData() const { return data; }
void SetData(const T& data) { this->data = data; }
void SetNext(Node * next) { this->next = next; }
Node * GetNext() { if(next) return next; else return NULL; }
};
Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.