use a linked list as the backend data structure.You may not add any more public
ID: 3549497 • Letter: U
Question
use a linked list as the backend data structure.You may not add any more public functions, but you can implement as many private helper functions as you wish.
const int MAX_SIZE 30;
private:
struct Node
{
int data;
Node *link;
};
Node *head; // the head of the list
Node *tail; // the tail of the list
Node *curr; // the current position in the list
int num_items; // the number of items in the list
public:
// constructor
// remember that an empty list has a "size" of -1 and its "position" is at -1
List()
{
}
// copy constructor
// clones the list l and sets the last element as the current
List(const List& l)
{
}
// copy constructor
// clones the list l and sets the last element as the current
void operator=(const List& l)
{
}
// navigates to the beginning of the list
void First()
{
}
// navigates to the end of the list
// the end of the list is at the last valid item in the list
void Last()
{
}
// navigates to the specified element (0-index)
// this should not be possible for an empty list
// this should not be possible for invalid positions
void SetPos(int pos)
{
}
// navigates to the previous element
// this should not be possible for an empty list
// there should be no wrap-around
void Prev()
{
}
// navigates to the next element
// this should not be possible for an empty list
// there should be no wrap-around
void Next()
{
}
// returns the location of the current element (or -1)
int GetPos()
{
}
// returns the value of the current element (or -1)
int GetValue()
{
}
// returns the size of the list
// size does not imply capacity
int GetSize()
{
}
// inserts an item before the current element
// the new element becomes the current
// this should not be possible for a full list
void InsertBefore(int data)
{
}
// inserts an item after the current element
// the new element becomes the current
// this should not be possible for a full list
void InsertAfter(int data)
{
}
// removes the current element (collapsing the list)
// this should not be possible for an empty list
void Remove()
{
}
// replaces the value of the current element with the specified value
// this should not be possible for an empty list
void Replace(int data)
{
}
// returns if the list is empty
bool IsEmpty()
{
}
// returns if the list is full
bool IsFull()
{
}
// returns the concatenation of two lists
// l should not be modified
// l should be concatenated to the end of *this
// the returned list should not exceed MAX_SIZE elements
// the last element of the new list is the current
List operator+(const List& l) const
{
}
// returns if two lists are equal (by value)
bool operator==(const List& l) const
{
}
// returns if two lists are not equal (by value)
bool operator!=(const List& l) const
{
}
// returns a string representation of the entire list (e.g., 1 2 3 4 5)
// the string "NULL" should be returned for an empty list
friend ostream& operator<<(ostream& out, const List &l)
{
}
};
Explanation / Answer
// Simple C++ Class if you need more help mail me at ashishkguptaiit.cse@gmail.com
// I think you have not specified main, so you can write main, if furthur doubts you can ask me.
#include <iostream>
using namespace std;
const int MAX_SIZE 30;
class List
{
private:
struct Node
{
int data;
Node *next;
}typedef Node;
Node *head; // the head of the list
Node *tail; // the tail of the list
Node *curr; // the current position in the list
int num_items; // the number of items in the list
public:
// constructor
// remember that an empty list has a "size" of -1 and its "position" is at -1
List()
{
head = NULL;
tail = NULL;
curr = NULL;
num_items = 0;
}
// copy constructor
// clones the list l and sets the last element as the current
List(const List &l)
{
while(l.IsEmpty())
{
Node *tmp = new Node;
tmp->item = l.GetData();
tmp->next = NULL;
if(head == NULL)
{
head = tmp;
tail = tmp;
num_items++;
curr = head;
}
else
{
tail ->next = tmp;
tail = tmp;
curr = tail;
num_items++;
}
}
}
// copy constructor
// clones the list l and sets the last element as the current
void operator=(const List& l)
{
}
// navigates to the beginning of the list
void First()
{
curr = head;
}
// navigates to the end of the list
// the end of the list is at the last valid item in the list
void Last()
{
curr = tail;
}
// navigates to the specified element (0-index)
// this should not be possible for an empty list
// this should not be possible for invalid positions
void SetPos(int pos)
{
Node *temp = head;
while(pos > 1)
{
if(temp != NULL)
temp = temp -> next;
pos--;
}
curr = temp;
}
// navigates to the previous element
// this should not be possible for an empty list
// there should be no wrap-around
void Prev()
{
Node *tmp = head;
while(tmp ->next != curr && tmp ->next != NULL)
{
cout << "Item is :" << tmp->item << " ";
tmp = tmp->next;
}
curr = tmp;
}
// navigates to the next element
// this should not be possible for an empty list
// there should be no wrap-around
void Next()
{
Node *tmp = curr;
if(tmp->next != NULL)
tmp = tmp->next;
curr = tmp;
}
// returns the location of the current element (or -1)
int GetPos()
{
Node *tmp = head;
int i = 0;
while(tmp->next != curr && tmp != NULL)
{
if(tmp ==NULL)
{
return -1;
}
else
{
tmp = tmp->next;
i++;
}
}
return ++i;
}
// returns the value of the current element (or -1)
int GetValue()
{
if(curr != NULL)
return curr->data;
}
// returns the size of the list
// size does not imply capacity
int GetSize()
{
return num_items;
}
// inserts an item before the current element
// the new element becomes the current
// this should not be possible for a full list
void InsertBefore(int data)
{
Node *tmp = curr;
Prev();
Node *n = new Node;
if(curr != NULL)
{
n->next = curr->next;
curr->next = n;
curr = n;
}
else
{
curr = n;
head = n;
tail = n;
}
num_items++;
}
// inserts an item after the current element
// the new element becomes the current
// this should not be possible for a full list
void InsertAfter(int data)
{
Node *n = new Node;
if(curr == NULL)
{
curr = n;
head = n;
tail = n;
}
else
{
n->next = curr->next;
curr ->next = n;
curr = n;
}
num_items++;
}
// removes the current element (collapsing the list)
// this should not be possible for an empty list
void Remove()
{
if(curr == NULL)
{
}
else if(curr -> next == NULL)
{
Node *temp = curr;
Prev();
tail = curr;
num_items--;
delete temp[];
}
}
// replaces the value of the current element with the specified value
// this should not be possible for an empty list
void Replace(int data)
{
}
// returns if the list is empty
bool IsEmpty()
{
if(head == NULL)
return 1;
else
return 0;
}
// returns if the list is full
bool IsFull()
{
if(num_items == MAX_SIZE)
return 1;
else
return 0;
}
// returns the concatenation of two lists
// l should not be modified
// l should be concatenated to the end of *this
// the returned list should not exceed MAX_SIZE elements
// the last element of the new list is the current
List operator+(const List& l) const
{
if(l.GetSize() + num_items > MAX_SIZE)
retrun -1;
else
{
curr = tail;
this->curr->next = l;
}
return *this;
}
// returns if two lists are equal (by value)
bool operator==(const List& l) const
{
Node *tmp = head
while(tmp != NULL && l)
{
if(tmp->item != l.GetValue )
return false
l.Next();
tmp = tmp->next;
}
return true;
}
// returns if two lists are not equal (by value)
bool operator!=(const List& l) const
{
if(num_items != l.GetSize())
return 0;
else
return 1;
}
// returns a string representation of the entire list (e.g., 1 2 3 4 5)
// the string "NULL" should be returned for an empty list
friend ostream& operator<<(ostream& out, const List &l)
{
if(l.GetSize() == )
cout << "NULL" << endl;
else
{
cout << "List is : "
while(!l.IsEmpty())
{
cout << l.GetItem() << " ";
l.Next();
}
cout << endl;
}
}
};
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.