Description: The Homework page contains a partial implementation of a linked lis

Question

Description: The Homework page contains a partial implementation of a linked list class, NodeSLList. (I commended out each sections, lengthy, but explains well)

NodeSLList.h

///////////////////////////////////////////////////////////////////////

// Class NodeSLList Interface

//

// Description - This is the interface for a class which implements

//               a singly linked list of integers. Each node in the

//               linked list is IntNode object, defined by the IntNode

//               class.

///////////////////////////////////////////////////////////////////////

#ifndef INT_LINKED_LIST

#define INT_LINKED_LIST

#include <iostream>

using std::ostream;

using std::cout;

using std::cin;

using std::endl;

struct IntNode

{

              int data;

              IntNode * next;

};

// Class NodeSLList Declaration

class NodeSLList {

              friend ostream & operator<<(ostream &, NodeSLList &);

public:

///////////////////////////////////////////////////////////////////////

// default constructor

//

// Description: initialize list

// Input: none

// Output: none

// Returns: none

///////////////////////////////////////////////////////////////////////

              NodeSLList();

///////////////////////////////////////////////////////////////////////

// copy constructor

//

// Description: initialize list from another list

// Input: none

// Output: none

// Returns: none

///////////////////////////////////////////////////////////////////////

              NodeSLList(NodeSLList &);

///////////////////////////////////////////////////////////////////////

// destructor

//

// Description: deallocates all memory for linked list by calling

//              destroyList() member function

// Input: none

// Output: none

// Returns: none

///////////////////////////////////////////////////////////////////////

              ~NodeSLList();

///////////////////////////////////////////////////////////////////////

// IsEmpty

//

// Description: returns status of array

// Input: none

// Returns: TRUE if list is empty

//          FALSE otherwise

///////////////////////////////////////////////////////////////////////

              bool IsEmpty();

///////////////////////////////////////////////////////////////////////

// GetSize

//

// Description: get current number of nodes in list

// Input: none

// Output: none

// Returns: number of nodes in list

///////////////////////////////////////////////////////////////////////

              int GetSize();

///////////////////////////////////////////////////////////////////////

// AddToHead

//

// Description: add a node to the head of the list

// Input: data for node to be added

// Output: none

// Returns: none

///////////////////////////////////////////////////////////////////////

              void AddToHead(const IntNode & node);

///////////////////////////////////////////////////////////////////////

// DeleteFromHead

//

// Description: remove a node from the head of the list

// Input: none

// Output: none

// Returns: data that was at the node just removed

///////////////////////////////////////////////////////////////////////

              IntNode DeleteFromHead();

///////////////////////////////////////////////////////////////////////

// AddToTail

//

// Description: add a node to the tail of the list

// Input: data for node to be added

// Output: none

// Returns: none

///////////////////////////////////////////////////////////////////////

              void AddToTail(const IntNode & node);

///////////////////////////////////////////////////////////////////////

// DeleteFromTail

//

// Description: remove a node from the tail of the list

// Input: none

// Output: none

// Returns: data that was at the node just removed

///////////////////////////////////////////////////////////////////////

              IntNode DeleteFromTail();

///////////////////////////////////////////////////////////////////////

// DeleteNode

//

// Description: remove a node from the list

// Input: node number to be removed

// Output: none

// Returns: data that was at the node just removed

///////////////////////////////////////////////////////////////////////

              IntNode DeleteNode(int nodeNum);

///////////////////////////////////////////////////////////////////////

// InsertNode

//

// Description: inserts a node in the list

// Input: node number after which a node is to be inserted

//        node data to be inserted

// Output: none

// Returns: data that was at the node just removed

///////////////////////////////////////////////////////////////////////

              void InsertNode(int nodeNum, const IntNode &node);

///////////////////////////////////////////////////////////////////////

// UpdateNode

//

// Description: update a node's data

// Input: node number (1-N; not 0-(N-1))

// Output: none

// Returns: none

///////////////////////////////////////////////////////////////////////

              void UpdateNode(int nodeNum, const IntNode &node);

///////////////////////////////////////////////////////////////////////

// SortList

//

// Description: sorts list

// Input: order (1=ascending, 2=descending)

// Output: none

// Returns: none

///////////////////////////////////////////////////////////////////////

              void SortList(unsigned int order);

///////////////////////////////////////////////////////////////////////

// DestroyList

//

// Description: deallocates all memory for linked list

// Input: none

// Output: none

// Returns: none

///////////////////////////////////////////////////////////////////////

