Answered step by step
Verified Expert Solution
Link Copied!

Question

1 Approved Answer

PLEASE DO NOT SPAM THE QUESTION I WILL AUTOMATICALLY DISLIKE IT (IF YOU SOLVE IT PLEASE POST A PICTURE OF IT WORKING ON YOUR END,

PLEASE DO NOT SPAM THE QUESTION I WILL AUTOMATICALLY DISLIKE IT (IF YOU SOLVE IT PLEASE POST A PICTURE OF IT WORKING ON YOUR END, THANKS)

Add a new method to the program (THE PROGRAM ALREADY WORKS) that will search the list for a specified value and return its index in the list (or -1 if not found). You are not implementing sorting, so don't try to implement a Binary search or other efficiencies. Just transverse the list and return an index where the integer value is found, or -1 if not found or the list is empty.

The new method should look similar to this:

// Private methods // -------------------------------------------------------- /** * Iterate node pointer to specified position in the list * @param position - 0 to size-1 * @return pointer to Node at List[position] (or null if empty) */ List::Node* List::traverse(int position) { Node* pNode = head; // start at head of list (null if empty) int counter = 0; // zero indexed list // (don't move if position == 0) while(counter < position && pNode->next) { pNode = pNode->next; counter++; } // traversal return pNode;

Code:

// File : List.cpp // Desc : Linked List ADT implementation // --------------------------------------------------------

#include

#include "List.h"

using namespace std;

/**

* Default constructor - initialize empty list

*/

List::List() {

head = NULL;

size = 0;

} // default constructor

/**

* Destructor - clean up nodes

*/

List::~List() {

Node* curr = head;

while( curr != NULL )

{

Node* temp = curr;

curr = curr->next;

delete temp;

}

} // destructor

/**

* Accessor for the list size property

* @return int size (empty = 0)

*/

int List::getSize() {

return size;

} // getSize

/**

* Signifies if the list is empty or not

* @return bool True if empty (size==0)

*/

bool List::isEmpty() {

return (size==0);

} // isEmpty

/**

* Add a new value into the list at the head, a

* specified position, or at the tail if position

* is -1 or invalid position

* @param value - int value to store

* @param position - position in list to store value

*/

void List::insert(int value, int position) {

// if position == -1, means adding node to end

if(position==-1)

{

//creating node

Node *newNode = new Node();

Node *last = head;

newNode->value = value;

newNode->next = NULL;

// is list is empty, then insert at starting

if(head==NULL)

{

head = newNode;

size++;

return;

}

// go to end of linked list

while(last->next!=NULL)

{

last = last->next;

}

// insert at end

last -> next = newNode;

size++; // increase the size

return;

}

else // else if position is not -1

{

Node *temp = head;

int x = 0;

// going to that position first

while(temp)

{

if(x==position)

{

// creating node, and inserting at position

Node *t= new Node();

t->value = value;

t->next = temp;

temp = t;

size++;

return;

}

x++;

temp=temp->next;

}

}

} // insert

/**

* Remove a value from the list at a specified position and

* return it to the caller

* @param position - position in the list or tail if -1

* or invalid position

* @return - value removed from the list

*/

int List::remove(int position) {

if (!head)

return -1;

Node* temp = head;

// If head needs to be removed

if (position == 0)

{

int x = head-> value;

head = temp->next;

free(temp);

size--;

return x;

}

// Find previous node of the node to be deleted

for (int i = 0; temp != NULL && i < position - 1; i++)

temp = temp->next;

// If position is more than number of nodes

if (temp == NULL || temp->next == NULL)

return -1;

// Node temp->next is the node to be deleted

// Store pointer to the next of node to be deleted

Node* next = temp->next->next;

// Unlink the node from linked list

free(temp->next); // Free memory

// Unlink the deleted node from list

temp->next = next;

return -1;

} // remove

/**

* Return a value from the list at a specified position without

* removing it

* @param position - position in the list

* @return - value found at position (-1 if not found or invalid position)

*/

int List::read(int position) {

int x = 0;

Node *temp =head;

// going to that position and returning the value

while(temp)

{

if(position==x)

{

return temp->value;

}

x++;

temp = temp->next;

}

// if position is not found, return -1

return -1;

} // read

/**

* Modify a value at a specified position in the list

* @param value - new value

* @param position - position in the list

*/

void List::modify(int value, int position) {

int x = 0;

// goinf to that position and modifying value

Node *temp = head;

while(temp)

{

if(position==x)

{

temp->value = value;

}

x++;

temp = temp->next;

}

} // modify

int main()

{

// sample run of program

// created list

List *l = new List();

// checking if linked list is empty or not

if(l->isEmpty())

cout<<"Linked list is empty. ";

else

cout<<"Linked list is not empty. ";

// inserting node to it

l->insert(10, -1); // at end

l->insert(20, 0); // at position 0

l->insert(30, -1); // at end

l->insert(40, -1); // at end

// printing size of linked list

cout<<" Size of Linked List : "<getSize()<

// checking if linked list is empty or not

if(l->isEmpty())

cout<<" Linked list is empty. ";

else

cout<<" Linked list is not empty. ";

// Reading node

cout<<" Node at position 0 is : "<read(0)<

cout<<"Node at position 1 is : "<read(1)<

cout<<"Node at position 2 is : "<read(2)<

// modifying node at 1 to 45

l->modify(45, 1);

// Reading node at position 1 after modifying

cout<<" Node at position 1 after modifying is : "<read(1)<

// removing node at position 2

l->remove(2);

// Reading node

cout<<" After removing node at index 2 ";

cout<<"Node at position 0 is : "<read(0)<

cout<<"Node at position 1 is : "<read(1)<

cout<<"Node at position 2 is : "<read(2)<

return 0;

}

---------------------------------------------------------

// File: List.h // Desc: Linked List ADT interface // -------------------------------------------------------- #ifndef LINKEDLIST_LIST_H #define LINKEDLIST_LIST_H const int LIST_HEAD = 0; const int LIST_TAIL = -1; class List { private: struct Node { int value; Node* next; }; Node* head; int size; public: List(); ~List(); int getSize(); bool isEmpty(); void insert(int value, int position=LIST_TAIL); int remove(int position=LIST_TAIL); int read(int position); void modify(int value, int position); }; #endif //LINKEDLIST_LIST_H

Step by Step Solution

There are 3 Steps involved in it

Step: 1

blur-text-image

Get Instant Access to Expert-Tailored Solutions

See step-by-step solutions with expert insights and AI powered tools for academic success

Step: 2

blur-text-image

Step: 3

blur-text-image

Ace Your Homework with AI

Get the answers you need in no time with our AI-driven, step-by-step assistance

Get Started

Recommended Textbook for

Modern Database Management

Authors: Jeffrey A. Hoffer Fred R. McFadden

9th Edition

ISBN: B01JXPZ7AK, 9780805360479

More Books

Students also viewed these Databases questions

Question

3. How frequently do the assessments occur?

Answered: 1 week ago