//=============================================================================
// dllist.h
// A doubly linked list class.
// Stores non-negative integers. (Making it easy to pass "-1" back from a
// function to indicate an error. Lazy, but effective.)
// contains head and tail pointers, and implements various operations.
//
// Written by Chuck Cusack, Feb 2001.
// Revised April 2002.
//=============================================================================
#ifndef DLLIST
#define DLLIST
#include<cstdlib>
#include<iostream>
using namespace std;
//=============================================================================
// Each item in the linked list is a node, which contains a key (the value we
// care about), and previous and next pointers.
//
struct node {
int key; // The value of interest in the node
node *next; // A pointer to the previous node in the list
node *previous; // A pointer to the next node in the list
};
//=============================================================================
class dllist {
public:
//---------------------------------------------------------
// The default constructor: Create an empty linked list
//
dllist();
//---------------------------------------------------------
// The destructor: Delete the linked list. Specifically,
// delete all of the nodes currently on the list
//
~dllist();
//---------------------------------------------------------
// The copy constructor. Implements a "deep" copy. That is,
// copies all of the nodes in originalList to the new list.
//
dllist(const dllist& originalList);
//---------------------------------------------------------
// The overloaded assign operator. Implements a "deep" copy.
// That is, copies all of the nodes in originalList to the
// new list.
//
dllist& operator=(const dllist & originalList);
//---------------------------------------------------------
// Insert a new item at the head of the list, containing a
// key with value K
//
void InsertAtHead(int K);
//---------------------------------------------------------
// Insert a new item at the tail of the list, containing a
// key with value K
//
void InsertAtTail(int K);
//---------------------------------------------------------
// Search for an item on the list with value K.
// Return true (1) if it is, false (0) if it is not.
//
bool Find(int K);
//---------------------------------------------------------
// Delete the value K from the linked list.
// Return true (1) if the key is on the list and was deleted,
// and false (0) if it is not on the list (and therefore was
// not deleted).
// Precondition: The list is not empty
//
bool Delete(int K);
//---------------------------------------------------------
// Delete the first item from the list.
// Return the value of the head if the list is not empty,
// and -1 if the list is empty.
// Precondition: The list is not empty
//
int DeleteFromHead();
//---------------------------------------------------------
// Delete the last item from the list.
// Return the value of the tail if the list is not empty,
// and -1 if the list is empty.
// Precondition: The list is not empty
//
int DeleteFromTail();
//---------------------------------------------------------
// Delete all items from the list.
void Purge();
//---------------------------------------------------------
// Return the value of the first item on the list. If the
// list is empty, return -1.
int getHead() const;
//---------------------------------------------------------
// Return the value of the last item on the list. If the
// list is empty, return -1.
//
int getTail() const;
//---------------------------------------------------------
// Return true (1) if the list is empty, and false (0) if
// the list is not empty.
//
bool isEmpty() const;
//---------------------------------------------------------
// The overloaded >> operator. Used to read in a doubly
// linked list from a stream (cin, or a file stream).
// Assumes the list is stored by specifying the elements on
// the list from head to tail.
// Example: if the linked list is:
// head->12->3->123->34->4->null
// then the file contains:
// 12 3 123 34 4
//
// --Not actually a class method, but a friend--
//
friend istream &operator>>(istream &thestream, dllist& theList);
//---------------------------------------------------------
// The overloaded << operator. Used to write a doubly linked
// list to a stream. Writes each element from head to tail.
// See the '>>' operator above for an example.
//
// --Not actually a class method, but a friend--
//
friend ostream &operator<<(ostream &thestream, const dllist theList);
//-----------------------------------------------------------------------------
private: // The data
node *head; // Points to the first item on the linked list
node *tail; // Points to the last item on the linked list
};
#endif
//=============================================================================