              void DestroyList();

///////////////////////////////////////////////////////////////////////

// operator=

//

// Description: assignment operator

// Input: reference to NodeSLList object to be assigned

// Output: none

// Returns: NodeSLList object that has been assigned

///////////////////////////////////////////////////////////////////////

              NodeSLList & operator=(NodeSLList &);

///////////////////////////////////////////////////////////////////////

// operator==

//

// Description: equality operator

// Input: reference to NodeSLList object to test equality with

// Output: none

// Returns: true if equal, false if not

///////////////////////////////////////////////////////////////////////

              bool operator==(NodeSLList &);

///////////////////////////////////////////////////////////////////////

// operator!=

//

// Description: inequality operator

// Input: reference to NodeSLList object to test inequality with

// Output: none

// Returns: true if not equal, false if equal

///////////////////////////////////////////////////////////////////////

              bool operator!=(NodeSLList &);

///////////////////////////////////////////////////////////////////////

// operator+

//

// Description: addition operator

// Input: reference to NodeSLList object to append to this one

// Output: none

// Returns: NodeSLList object that is the result of the addition operator

///////////////////////////////////////////////////////////////////////

              NodeSLList operator+(NodeSLList &);

             

private:

              IntNode *head, *tail;

              IntNode &RetrieveNode(int nodeNum) const; //helper function

                                                        //nodeNum is

};

#endif INT_LINKED_LIST

NodeSLList.cpp

///////////////////////////////////////////////////////////////////////

// Class NodeSLList Implementation

//

// Description - This file implements a singly linked list.

///////////////////////////////////////////////////////////////////////

#include "NodeSLList.h"

///////////////////////////////////////////////////////////////////////

// default constructor

///////////////////////////////////////////////////////////////////////

NodeSLList::NodeSLList()

{

              head = tail = 0;

}

///////////////////////////////////////////////////////////////////////

// copy constructor

///////////////////////////////////////////////////////////////////////

NodeSLList::NodeSLList(NodeSLList & list)

{

}

///////////////////////////////////////////////////////////////////////

// destructor

///////////////////////////////////////////////////////////////////////

NodeSLList::~NodeSLList()

{

              // call destroyList() to remove all nodes

              // and reset linked list

              DestroyList();

}

///////////////////////////////////////////////////////////////////////

// IsEmpty

///////////////////////////////////////////////////////////////////////

bool NodeSLList::IsEmpty()

{

              // if head is NULL, then the list is empty, and we will return true

              // otherwise, we will return false

              return (head == 0);

}

///////////////////////////////////////////////////////////////////////

// GetSize

///////////////////////////////////////////////////////////////////////

int NodeSLList::GetSize()

{

              // check to see if the list is empty. if

              // so, just return 0

              if ( IsEmpty() ) return 0;

              int size = 1;

              IntNode *p = head;

              // compute the number of nodes and return

              while (p != tail)

              {

                             // until we reach the tail, keep counting

                             size++;

                             p = p->next;

              }

              return size;

}

///////////////////////////////////////////////////////////////////////

// AddToHead

///////////////////////////////////////////////////////////////////////

void NodeSLList::AddToHead(const IntNode & node)

{

              // create a new node, and make it the head. the

              // previous head will become head->next

              IntNode * next = head;

              head = new IntNode;

              head->next = next;

              head->data = node.data;

              // if this is the first node, make the tail the

              // same as the head

              if (tail == 0)

                             tail = head;

}

///////////////////////////////////////////////////////////////////////

// DeleteFromHead

///////////////////////////////////////////////////////////////////////

IntNode NodeSLList::DeleteFromHead()

{

              IntNode temp;

              temp.data=0;

              temp.next=NULL;

              if (IsEmpty())

              {

                             cout << "*****ERROR: Can't delete from head. List is Empty" << endl;

                             return temp;

              }

              // get current value of node we are about to delete,

              // so we can return it.

              temp.data = head->data;

              IntNode *tmp = head;

              // if there is only one node, set the head and pointer tails

              // to NULL (0)

              if (head == tail)

                             head = tail = 0;

              // otherwise, move the head pointer to the next node

              // in the list

              else

                             head = head->next;

              // delete head node

              delete tmp;

              // return value of node that was deleted

              return temp;

}

///////////////////////////////////////////////////////////////////////

// AddToTail

///////////////////////////////////////////////////////////////////////

void NodeSLList::AddToTail(const IntNode & node)

{

}

///////////////////////////////////////////////////////////////////////

// DeleteFromTail

///////////////////////////////////////////////////////////////////////

IntNode NodeSLList::DeleteFromTail()

