PART 1
Implement a C++ class for an array representation of a list. The methods must be based upon the pseudocode provided on the CS210 Algorithms below. Use the following declarations as a starting point for your implementation.
const int MAX_LENGTH = some application-specific max value;
typedef <some data type> DataType;
class List
{
public:
methods go here
private:
int p;
int length;
DataType a [MAX_LENGTH];
};
Note: Any other variable or constant declarations required would be local to the methods.
List
Create ()
// this is the constructor
// initializes the list
length = 0
p = -1
ResetP ()
// sets p
p = -1
return
Iterate ()
// sets p to point to the next element in the list
// always call ResetP prior to the initial call to Iterate
// always call IsPSet after each call to Iterate
p ++
return
IsPSet ()
// checks whether p points to an element in the list
if p < 0 or p > length - 1
return FALSE
return TRUE
GetP ()
// returns the current value of p
return p
SetP (q)
// always call IsPSet after each call to SetP
// sets p
p = q
return
Read ()
// returns the value of the element pointed to by p
// p must be set prior to calling Read
// always call IsPSet prior to calling Read
return a [p]
Write (x)
// writes a new value into the element pointed to by p
// p must be set prior to calling Write
// always call IsPSet prior to calling Write
// could cause a problem in a sorted list if the key is changed
a [p] = x
return
Length ()
// returns the number of elements in the list
return length
IsEmpty ()
// checks whether the list is empty
if length == 0
return TRUE
return FALSE
IsFull ()
// checks whether the list is full
if length == MAX_LENGTH
return TRUE
return FALSE
InsertUnsorted (x)
// inserts a new element at the end of the list
// always call IsFull prior to calling InsertUnsorted
// sets p
p = length
a [p] = x
length ++
return
FindUnsorted (x)
// always call IsEmpty prior to calling FindUnsorted
// sets p
p = 0
while p < length
if x == a [p]
return TRUE
p++
return FALSE
DeleteUnsorted ()
// deletes element pointed to by p
// p must be set prior to calling DeleteUnsorted
// always call IsPSet prior to calling DeleteUnsorted
// moves the last element into the element pointed to by p
a [p] = a [length - 1]
length --
return
InsertSorted (x)
// inserts a new element into the list in sorted order
// always call IsFull prior to calling InsertSorted
// p will point to where the new element should be inserted
// moves all elements to the right of p one element to the right to make space for the new element
// sets p
p = 0
while p < length and x > a [p]
p ++
q = length
while q > p
a [q] = a [q - 1]
q --
a [p] = x
length ++
return
FindSorted (x)
// binary search
// always call IsEmpty prior to calling FindSorted
// sets p
q = 0
r = length - 1
while q <= r
p = (q + r) / 2
if x < a [p]
r = p - 1
else if x > a [p]
q = p + 1
else
return TRUE
return FALSE
DeleteSorted ()
// deletes element pointed to by p
// p must be set prior to calling DeleteSorted
// always call IsPSet prior to calling DeleteSorted
// all elements following the one pointed to by p are moved one element to the left
// sets p
q = p
p ++
while p < length
a [p - 1] = a[p]
p ++
length --
p = q
return
Clear ()
// reinitializes the list
length = 0
p = -1
return
PART 2
Implement a C++ class for a linked list representation of a list. The methods must be based upon the pseudocode provided on the CS210 Algorithms given below. Use the following declarations as a starting point for your implementation.
typedef <some data type> DataType;
struct Node;
struct Node
{
DataType value;
Node* next;
};
class List
{
public:
methods go here
private:
Node* head;
int length;
Node* p;
Node* prevP;
};
Note: Any other variable or constant declarations required would be local to the methods.
Linked list
Create ()
// this is the constructor
// initializes the list
p = NULL
head = NULL
length = 0
ResetP ()
// sets p
p = NULL
return
Iterate ()
// sets p to point to the next element in the list
// always call ResetP prior to the initial call to Iterate
// always call IsPSet after each call to Iterate
if p == NULL
prevP = NULL
p = head
else
prevP = p
p = p -> next
return
IsPSet ()
// checks whether p points to a node in the list
if p == NULL
return FALSE
return TRUE
GetP ()
// returns the current value of p
return p
SetP (q)
// always call IsEmpty prior to calling SetP
// always call IsPSet after each call to SetP
// sets p
prevP = NULL
p = head
while p != NULL and q != p
prevP = p
p = p -> next
return
Read ()
// returns the value of the node pointed to by p
// p must be set prior to calling Read
// always call IsPSet prior to calling Read
return p -> value
Write (x)
// writes a new value into the node pointed to by p
// p must be set prior to calling Write
// always call IsPSet prior to calling Write
// could cause a problem in a sorted list if the key is changed
p -> value = x
return
Length ()
// returns the number of nodes in the list
return length
IsEmpty ()
// checks whether the list is empty
if length == 0
return TRUE
return FALSE
IsFull ()
// checks whether the list is full
q = new Node
if BAD_ALLOCATION
return TRUE
delete q
return FALSE
InsertHead (x)
// inserts a new node at the beginning of the list
// always call IsFull prior to calling InsertHead
// sets p
p = new Node
p -> value = x
p -> next = head
prevP = NULL
head = p
length ++
return
InsertSorted (x)
// inserts a new node in the list
// always call IsFull prior to calling InsertSorted
// sets p
q = new Node
prevP = NULL
p = head
while p != NULL and x >= p -> value
prevP = p
p = p -> next
q -> value = x
q -> next = p
if prevP == NULL
head = q
else
prevP -> next = q
p = q
length ++
return
InsertTail (x)
// inserts a new node at the end of the list
// always call IsFull prior to calling InsertTail
// always call IsEmpty prior to calling InsertTail
// p must be set prior to calling InsertTail
// always call IsPSet prior to calling InsertTail
// starts scanning at the node p is pointing to
// sets p
q = new Node
q -> value = x
q -> next = NULL
while p != NULL
prevP = p
p = p -> next
prevP -> next = q
p = q
length ++
return
Find (x)
// scans the list from left to right
// always call IsEmpty prior to calling Find
// sets p
prevP = NULL
p = head
while p != NULL
if x == p -> value
return TRUE
prevP = p
p = p -> next
return FALSE
DeleteHead ()
// deletes the first node in the list
// always call IsEmpty prior to calling DeleteHead
// sets p
prevP = NULL
p = head
head = head -> next
delete p
p = head
length --
return
Delete ()
// deletes a node from the list
// p must be set prior to calling Delete
// always call IsPSet prior to calling Delete
// sets p
if prevP == NULL
head = head -> next
q = head
else
if p -> next == NULL
prevP -> next = NULL
else
prevP -> next = p -> next
q = p -> next
delete p
p = q
length --
return
DeleteTail ()
// deletes the last node in the list
// always call IsEmpty prior to calling DeleteTail
// p must be set prior to calling DeleteTail
// always call IsPSet prior to calling DeleteTail
// starts scanning at node p is pointing to
// sets p
while p -> next != NULL
prevP = p
p = p -> next
if prevP == NULL
head = NULL
else
prevP -> next = NULL
delete p
p = NULL
length --
return
Clear ()
// reinitializes the list
while head != NULL
p = head
head = head -> next
delete p
p = NULL
length = 0
return
PART 3
Implement a C++ program that can be used to demonstrate that the list classes implemented in Parts 1 and 2 are correct. To simplify the demonstration, set some application-specific max value to 10 and some data type to int.
PART 4
For programming problems, the Results are worth 70%. So, for this problem, the Results are worth 70 marks out of the 100 marks available. Demonstrate that the list classes are correct. Be sure to demonstrate all possible execution sequences, including boundary conditions and error conditions as discussed in class. Your demonstration should be captured in a script file.
Using List
Screenshot
Program
//Header files
#include <iostream>
using namespace std;
//Constant
const int MAX_LENGTH = 10;
typedef int DataType;
//Create a list class
class List{
public:
//Constructor
List();
//Reset
void ResetP();
//Get next element
void iterate();
//Check p in the range
bool isPSet();
//Get p
int getP();
//set p value;
void setP(int q);
//Get elemnt from array
DataType read();
//write into array
void write(DataType x);
// returns the number of elements in the list
int Length();
//Empty list check
bool isEmpty();
// checks whether the list is full
bool isFull();
// inserts a new element at the end of the list
void insertUnsorted(DataType x);
//Check a value present in list
bool findUnsorted(DataType x);
//Delete an element
void deleteUnsorted();
// inserts a new element at the end of the list
void insertSorted(DataType x);
//Check a value present in list
bool findSorted(DataType x);
//Delete an element
void deleteSorted();
//Clear
void clear();
private:
int p;
int length;
DataType a[MAX_LENGTH];
};
// this is the constructor
// initializes the list
List::List() {
length = 0;
p = -1;
}
//ResetP ()
void List::ResetP() {
p = -1;
}
//sets p to point to the next element in the list
// always call ResetP prior to the initial call to
// always call IsPSet after each call to Iterateint main()
void List::iterate() {
p++;
}
// checks whether p points to an element in the list
bool List::isPSet() {
if (p < 0 || p > length - 1)
return false;
return true;
}
// returns the current value of p
int List::getP() {
return p;
}
void List::setP(int q)
{
p = q;
}
// returns the value of the element pointed to by p
// p must be set prior to calling Read
// always call IsPSet prior to calling Read
DataType List::read() {
return a[p];
}
// writes a new value into the element pointed to by p
// p must be set prior to calling Write
// always call IsPSet prior to calling Write
// could cause a problem in a sorted list if the key is
changed
void List::write(DataType x) {
if (isPSet()) {
a[p] = x;
}
}
// returns the number of elements in the list
int List::Length() {
return length;
}
// checks whether the list is empty
bool List::isEmpty() {
if (length == 0)
return true;
return false;
}
// checks whether the list is full
bool List::isFull() {
if (length == MAX_LENGTH)
return true;
return false;
}
// inserts a new element at the end of the list
// always call IsFull prior to calling InsertUnsorted
// sets p
void List::insertUnsorted(DataType x) {
if (!isFull()) {
p = length;
a[p] = x;
length++;
}
}
// always call IsEmpty prior to calling FindUnsorted
// sets p
bool List::findUnsorted(DataType x) {
if (!isEmpty()) {
p = 0;
while (p < length) {
if (x ==
a[p]){
return true;
}
p++;
}
return false;
}
return false;
}
// deletes element pointed to by p
// p must be set prior to calling DeleteUnsorted
// always call IsPSet prior to calling DeleteUnsorted
// moves the last element into the element pointed to by p
void List::deleteUnsorted() {
if (isPSet()) {
a[p] = a[length - 1];
length--;
}
}
// inserts a new element into the list in sorted order
// always call IsFull prior to calling InsertSorted
// p will point to where the new element should be inserted
// moves all elements to the right of p one element to the right to
make space for the new element
// sets p
void List::insertSorted(DataType x) {
p = 0;
while (p < length and x > a[p]) {
p++;
}
int q = length;
while (q > p) {
a[q] = a[q - 1];
q--;
}
a[p] = x;
length++;
}
// binary search
// always call IsEmpty prior to calling FindSorted
// sets p
bool List::findSorted(DataType x) {
int q = 0;
int r = length - 1;
while (q <= r) {
p = (q + r) / 2;
if (x < a[p]) {
r = p - 1;
}
else if (x > a[p]) {
q = p + 1;
}
else {
return
true;
}
}
return false;
}
// deletes element pointed to by p
// p must be set prior to calling DeleteSorted
// always call IsPSet prior to calling DeleteSorted
// all elements following the one pointed to by p are moved one
element to the left
// sets p
void List::deleteSorted() {
int q = p;
p++;
while (p < length) {
a[p - 1] = a[p];
p++;
}
length--;
p = q;
}
// reinitializes the list
void List::clear() {
length = 0;
p = -1;
}
int main()
{
//Create a list
List list;
//Add elements into unsorted list
list.insertUnsorted(10);
list.insertUnsorted(5);
list.insertUnsorted(6);
//Display list
list.ResetP();
list.iterate();
cout << "Unsorted List elements are: ";
while (list.isPSet()) {
cout << list.read()<<"
";
list.iterate();
}
cout << endl;
//Check the write opertaton
list.ResetP();
list.iterate();
list.write(7);
//Display list
list.ResetP();
list.iterate();
cout << "Unsorted List elements after write are:
";
while (list.isPSet()) {
cout << list.read() <<
" ";
list.iterate();
}
//Clear list
list.clear();
//Add elements into sorted list
list.insertSorted(10);
list.insertSorted(5);
list.insertSorted(6);
//Display list
list.ResetP();
list.iterate();
cout << "\nSorted List elements are: ";
while (list.isPSet()) {
cout << list.read() <<
" ";
list.iterate();
}
cout << endl;
//Deletion check
list.ResetP();
list.iterate();
list.deleteSorted();
//Find check
if (list.findSorted(5)) {
cout << "5 Found in the
list!!" << endl;
}
else {
cout << "5 Not Found in the
list!!" << endl;
}
}
Output
Unsorted List elements are: 10 5 6
Unsorted List elements after write are: 7 5 6
Sorted List elements are: 5 6 10
5 Not Found in the list!!
----------------------------------------------------------------------------------------------------------------------
Using Linkedlist
Screenshot
Program
#include <iostream>
using namespace std;
typedef int DataType;
struct Node;
struct Node{
DataType value;
Node* next;
};
class List{
public:
List();
void ResetP();
void Iterate();
bool IsPSet();
Node* GetP();
void SetP(Node* q);
DataType Read();
void Write(DataType x);
int Length();
bool IsEmpty();
bool IsFull();
void InsertHead(DataType x);
void InsertSorted(DataType x);
void InsertTail(DataType x);
bool Find(DataType x);
void DeleteHead();
void Delete();
void DeleteTail();
void Clear();
private:
Node* head;
int length;
Node* p;
Node* prevP;
};
// this is the constructor
// initializes the list
List::List() {
p = NULL;
head = NULL;
length = 0;
}
// sets p
void List::ResetP() {
p = NULL;
}
// sets p to point to the next element in the list
// always call ResetP prior to the initial call to Iterate
// always call IsPSet after each call to Iterate
void List::Iterate() {
if (p == NULL){
prevP = NULL;
p = head;
}
else {
prevP = p;
p = p->next;
}
}
// checks whether p points to a node in the list
bool List::IsPSet() {
if (p == NULL) {
return false;
}
return true;
}
// returns the current value of p
Node* List::GetP() {
return p;
}
// always call IsEmpty prior to calling SetP
// always call IsPSet after each call to SetP
// sets p
void List::SetP(Node* q) {
prevP = NULL;
p = head;
while (p != NULL and q != p) {
prevP = p;
p = p->next;
}
}
// returns the value of the node pointed to by p
// p must be set prior to calling Read
// always call IsPSet prior to calling Read
DataType List::Read() {
return p->value;
}
// writes a new value into the node pointed to by p
// p must be set prior to calling Write
// always call IsPSet prior to calling Write
// could cause a problem in a sorted list if the key is
changed
void List::Write(DataType x) {
p->value = x;
}
// returns the number of nodes in the list
int List::Length() {
return length;
}
// checks whether the list is empty
bool List::IsEmpty() {
if (length == 0) {
return true;
}
return false;
}
// checks whether the list is full
bool List::IsFull() {
try
{
Node* q = new Node;
delete q;
return false;
}
catch (bad_alloc & ba)
{
return true;
}
}
// inserts a new node at the beginning of the list
// always call IsFull prior to calling InsertHead
// sets p
void List::InsertHead(DataType x) {
p = new Node;
p->value = x;
p->next = head;
prevP = NULL;
head = p;
length++;
}
// inserts a new node in the list
// always call IsFull prior to calling InsertSorted
// sets p
void List::InsertSorted(DataType x) {
Node* q = new Node;
prevP = NULL;
p = head;
while (p != NULL and x >= p->value) {
prevP = p;
p = p->next;
}
q->value = x;
q->next = p;
if (prevP == NULL) {
head = q;
}
else {
prevP->next = q;
}
p = q;
length++;
}
// inserts a new node at the end of the list
// always call IsFull prior to calling InsertTail
// always call IsEmpty prior to calling InsertTail
// p must be set prior to calling InsertTail
// always call IsPSet prior to calling InsertTail
// starts scanning at the node p is pointing to
// sets p
void List::InsertTail(DataType x) {
Node* q = new Node;
q->value = x;
q->next = NULL;
while (p != NULL) {
prevP = p;
p = p->next;
}
prevP->next = q;
p = q;
length++;
}
// scans the list from left to right
// always call IsEmpty prior to calling Find
// sets p
bool List::Find(DataType x) {
prevP = NULL;
p = head;
while (p != NULL) {
if (x == p->value) {
return
true;
}
prevP = p;
p = p->next;
return true;
}
}
// deletes the first node in the list
// always call IsEmpty prior to calling DeleteHead
// sets p
void List::DeleteHead() {
prevP = NULL;
p = head;
head = head->next;
delete p;
p = head;
length--;
}
// deletes a node from the list
// p must be set prior to calling Delete
// always call IsPSet prior to calling Delete
// sets p
void List::Delete() {
Node* q;
if (prevP == NULL) {
head = head->next;
q = head;
}
else {
if (p->next == NULL)
prevP->next =
NULL;
else
prevP->next =
p->next;
q = p->next;
}
delete p;
p = q;
length--;
}
// deletes the last node in the list
// always call IsEmpty prior to calling DeleteTail
// p must be set prior to calling DeleteTail
// always call IsPSet prior to calling DeleteTail
// starts scanning at node p is pointing to
// sets p
void List::DeleteTail() {
while (p->next != NULL) {
prevP = p;
p = p->next;
}
if (prevP == NULL)
head = NULL;
else
prevP->next = NULL;
delete p;
p = NULL;
length--;
}
// reinitializes the list
void List::Clear() {
while (head != NULL) {
p = head;
head = head->next;
delete p;
}
p = NULL;
length = 0;
}
int main()
{
//Create a list
List list;
//Add elements into list
list.InsertHead(10);
list.InsertTail(5);
list.InsertHead(6);
//Display list
list.ResetP();
list.Iterate();
cout << "Unsorted List elements are: ";
while (list.IsPSet()) {
cout << list.Read() <<
" ";
list.Iterate();
}
cout << endl;
//Check the write opertaton
list.ResetP();
list.Iterate();
list.Write(7);
//Display list
list.ResetP();
list.Iterate();
cout << "Unsorted List elements after write are:
";
while (list.IsPSet()) {
cout << list.Read() <<
" ";
list.Iterate();
}
//Clear list
list.Clear();
//Add elements into sorted list
list.InsertSorted(10);
list.InsertSorted(5);
list.InsertSorted(6);
//Display list
list.ResetP();
list.Iterate();
cout << "\nSorted List elements are: ";
while (list.IsPSet()) {
cout << list.Read() <<
" ";
list.Iterate();
}
cout << endl;
//Deletion check
list.ResetP();
list.Iterate();
list.Delete();
//Find check
if (list.Find(5)) {
cout << "5 Found in the
list!!" << endl;
}
else {
cout << "5 Not Found in the
list!!" << endl;
}
}
Output
Unsorted List elements are: 6 10 5
Unsorted List elements after write are: 7 10 5
Sorted List elements are: 5 6 10
5 Found in the list!!
--------------------------------------------------------------
Note:-
I wrote some test cases , you check and let me know, if you have any doubt;
PART 1 Implement a C++ class for an array representation of a list. The methods must...
C++ Create a class that implements a sorted, doubly-linked list: Start with a copy of the sortedList class. Call your new class doublyLinkedList. Convert the baseline code into a doubly linkedlist, and thoroughly test all existing operations (make sure to check all edge conditions), and then implement the new operations below. The class should have the following additional class methods: • A reverse method: this method will reverse the order of the doubly linked list. This method takes no parameters,...
// 1. Add methods to get and set, Data and Link. Data should be any Comparable object. class Node { Integer data; // Integer is Comparable Node link; public Node(Integer data, Node link) { this.data = data; this.link = link; } public Integer getData() { return data; } public void setData(Integer data) { this.data = data; } public Node getLink() { return link; } public void setLink(Node link) { this.link = link; } } // b. Create MyLinkedList class and...
could somone please help me to complete this ! public class MyLinkedList<AnyType> { private Node<AnyType> head, tail; private int size; public MyLinkedList() { this.head = null; this.tail = null; this.size = 0; } //1.Insert a node at the end of the list public void insert(AnyType data) { Node<AnyType> newNode = new Node(); newNode.data = data; if (head == null) { head = newNode; tail = newNode; head.next = null; tail.next = null; } else { tail.next = newNode; tail =...
Q) Modify the class Linked List below to make it a Doubly Linked List. Name your class DoublyLinkedList. Add a method addEnd to add an integer at the end of the list and a method displayInReverse to print the list backwards. void addEnd(int x): create this method to add x to the end of the list. void displayInReverse(): create this method to display the list elements from the last item to the first one. Create a main() function to test...
c++ modify the attached unsorted linked list class into a sorted linked list class #include <iostream> using namespace std; template<class T> struct Node { T data;//data field Node * next;//link field Node(T data) { this->data = data; } }; template<class T> class linked_list{ private: Node<T> *head,*current; public: linked_list(){//constructor, empty linked list head = NULL; current = NULL; } ~linked_list(){ current = head; while(current != NULL) { ...
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...
Data Structures - Singly Linked Lists You will add a method swapNodes to SinglyLinkedList class (below). This method should swap two nodes node1 and node2 (and not just their contents) given references only to node1 and node2. The new method should check if node1 and node2 are the same node, etc. Write the main method to test the swapNodes method. You may need to traverse the list. package linkedlists; public class SinglyLinkedList<E> implements Cloneable { // ---------------- nested Node class...
Java help: Please help complete the locate method that is in bold.. public class LinkedDoubleEndedList implements DoubleEndedList { private Node front; // first node in list private Node rear; // last node in list private int size; // number of elements in list ////////////////////////////////////////////////// // YOU MUST IMPLEMENT THE LOCATE METHOD BELOW // ////////////////////////////////////////////////// /** * Returns the position of the node containing the given value, where * the front node is at position zero and the rear node is...
Here is the IntegerLinkedList_incomplete class: public class IntegerLinkedList { static class Node { /** The element stored at this node */ private int element; // reference to the element stored at this node /** A reference to the subsequent node in the list */ private Node next; // reference to the subsequent node in the list /** * Creates a node with the given element and next node. * * @param e the element to be stored * @param n...
Q1: You can find a file that defines the CircularlyLinked List class similar to what we discussed in the class. Download the file and work on it. Your task is to: 1. Complete the missing methods in the file as discussed in the class. Search for the comment/" MISSING / in the file to see the methods that need to be completed. 2. Add the following methods to the class a. public Node getMin 1. Task: find the node with...