Help Please. I am trying to implement a double linked list in c++. This is what
ID: 3551224 • Letter: H
Question
Help Please. I am trying to implement a double linked list in c++. This is what I have so far. I have everything written out already but I'm running into problems with my removeTail function. If I take it out, everything else works fine. The person that can figure out my issue and correct will be awarded points.
#include<iostream>
using namespace std;
//our node
struct node
{
node * prev;
node * next;
char d;
};
//head and tail pointers
node * head = 0;
node * tail = 0;
//function declarations
void appendTail(char);
void appendHead(char);
char removeHead(void);
char removeTail(void);
int find(char);
void traverseFWD(void);
void traverseBWD(void);
int isempty(void);
void invert(void);
//main for testing the access functions
void main(void)
{
appendTail('A');
appendTail('B');
appendTail('C');
appendTail('D');
traverseFWD();
invert();
traverseFWD();
find('x');
find('D');
traverseFWD();
traverseBWD();
appendHead('E');
traverseFWD();
cout << "Removed Head: " << removeHead() << endl;
cout << "Removed Tail: " << removeTail() << endl;
appendHead('F');
appendTail('G');
traverseFWD();
//empty the list
cout << "Removed ";
while(!isempty())
cout << removeHead() << ", ";
cout << endl;
traverseFWD();
find('G');
//should really do a lot more testing than shown here.
}
//receives a char element and appends it to the tail of the list.
void appendTail(char d)
{
//make new node
node * p = new node;
p->next = 0;
p->prev = 0;
p->d=d;
if(isempty()) //list is empty
{
head = tail = p;
}
else //append to tail end
{
tail->next=p;
tail=p;
}
cout << "Append Tail: " << d << endl;
}
void appendHead(char d)
{
//make new node
node * p = new node;
p->next = head;
head = p;
head->d=d;
cout << "Append Head: " << d << endl;
}
//removes char element from tail of list and returns it
//returns -1 if list is empty
char removeTail(void)
{
node * p;
char temp;
//return if list is empty
if(isempty())
return -1;
//only one node?
if(tail==head)
{
//remove and destroy tail node
temp = tail->d;
delete tail;
tail = head = 0;
return temp;
}
//more than one node
//remove and destroy tail node
p = tail;
tail = tail->next;
temp = p->d;
delete p;
return temp;
}
//removes char element from head of list and returns it
//returns -1 if list is empty
char removeHead(void)
{
node * p;
char temp;
//return if list is empty
if(isempty())
return -1;
//only one node?
if(head==tail)
{
//remove and destroy head node
temp = head->d;
delete head;
head = tail = 0;
return temp;
}
//more than one node
//remove and destroy head node
p = head;
head = head->next;
temp = p->d;
delete p;
return temp;
}
//searches list for char element
//if char is found, removes char and returns 0
//otherwise returns -1
int find(char d)
{
node * c;
node * pc;
//empty?
if(!head)
{
cout << d << " not found" << endl;
return 0;
}
//only one node?
if(head==tail)
{
if(head->d==d)
{
//destroy node
delete head;
head = tail = 0;
cout << d << " found" << endl;
return 0;
}
else
{
cout << d << " not found" << endl;
return -1;
}
}
//two or more nodes
pc = head;
c = head->next;
if(pc->d==d) //found at head
{
head = head->next;
delete pc;
cout << d << " found" << endl;
return 0;
}
//look at node after head
while(c)
{
if(c->d==d) //found after head
{
pc->next = c->next;
//take care of tail
if(c == tail)
tail = pc;
//destroy node
delete c;
cout << d << " found" << endl;
return 0;
}
pc = c;
c = c->next;
}
cout << d << " not found" << endl;
return -1;
}
//traverses the list from head to tail
void traverseFWD(void)
{
node*p=head;
cout << "The list (Head to tail) contains: ";
while(p)
{
cout << (char)p->d<< " ";
p=p->next;
}
cout << endl;
}
//traverses the list from tail to head
void traverseBWD(void)
{
node*p=tail;
cout << "The list (Tail to head) contains: ";
while(p)
{
cout << (char)p->d<< " ";
p=p->prev;
}
cout << endl;
}
//returns true if the list is empty, false otherwise
int isempty(void)
{
if(head)
return 0;
else
return 1;
}
//swaps head and tail
void invert(void)
{
int temp = head->d;
head->d = tail->d;
tail->d = temp;
cout << " Swapped head and tail" << endl;
}
Explanation / Answer
// 5 methods have problems:
// appendTail appendHead removeTail removeHead find
// fixed code:
#include<iostream>
using namespace std;
//our node
struct node
{
node * prev;
node * next;
char d;
};
//head and tail pointers
node * head = 0;
node * tail = 0;
//function declarations
void appendTail(char);
void appendHead(char);
char removeHead(void);
char removeTail(void);
int find(char);
void traverseFWD(void);
void traverseBWD(void);
int isempty(void);
void invert(void);
//main for testing the access functions
void main(void)
{
appendTail('A');
appendTail('B');
appendTail('C');
appendTail('D');
traverseFWD();
invert();
traverseFWD();
find('x');
find('D');
traverseFWD();
traverseBWD();
appendHead('E');
traverseFWD();
cout << "Removed Head: " << removeHead() << endl;
cout << "Removed Tail: " << removeTail() << endl;
appendHead('F');
appendTail('G');
traverseFWD();
//empty the list
cout << "Removed ";
while(!isempty())
cout << removeHead() << ", ";
cout << endl;
traverseFWD();
find('G');
//should really do a lot more testing than shown here.
}
//receives a char element and appends it to the tail of the list.
void appendTail(char d)
{
//make new node
node * p = new node;
p->next = 0;
p->prev = 0;
p->d=d;
if(isempty()) //list is empty
{
head = tail = p;
}
else //append to tail end
{
tail->next=p;
p->prev = tail;
tail=p;
}
cout << "Append Tail: " << d << endl;
}
void appendHead(char d)
{
//make new node
node * p = new node;
p->next = 0;
p->prev = 0;
p->d=d;
if(isempty()) //list is empty
{
head = tail = p;
}
else //append to head
{
p->next = head;
head->prev = p;
head = p;
}
cout << "Append Head: " << d << endl;
}
//removes char element from tail of list and returns it
//returns -1 if list is empty
char removeTail(void)
{
node * p;
char temp;
//return if list is empty
if(isempty())
return -1;
//only one node?
if(tail==head)
{
//remove and destroy tail node
temp = tail->d;
delete tail;
tail = head = 0;
return temp;
}
//more than one node
//remove and destroy tail node
p = tail;
tail = tail->prev;
tail->next = 0;
temp = p->d;
delete p;
return temp;
}
//removes char element from head of list and returns it
//returns -1 if list is empty
char removeHead(void)
{
node * p;
char temp;
//return if list is empty
if(isempty())
return -1;
//only one node?
if(head==tail)
{
//remove and destroy head node
temp = head->d;
delete head;
head = tail = 0;
return temp;
}
//more than one node
//remove and destroy head node
p = head;
head = head->next;
head->prev = 0;
temp = p->d;
delete p;
return temp;
}
//searches list for char element
//if char is found, removes char and returns 0
//otherwise returns -1
int find(char d)
{
node * c;
node * pc;
//empty?
if(!head)
{
cout << d << " not found" << endl;
return 0;
}
//only one node?
if(head==tail)
{
if(head->d==d)
{
//destroy node
delete head;
head = tail = 0;
cout << d << " found" << endl;
return 0;
}
else
{
cout << d << " not found" << endl;
return -1;
}
}
//two or more nodes
pc = head;
c = head->next;
if(pc->d==d) //found at head
{
head = head->next;
head->prev = 0;
delete pc;
cout << d << " found" << endl;
return 0;
}
//look at node after head
while(c)
{
if(c->d==d) //found after head
{
pc->next = c->next;
if (pc->next)
pc->next->prev = pc;
//take care of tail
if(c == tail)
tail = pc;
//destroy node
delete c;
cout << d << " found" << endl;
return 0;
}
pc = c;
c = c->next;
}
cout << d << " not found" << endl;
return -1;
}
//traverses the list from head to tail
void traverseFWD(void)
{
node*p=head;
cout << "The list (Head to tail) contains: ";
while(p)
{
cout << (char)p->d<< " ";
p=p->next;
}
cout << endl;
}
//traverses the list from tail to head
void traverseBWD(void)
{
node*p=tail;
cout << "The list (Tail to head) contains: ";
while(p)
{
cout << (char)p->d<< " ";
p=p->prev;
}
cout << endl;
}
//returns true if the list is empty, false otherwise
int isempty(void)
{
if(head)
return 0;
else
return 1;
}
//swaps head and tail
void invert(void)
{
int temp = head->d;
head->d = tail->d;
tail->d = temp;
cout << " Swapped head and tail" << endl;
}
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.