{

              IntNode nodeData;

              // get the current data at the tail

              nodeData.data = tail->data;

              // if there is only one node, delete the only node, and set the

              // head and tail pointers to NULL (0)

              if (head == tail)

              {

                             delete head;

                             head = tail =0;

              }

              // otherwise, traverse to the tail node and delete it

              else

              {

                             IntNode * temp;

                             // traverse to tail pointer

                             for (temp = head; temp->next != tail; temp = temp->next);

                             delete tail;

                             tail = temp;

                             tail->next = 0;

              }

              return nodeData;

}

///////////////////////////////////////////////////////////////////////

// DeleteNode

///////////////////////////////////////////////////////////////////////

IntNode NodeSLList::DeleteNode(int nodeNum)

{

              if (nodeNum <= 0) nodeNum = 1;

              IntNode *prev=head , *temp=head;

              IntNode current;

              // traverse to the node

              for (int loop=1; loop<nodeNum; loop++)

              {

                             prev=temp, temp=temp->next;

                             // check for case where nodeNum is > the number of

                             // nodes in the list. if we reach the tail before

                             // we traverse to the node, delete the tail

                             if ( temp == tail )

                                           return DeleteFromTail();

              }

              // if deleting the head just call

              // the appropriate member function

              // and don't repeat that logic here

              if (temp == head) return DeleteFromHead();

              // otherwise, delete the node we traversed to

              prev->next = temp->next;

              current.data = temp->data;

              delete temp;

              return current;

}

///////////////////////////////////////////////////////////////////////

// InsertNode

///////////////////////////////////////////////////////////////////////

void NodeSLList::InsertNode(int nodeNum, const IntNode &node)

{

}

///////////////////////////////////////////////////////////////////////

// UpdateNode

///////////////////////////////////////////////////////////////////////

void NodeSLList::UpdateNode(int nodeNum, const IntNode &node)

{

              IntNode *tmp = head;

              // traverse to the node, or to the last node, whichever comes

              // first. if the last node is reached, then that is the node

              // that is updated

              for (int i=1; i< nodeNum && tmp != tail; i++)

                             tmp = tmp->next;

              tmp->data = node.data;

}

///////////////////////////////////////////////////////////////////////

// SortList

///////////////////////////////////////////////////////////////////////

void NodeSLList::SortList(unsigned int order)

{

}

///////////////////////////////////////////////////////////////////////

// DestroyList

///////////////////////////////////////////////////////////////////////

void NodeSLList::DestroyList()

{

              // while the list is NOT empy

              // keep removing the head node and make

              // the next node the head node

              for (IntNode *p; !IsEmpty(); )

              {

                             p = head->next;

                             delete head;

                             head = p;

              }

              head = tail = 0;

}

///////////////////////////////////////////////////////////////////////

// operator=

///////////////////////////////////////////////////////////////////////

NodeSLList & NodeSLList::operator=(NodeSLList & list)

{

}

///////////////////////////////////////////////////////////////////////

// operator==

///////////////////////////////////////////////////////////////////////

bool NodeSLList::operator==(NodeSLList & list)

{

}

///////////////////////////////////////////////////////////////////////

// operator!=

///////////////////////////////////////////////////////////////////////

bool NodeSLList::operator!=(NodeSLList & list)

{

}

///////////////////////////////////////////////////////////////////////

// operator+

///////////////////////////////////////////////////////////////////////

NodeSLList NodeSLList::operator+(NodeSLList & list)

{

}

///////////////////////////////////////////////////////////////////////

// RetrieveNode

//

// Description: retrieve data from a node without removing it from

//              the list

// Input: node number (1-N; not 0-N-1)

// Output: none

// Returns: reference to node data

///////////////////////////////////////////////////////////////////////

IntNode & NodeSLList::RetrieveNode(int nodeNum) const

{

              IntNode *tmp = head;

              // traverse to the node, or to the last node, whichever comes

              // first

              for (int i=1; i< nodeNum && tmp != tail; i++)

                             tmp = tmp->next;

              return *tmp;

}

ostream & operator<<(ostream & output, NodeSLList & list)

{

}

Explanation / Answer

#ifndef INT_LINKED_LIST
#define INT_LINKED_LIST

#include <iostream>

using std::ostream;
using std::cout;
using std::cin;
using std::endl;


struct IntNode
{
int data;
IntNode * next;
};

// Class NodeSLList1 Declaration

