//-----------------------------------------------------------------------------
// dllist.cpp
//
// Written by Chuck Cusack, Feb 2001.
// Revised April 2002.
//-----------------------------------------------------------------------------
// Not all details are given here.
//
// In order to run the sample program and use this class with the various
// Stacks and Queues, you will need to finish implementing at least:
//
// InsertAtHead
//
// The other methods are needed to complete this class, but are not used in
// this context.
//-----------------------------------------------------------------------------
#include "dllist.h"
//-----------------------------------------------------------------------------
dllist::dllist() {
head=NULL; // An empty list has head==tail==NULL
tail=NULL; // This assumes you are NOT using dummy nodes.
}
//-----------------------------------------------------------------------------
dllist::~dllist () {
Purge(); // See Purge() for details
}
//-----------------------------------------------------------------------------
dllist::dllist(const dllist& originalList) {
//
// NOT IMPLEMENTED YET
//
// Copy the linked list
// This probably needs to be done node by node
}
//-----------------------------------------------------------------------------
dllist& dllist::operator=(const dllist & originalList) {
//
// NOT IMPLEMENTED FULLY YET
//
if(&originalList!=this) {
// Delete current linked list stuff
// Copy the linked list
}
return *this;
}
//-----------------------------------------------------------------------------
// InsertAtTail: Insert a new node at the tail of the list
//
void dllist::InsertAtTail(int K) {
node *P=new node; // Create the new node
P->key=K; // Set the key of the new node
P->next=NULL; // Set the next to NULL, since it is at tail
if(isEmpty()) // Case 1: The list is empty
{
head=P; // This node is head and tail
tail=P;
P->previous=NULL; // Since it is head, set previous to NULL as well
}
else // Case 2: The list is not empty
{
tail->next=P; // The tail's next now points to the new node
P->previous=tail; // The new node's previous points to the current tail
tail=P; // The new node becomes the tail
}
}
//-----------------------------------------------------------------------------
void dllist::InsertAtHead(int K) {
//
// NOT IMPLEMENTED FULLY YET
//
}
//-----------------------------------------------------------------------------
bool dllist::Find(int K) {
//
// NOT IMPLEMENTED FULLY YET
//
}
//-----------------------------------------------------------------------------
bool dllist::Delete(int K) { // Start by finding the node, if it exists
node *T=head; // Start looking at the head
while(T!=NULL && T->key!=K) // While we haven't reached the end and
// haven't found the item we are looking for
T=T->next; // continue with the next node
if(T!=NULL) // If the item was found, we will proceed to delete it
{
if(T==head) // Case 1: The node is the head
DeleteFromHead();
else if(T==tail) // Case 2: The node is the tail
DeleteFromTail();
else // Case 3: The node is internal
{
T->previous->next=T->next; // Bypass the node forward
T->next->previous=T->previous; // Bypass the node backward
delete T; // Delete the node
}
return true; // Since we deleted the node, return successful
}
else
return false; // Since it wasn't found, return unsuccessful
}
//-----------------------------------------------------------------------------
int dllist::DeleteFromHead() {
if(!isEmpty()) // As long as there is a node...
{
int x=head->key; // Save the key value so it can be returned
node *T=head; // Save a pointer to the node
head=head->next; // Move the head forward by one
delete T; // Delete the old head
if (head == NULL) // If the list is empty
tail = NULL; // Set tail to NULL as well
else // If the list is not empty
head->previous=NULL; // The new head's previous should be NULL
return x; // Return the key from the head
}
else // If there are no nodes...
return -1; // Return an invalid number
}
//-----------------------------------------------------------------------------
int dllist::DeleteFromTail() {
//
// NOT IMPLEMENTED FULLY YET
//
}
//-----------------------------------------------------------------------------
int dllist::getHead() const {
if(!isEmpty()) // As long as the list is not empty
return head->key; // Return the key from the head
else // But if the list is empty
return -1; // Return an invalid number
}
//-----------------------------------------------------------------------------
int dllist::getTail() const {
//
// NOT IMPLEMENTED FULLY YET
//
}
//-----------------------------------------------------------------------------
void dllist::Purge() {
while(!isEmpty()) // As long as there are still nodes in the list
DeleteFromHead(); // Delete the head node
head=NULL; // Set the head and tail to NULL, indicating empty list
tail=NULL;
}
//-----------------------------------------------------------------------------
bool dllist::isEmpty() const {
return (head==NULL); // Clearly if head==NULL, the list is empty
}
//-----------------------------------------------------------------------------
istream &operator>>(istream &thestream, dllist& theList) {
//
// NOT IMPLEMENTED YET
//
// Read from the stream and store the items on theList.
// NOTE: If the list is not empty, it should be emptied first.
return thestream;
}
//-----------------------------------------------------------------------------
ostream &operator<<(ostream &thestream, const dllist theList) {
//
// NOT IMPLEMENTED YET
//
// Write out the elements in the list to the stream.
return thestream;
}
//-----------------------------------------------------------------------------