Modify our Doubly Linked List code to include following index (rank) based acces

Question

Modify our Doubly Linked List code to include following index (rank) based access operations

int RetrieveAt(int index)
void DeleteAt(int index)

void Swap(int index, int index)

index starts at 0 (just like array's subscript)
If the index is out of bound, RetrieveAt returns -999, DeleteAt does nothing, do nothing in Swap.

Write your own testing program to test the modified class

__________________________________________________________________DLinkeList.h_________________________________________________________

____________________________________________________________________________________________________________________________________

____________________________________________________________________DLinkedList.cpp____________________________________________________

____________________________________________________________________________________________________________________________________

Explanation / Answer

CODE

#ifndef DLINKEDLIST_H
#define DLINKEDLIST_H

class Node
{
private:
int data;
Node *next;
Node *prev;
public:
Node();
int GetData();
friend class DLinkedList;
};

class DLinkedList
{
private:
int length;
Node *currentPos;
Node *head;
Node *tail;
public:
DLinkedList();
~DLinkedList();
int LengthIs();
void MakeEmpty();
void AddToTail(int);
void AddToHead(int);
int SearchRank(int);
void DeleteFromHead();
void DeleteFromTail();
void Delete(int);
Node GetNext();
bool IsLast();
void Reset();
void PrintAll();
int RetrieveAt(int);
void DeleteAt(int);
void Swap(int,int);

};

#endif

DLinkedList.cpp

#include "DLinkedList.h"
#include <iostream>
using namespace std;

Node::Node()
{
next = 0;
prev = 0;
}

int Node::GetData()
{
return data;
}

DLinkedList::DLinkedList()
{
length = 0;
head = 0;
tail = 0;
currentPos = 0;
}

int DLinkedList::LengthIs()
{
return length;
}

void DLinkedList::MakeEmpty()
{
Node *ptr = head;
Node *ptr2;
for(int i=0;i<length;i++)
{
ptr2 = ptr->next;
delete ptr;
ptr = ptr2;
}

length = 0;
head = tail = currentPos = 0;
}

void DLinkedList::AddToTail(int item)
{
Node *ptr=new Node();
ptr->data = item;
if(length==0)
{
tail = ptr;
head = ptr;
length++;
return;
}
tail->next = ptr;
ptr->prev = tail;
tail = ptr;
length++;

}

void DLinkedList::AddToHead(int item)
{
Node *ptr = new Node;
ptr->data = item;
ptr->next = head;
head = ptr;
if(length==0) tail = ptr;
else head->next->prev = head;
length++;
}

int DLinkedList::SearchRank(int value)
{
int rank = 0;
Node *current = head;
while(current)
{
if(current->data == value) return rank;
rank++;
current = current->next;
}
return -1;
}

void DLinkedList::DeleteFromHead()
{
if(length == 0) return;
Node *ptr = head->next;
if(currentPos==head) currentPos = 0;
delete head;
head = ptr;
length--;
if(length == 0) tail = 0;
if(head) head->prev = 0;
}

void DLinkedList::DeleteFromTail()
{
if(length==0) return;
else if (length==1)
{
delete head;
head = tail =currentPos = 0;
length--;
return;
}
Node *current = tail->prev;

tail = current;
if(currentPos == current->next) currentPos = 0;
delete current->next;
current->next = 0;
length--;
return;
}

bool DLinkedList::IsLast()
{
if(currentPos==tail) return 1;
else return 0;
}

void DLinkedList::Reset()
{
currentPos = 0;
}

Node DLinkedList::GetNext()
{
Node temp;
if(currentPos==0)
{
if(head) temp.data = head->data;
else temp.data = -1;
currentPos = head;
}
else
{
if(currentPos->next!=0)
{
temp.data = currentPos->next->data;
currentPos=currentPos->next;
}
else temp.data = -1;
}
return temp;
}

DLinkedList::~DLinkedList()
{
MakeEmpty();

}

void DLinkedList::PrintAll()
{
Node *current = head;
while(current)
{
cout<<current->data<<endl;
current = current->next;
}
}

int DLinkedList::RetrieveAt(int index)
{
Node *current = head;
int count = 0;
int retVal = -999;
if(index<0 || index>length-1)
return retVal;
while(current)
{
if(count==index)
{
retVal = current->data;
break;
}
current = current->next;
count++;
}
return retVal;
}

void DLinkedList::DeleteAt(int index)
{
if(length == 0) return;
if(index<0 || index>length-1)
return;
if(index==0)
{
DeleteFromHead();
return;
}
if(index==length-1)
{
DeleteFromTail();
return;
}
Node *current=head->next;
int currentIndex=1;
while(current)
{
if(currentIndex==index)
{
length--;
current->prev->next = current->next;
current->next->prev = current->prev;
if(currentPos==current) currentPos=0;
delete current;
return;
}
current = current->next;
currentIndex++;
}
}

void DLinkedList::Swap(int ind1, int ind2)
{
if(ind1<0 || ind1>length-1)
return;
if(ind2<0 || ind2>length-1)
return;

Node *current = head;
Node *current1, *current2;
bool flag1 = false, flag2 = false;
int count = 0;

while(current && (!flag1 || !flag2))
{
if(count == ind1)
{
flag1 = true;
current1 = current;
}
if(count == ind2)
{
flag2 = true;
current2 = current;
}
current = current->next;
count++;
}

int temp = current1->data;
current1->data = current2->data;
current2->data = temp;
}

DLinkedListProg.cpp

#include "DLinkedList.h"

#include <iostream>

using namespace std;

int main()
{
DLinkedList myList;
for(int i=0;i<20;i++) myList.AddToTail(i);

cout<<myList.RetrieveAt(0)<<endl;
cout<<myList.RetrieveAt(19)<<endl;

myList.DeleteAt(0);

cout<<myList.RetrieveAt(12)<<endl;

myList.DeleteAt(18);
myList.DeleteAt(12);
myList.DeleteAt(12);

while(!myList.IsLast()) cout<<myList.GetNext().GetData()<<" ";
cout<<endl;

myList.Reset();
myList.Swap(0,15);

while(!myList.IsLast()) cout<<myList.GetNext().GetData()<<" ";
cout<<endl;

myList.Reset();
myList.Swap(3,10);

while(!myList.IsLast()) cout<<myList.GetNext().GetData()<<" ";
cout<<endl;
}

IF ANY QUERIES REGARDING CODE AND EXECUTION PLEASE GET BACK TO ME
THANK YOU

Related Questions

Navigate

• Browse (All)
• Browse M
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.