class NodeSLList {

friend ostream & operator<<(ostream &, NodeSLList &);

public:
  
NodeSLList();
NodeSLList(NodeSLList &);
~NodeSLList();
bool IsEmpty();
int GetSize();
void AddToHead(const IntNode & node);
IntNode DeleteFromHead();
void AddToTail(const IntNode & node);
IntNode DeleteFromTail();
IntNode DeleteNode(int nodeNum);
void InsertNode(int nodeNum, const IntNode &node);
void UpdateNode(int nodeNum, const IntNode &node);
void DestroyList();
NodeSLList & operator=(NodeSLList &);
bool operator==(NodeSLList &);
bool operator!=(NodeSLList &);
NodeSLList operator+(NodeSLList &);

private:


IntNode *head, *tail;
IntNode &RetrieveNode(int nodeNum) const; //helper function
//nodeNum is
};

#endif INT_LINKED_LIST

//NodeListSL.cpp

#include "NodeSLList.h"

///////////////////////////////////////////////////////////////////////
// default constructor
///////////////////////////////////////////////////////////////////////
NodeSLList::NodeSLList()
{
head = tail = 0;
}

///////////////////////////////////////////////////////////////////////
// copy constructor
///////////////////////////////////////////////////////////////////////
NodeSLList::NodeSLList(NodeSLList & list)
{
   IntNode *tmp;
  
   for(int i=1;i<list.GetSize();i++)
   {
       *tmp=list.RetrieveNode(i);
       AddToTail(*tmp);
   }
}

///////////////////////////////////////////////////////////////////////
// destructor
///////////////////////////////////////////////////////////////////////
NodeSLList::~NodeSLList()
{
// call destroyList() to remove all nodes
// and reset linked list
DestroyList();
}

///////////////////////////////////////////////////////////////////////
// IsEmpty
///////////////////////////////////////////////////////////////////////
bool NodeSLList::IsEmpty()
{
// if head is NULL, then the list is empty, and we will return true
// otherwise, we will return false
return (head == 0);
}

///////////////////////////////////////////////////////////////////////
// GetSize
///////////////////////////////////////////////////////////////////////
int NodeSLList::GetSize()
{
// check to see if the list is empty. if
// so, just return 0
if ( IsEmpty() ) return 0;

int size = 1;
IntNode *p = head;
// compute the number of nodes and return
while (p != tail)
{
// until we reach the tail, keep counting
size++;
p = p->next;
}
return size;
}

///////////////////////////////////////////////////////////////////////
// AddToHead
///////////////////////////////////////////////////////////////////////
void NodeSLList::AddToHead(const IntNode & node)
{
// create a new node, and make it the head. the
// previous head will become head->next
IntNode * next = head;
head = new IntNode;
head->next = next;
head->data = node.data;

// if this is the first node, make the tail the
// same as the head
if (tail == 0)
tail = head;
}

///////////////////////////////////////////////////////////////////////
// DeleteFromHead
///////////////////////////////////////////////////////////////////////
IntNode NodeSLList::DeleteFromHead()
{
IntNode temp;
temp.data=0;
temp.next=NULL;
if (IsEmpty())
{
cout << "*****ERROR: Can't delete from head. List is Empty" << endl;
return temp;
}

// get current value of node we are about to delete,
// so we can return it.
temp.data = head->data;

IntNode *tmp = head;

// if there is only one node, set the head and pointer tails
// to NULL (0)
if (head == tail)
head = tail = 0;

// otherwise, move the head pointer to the next node
// in the list
else
head = head->next;

// delete head node
delete tmp;

// return value of node that was deleted
return temp;
}

///////////////////////////////////////////////////////////////////////
// AddToTail
///////////////////////////////////////////////////////////////////////
void NodeSLList::AddToTail(const IntNode & node)
{

   // create a new node, and make it the tail. the
   // previous tail will become tail->next
  
   IntNode *tmp;
   tmp->data=node.data;
   tmp->next=NULL;//or nullptr?
   tail->next=tmp;

       // if this is the first node, make the tail the
   // same as the head
   if (head == 0) //
       tail=tmp;
}

///////////////////////////////////////////////////////////////////////
// DeleteFromTail
///////////////////////////////////////////////////////////////////////
IntNode NodeSLList::DeleteFromTail()
{
IntNode nodeData;

// get the current data at the tail
nodeData.data = tail->data;


// if there is only one node, delete the only node, and set the
// head and tail pointers to NULL (0)
if (head == tail)
{
delete head;
head = tail =0;
}

// otherwise, traverse to the tail node and delete it
else
{
IntNode * temp;
// traverse to tail pointer
for (temp = head; temp->next != tail; temp = temp->next);
delete tail;
tail = temp;
tail->next = 0;
}

return nodeData;
}


