Question #27337

Data Structures and Algorithm

Implement linkedlist for integers; following methods should be implemented.

void insertAtPosition(int x,int pos); //insert value x at given position

void insertAtEnd(int x); //insert value at the end of the list

void insertAtFront(int x); //insert value at the first position of the list

void removeFromFront(); //remove element from first position

void removeFromEnd(); //remove element from the end of the list

void removeFromPosition(int pos); //remove element from the position given by user. After the //operation there should be no gap in the elements of list

node* find(int x) const; //return the address

int findPosition(int pos) const; //find at given position and return the value

bool IsEmpty() const; //return true if list is empty

void print() const; //print the whole list

Note: Implement the main() to show that all above given methods are working properly

Implement linkedlist for integers; following methods should be implemented.

void insertAtPosition(int x,int pos); //insert value x at given position

void insertAtEnd(int x); //insert value at the end of the list

void insertAtFront(int x); //insert value at the first position of the list

void removeFromFront(); //remove element from first position

void removeFromEnd(); //remove element from the end of the list

void removeFromPosition(int pos); //remove element from the position given by user. After the //operation there should be no gap in the elements of list

node* find(int x) const; //return the address

int findPosition(int pos) const; //find at given position and return the value

bool IsEmpty() const; //return true if list is empty

void print() const; //print the whole list

Note: Implement the main() to show that all above given methods are working properly

Expert's answer

/*

***********************

& The methods of the list

& is defined in the file

***********************

*/

#include "List.h" &

#include <iostream>

using namespace std;

Node::Node(int value){

m_value = value; &

next = NULL;

prev = NULL;

}

Node::~Node(){

}

int Node::GetValue(){

return m_value;

}

List::List(){

head = NULL;

tail = NULL;

count = 0;

}

List::~List(){

RemoveAll();

}

void List::InsertAtEnd(int x){

//create an instance of Node class

Node* node = new Node(x);

if(IsEmpty()) //if the list is empty

{

tail = node;

head = tail;

}

else //if the list is not empty

{

tail->next = node;

node->prev = tail;

tail = node;

}

count++; //increase size of the list

}

void List::InsertAtFront(int x){

//create an instance of Node class

Node* node = new Node(x);

if(IsEmpty()) & //if the list is empty

{

head = node;

tail = head;

}

else //if the list is not empty

{

head->prev = node;

node->next = head;

head = node;

}

count++;

}

void List::InsertAtPosition(int x, int pos){

&

& if(pos >= 0 && pos <= count - 1) //if pos is not less 0 and not more size of the list

& {

if(IsEmpty()|| pos == 0) //if list is empty or pos is 0 to insert x at the front of the list

InsertAtFront(x);

else

{

if(pos == count - 1) //if pos is count - 1 to insert x at the end of the list

InsertAtEnd(x);

else

{

Node* node = new Node(x);

Node* temp = head;

int i = 0;

while(i != pos){ //finding an element of the list

temp = temp->next;

i++;

}

& temp->prev->next = node; &

& node->prev = temp->prev;

& node->next = temp;

& temp->prev = node;

&

& count++;

}

}

& }

& else{

cout << endl << "Incorrect value of the position";

& }

}

void List::RemoveFromEnd(){

if(!IsEmpty()){

& //if the list is not empty

if(count > 1 && tail != NULL){ & //if the list has got more than one element

Node* temp = tail;

temp->prev->next = NULL;

tail = temp->prev;

delete temp;

count--;

& }

else if(count == 1 && tail != NULL) & //if the list has got one element

{

head = tail = NULL;

count--;

}

}

}

void List::RemoveFromFront(){

if(!IsEmpty()){ & //if the list is not empty

if(count > 1 && head != NULL){ //if the list has got more than one element

Node* temp = head;

head->next->prev = NULL;

head = temp->next;

delete temp;

count--;

& }

else if(count == 1 && head != NULL) & //if the list has got only one element

{

head = tail = NULL;

count--;

}

}

}

void List::RemoveFromPosition(int pos){

if(!IsEmpty()){ & //if the list is not empty

if(pos >=0 && pos <= count - 1){ & //if pos is not less 0 and pos is not more size of the list

if(pos == 0){ & //if the first element needs removing

RemoveFromFront();

}

else if(pos == count - 1) & //if the last element needs removing

{

RemoveFromEnd();

}

else & //if pos is not the first or the last element

{

Node* temp = head;

int i = 0;

while(i != pos)

{

temp = temp->next;

i++;

}

temp->next->prev = temp->prev;

temp->prev->next = temp->next;

delete temp;

count--;

}

}

else

cout << endl << "Incorrect position!";

}

}

void List::RemoveAll(){

& while(count != 0) &

& RemoveFromPosition();

}

bool List::IsEmpty() const

{ &

if(count == 0) //if size of the list is 0 to return true

return true;

else

return false; //if size of the list is not 0 to return false

}

int List::FindPosition(int x) const

{ &

if(!IsEmpty()){ //if the list is not empty

int i = 0;

Node* temp = head;

while(temp->next != NULL){ //finding an element to return it

if(temp->GetValue() == x) return i;

temp = temp ->next;

i++;

}

if(temp->GetValue() == x) return count - 1; & //if the element is the last element of the list

else

& return -1; //if such element do not exist

}

}

Node* List::Find(int x) const{

if(!IsEmpty()) & //if the list is not empty

{

Node* temp = head;

while(temp->next != NULL){

if(temp->GetValue() == x) return temp; &

temp = temp ->next;

}

if(temp->GetValue() == x) return temp;

else

& return NULL;

}

}

void List::Print() const{

if(!IsEmpty()){ //if the list is not empty

& &

Node* temp = head;

while(temp ->next != NULL){

cout << temp->GetValue() << ",";

temp = temp ->next;

}

cout << temp ->GetValue();

}

}

#include <iostream>

#include "List.h"

using namespace std;

int main(){

List* list = new List();

list->InsertAtEnd(4);

list->InsertAtFront(10);

list->InsertAtFront(3);

list->InsertAtPosition(5, 1);

list->InsertAtPosition(14, 2);

list->InsertAtPosition(13, 1);

list->Print();

list->RemoveFromEnd();

cout <<endl;

list->Print();

list->RemoveFromPosition(3);

list->RemoveFromPosition(4);

cout << endl;

list->Print();

list->RemoveFromFront();

cout << endl;

list->Print();

cout << endl;

cout << list->Find(10);

cout << endl;

cout << list->FindPosition(10);

list->RemoveFromEnd();

list->RemoveFromEnd();

list->RemoveFromEnd();

list->RemoveFromFront();

list->RemoveFromFront();

list->FindPosition(10);

list->Find(10);

delete list;

return 0;

}

Learn more about our help with Assignments: C++

## Comments

## Leave a comment