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
1
Expert's answer
2013-03-29T07:01:19-0400
/* *********************** & 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++; }
& } & 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!"; } }
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;
Comments
Leave a comment