///////////////////////////////////////////////////////////////////////
// DeleteNode
///////////////////////////////////////////////////////////////////////
IntNode NodeSLList::DeleteNode(int nodeNum)
{
if (nodeNum <= 0) nodeNum = 1;
IntNode *prev=head , *temp=head;
IntNode current;

// traverse to the node
for (int loop=1; loop<nodeNum; loop++)
{
prev=temp, temp=temp->next;
// check for case where nodeNum is > the number of
// nodes in the list. if we reach the tail before
// we traverse to the node, delete the tail
if ( temp == tail )
return DeleteFromTail();
}

// if deleting the head just call
// the appropriate member function
// and don't repeat that logic here
if (temp == head) return DeleteFromHead();

// otherwise, delete the node we traversed to
prev->next = temp->next;
current.data = temp->data;

delete temp;

return current;
}

///////////////////////////////////////////////////////////////////////
// InsertNode
///////////////////////////////////////////////////////////////////////
void NodeSLList::InsertNode(int nodeNum, const IntNode &node)
{
IntNode *prevNode = head;
for (int i = 1; i < nodeNum; i++)
prevNode = prevNode->next;

IntNode * insert;
insert = new IntNode(node);
prevNode->next = insert;

insert->next = prevNode->next->next;
}


///////////////////////////////////////////////////////////////////////
// UpdateNode
///////////////////////////////////////////////////////////////////////
void NodeSLList::UpdateNode(int nodeNum, const IntNode &node)
{
IntNode *tmp = head;

// traverse to the node, or to the last node, whichever comes
// first. if the last node is reached, then that is the node
// that is updated
for (int i=1; i< nodeNum && tmp != tail; i++)
tmp = tmp->next;

tmp->data = node.data;
}

///////////////////////////////////////////////////////////////////////
// DestroyList
///////////////////////////////////////////////////////////////////////
void NodeSLList::DestroyList()
{
// while the list is NOT empy
// keep removing the head node and make
// the next node the head node
for (IntNode *p; !IsEmpty(); )
{
p = head->next;
delete head;
head = p;
}
head = tail = 0;
}

///////////////////////////////////////////////////////////////////////
// operator=
///////////////////////////////////////////////////////////////////////
NodeSLList & NodeSLList::operator=(NodeSLList & list)
{
   IntNode *origPtr, *LastPtr;
   origPtr=list.head;
   LastPtr= new IntNode();
   head=LastPtr;

   while(LastPtr != NULL){
           LastPtr = new IntNode();
           LastPtr = LastPtr->next;
       }
   return *this;  
}

///////////////////////////////////////////////////////////////////////
// operator==
///////////////////////////////////////////////////////////////////////
bool NodeSLList::operator==(NodeSLList & list)
{
   IntNode *tmp1;
   *tmp1=RetrieveNode(1);
      
   IntNode *tmp2=list.head;
   int c=0;
  
  
   for(int i=2;i<list.GetSize();i++,tmp2=tmp2->next)
   {
       *tmp1 = RetrieveNode(i);
      
       if(tmp1->data==tmp2->data)

           c=1;

       else
          
       {
           c=0;
           break;
       }  
   }
  
   return(c==1);
}

///////////////////////////////////////////////////////////////////////
// operator!=
///////////////////////////////////////////////////////////////////////
bool NodeSLList::operator!=(NodeSLList & list)
{
   IntNode *tmp1;
   IntNode *tmp2=list.head;
   int c=0;
  
  
   for(int i=1;i<GetSize();i++,tmp2=tmp2->next)
   {
       *tmp1 = RetrieveNode(i);
      
       if(tmp1->data!=tmp2->data)
       {
           c=1;
           break;
       }
   }
          
   return(c==1);
}

///////////////////////////////////////////////////////////////////////
// RetrieveNode
//
// Description: retrieve data from a node without removing it from
// the list
// Input: node number (1-N; not 0-N-1)
// Output: none
// Returns: reference to node data
///////////////////////////////////////////////////////////////////////
IntNode & NodeSLList::RetrieveNode(int nodeNum) const
{
IntNode *tmp = head;

// traverse to the node, or to the last node, whichever comes
// first
for (int i=1; i< nodeNum && tmp != tail; i++)
tmp = tmp->next;

return *tmp;
}

ostream & operator<<(ostream & output, NodeSLList & list)
{  
   IntNode *tmp = list.head; // temporary pointer starting from head
  
   for (int i=1; i<=list.GetSize(); i++)
   {
       output<<tmp->data;
       tmp=tmp->next;//movethe pointer till the specified nodeNum
  
   }
   return output;
}

Related Questions

Navigate

• Browse (All)
• Browse D
• Subjects

---