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

-----------------------------------------------------------------------------------------------------------------------------------------------------------------------------------DLinklist.h-----------------------------

------------------------------------------------------------------------------------------DlinkedList.cpp---------------------------------------------------------------------------------------------

----------------------------------------------------------------------------------------------------------------DlinkedListprog.cpp-----------------------------------------------------------------------------------

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

Explanation / Answer

The Doubly linked list code has been modified as specified. A sample testing program has been written to check the added functions.

Please rate my answer if you find it useful.

----------DLinkedList.h----------

#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;
}

Related Questions

Navigate

• Browse (All)
• Browse M
• Subjects

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