#include<iostream>
using namespace std;
//NODE
class Node{
public:
int data;
Node* prev;
Node* next;
//constructors
Node(){
data=0;
prev=NULL;
next=NULL;
}
Node(int d){
data=d;
prev=NULL;
next=NULL;
}
};
//Doubly Linkedlist
class DoublyLinkedList{
Node* head;
Node* tail;
public:
DoublyLinkedList(){
head=tail=NULL;
}
//METHODS
void insertAtHead(int d);
void deleteFromTail();
void display();
void insertAtTail(int d);
bool deleteFromHead();
int findTheMiddle();
void isPalindrome();
};
//Display
void DoublyLinkedList::display(){
Node* temp=head;
while(temp!=NULL){
cout<<temp->data<<"\t";
temp=temp->next;
}
}
//Insert At Head
void DoublyLinkedList::insertAtHead(int d){
Node*temp= new Node(d);
if(head==NULL){ //if doublyLinkedList is empty
head=tail=temp;
temp->next=temp->prev=NULL;
}
else{
temp->next=head;
head->prev=temp;
temp->prev=NULL;
head=temp;
}
}
//Delete From Tail
void DoublyLinkedList::deleteFromTail(){
if(head==NULL)
cout<<"Task Failed, List is empty"<<endl;
Node* temp=tail->prev;
delete tail;
tail=temp;
temp->next=NULL;
}
//Insert At Tail
void DoublyLinkedList::insertAtTail(int d){
Node* temp= new Node(d);
if(tail==NULL){
head=tail=temp;
temp->next=temp->prev=NULL;
}
else{
tail->next=temp;
temp->prev=tail;
tail=temp;
temp->next=NULL;
}
}
//Delete From Head
bool DoublyLinkedList::deleteFromHead(){
if(head==NULL)
cout<<"Task Failed, list is empty."<<endl;
head=head->next;
delete head->prev;
head->prev=NULL;
}
//Find the Middle
int DoublyLinkedList::findTheMiddle(){
int n=1;
if(head==NULL)
cout<<"List is empty, operation failed"<<endl;
Node* temp1 =head;
Node* temp2 =head;
while(temp2->next->next!=NULL){
n++;
temp1=temp1->next;
temp2=temp2->next->next;
}
return n;
}
//isPalindrome
void DoublyLinkedList::isPalindrome(){
//if list is ODD, we want to stop our loop when HEAD==TAIL.
//if list is EVEN, there will never be a moment when HEAD==TAIL. SO when head->prev==tail, we want our loop to stop.
while(head!=tail && head->prev!=tail){
//with each step, we want to look whether head->data==tail->data. if NOT then RETURN, if YES then CONTINUE
if(head->data==tail->data){
head=head->next;
tail=tail->prev;
}
else
{
cout<<"Not a Palindrome"<<endl;
return;
}
}
//if our list is EVEN, we will enter into the following IF statement.
if(head->prev==tail){
//an EVEN list will be a palindrome if the middle two integers are equal.
if(head->data==tail->data){
cout<<"Your list is a Palindrome"<<endl;
return;
}
}
//Now that compiler has looked at all lines before. list is now definitely a palindrome.
cout<<"Your list is a Palindrome"<<endl;
}
//MAIN
int main(){
DoublyLinkedList list;
list.insertAtTail(5);
list.insertAtTail(6);
list.insertAtTail(7);
// list.insertAtTail(7);
list.insertAtTail(0);
list.insertAtTail(5);
list.display();
cout<<endl;
list.isPalindrome();
}
Comments
Post a Comment