Question

For this program you will add and test 2 new member functions to the class in

//************************  intSLList.h  **************************
//           singly-linked list class to store integers

#ifndef INT_LINKED_LIST
#define INT_LINKED_LIST

class IntSLLNode {
public:
    IntSLLNode() {
        next = 0;
    }
    IntSLLNode(int el, IntSLLNode *ptr = 0) {
        info = el; next = ptr;
    }
    int info;
    IntSLLNode *next;
};

class IntSLList {
public:
    IntSLList() {
        head = tail = 0;
    }
    ~IntSLList();
    int isEmpty() {
        return head == 0;
    }
    void addToHead(int);
    void addToTail(int);
    int  deleteFromHead(); // delete the head and return its info;
    int  deleteFromTail(); // delete the tail and return its info;
    void deleteNode(int);
    bool isInList(int) const;
    void printAll() const;
private:
    IntSLLNode *head, *tail;
};

#endif

The two member functions are:

insertByPosn(int el, int pos)

Assuming that the positions of elements of a list begin numbering at 1 and continue to the end of the list, you will insert a new node with info value el at position pos. pos will become the position of the new node in the modified list. For example, if pos = 1, insert the new node at the head of the list. If pos = 2, for example, insert the new node BEFORE the node currently at position 2. If the list is empty prior to insertion, insert the new node in the list and adjust head and tail pointers. If pos is too large, don't do anything. If pos is 0 or negative, don't do anything.

removeByPosn(int pos)

Assume position of elements are defined as above. If pos is zero or negative, do nothing. If the list is empty prior to the request to delete a node, do nothing. If pos is too large, do nothing.

To aid in verifying results, you should use the following modified version of printAll. This requires: #include <string>

void IntSLList::printAll(string locn) const {

cout << "Contents of the list " << locn << endl;

for (IntSLLNode *tmp = head; tmp != 0; tmp = tmp->next)

cout << tmp->info << " ";

if (head != 0)

cout << "Head is: " << head->info << " Tail is: " << tail->info << endl << endl;

}

For extra credit, you can also create the following:

reverseList()

Traverse the existing list beginning at the head and create a new (reversed) list with head newhead and tail newtail. Put new nodes in the new list by putting the new nodes at the head of the new list each time. Do not call any other member functions during this process. If the list to be reversed is empty, make sure that you account for this case. After the new (reversed) list is created, delete the old list using its destructor.

The test program to be used is:

int main()

{

IntSLList singly_linked_list = IntSLList();

singly_linked_list.addToHead(9);

singly_linked_list.addToHead(7);

singly_linked_list.addToHead(6);

singly_linked_list.printAll("at creation:");

singly_linked_list.insertByPosn(8, 2);

singly_linked_list.printAll("after insertion of 8 at position 2:");

singly_linked_list.insertByPosn(10, 4);

singly_linked_list.printAll("after insertion of 10 at position 4:");

singly_linked_list.insertByPosn(12, 6);

singly_linked_list.printAll("after insertion of 12 at position 6:");

singly_linked_list.insertByPosn(14, 8);

singly_linked_list.printAll("after attempted insertion of 14 at position 8:");

singly_linked_list.insertByPosn(5, 1);

singly_linked_list.printAll("after insertion of 5 at position 1:");

singly_linked_list.insertByPosn(4, 0);

singly_linked_list.printAll("after attempted insertion of 4 at position 0:");

singly_linked_list.removeByPosn(2);

singly_linked_list.printAll("after deletion of 6 at position 2:");

singly_linked_list.removeByPosn(6);

singly_linked_list.printAll("after deletion of 12 at position 6:");

singly_linked_list.removeByPosn(10);

singly_linked_list.printAll("after attempted deletion at position 10:");

// insert test for optional list reversal here

return (0);

}

The correct output from running the test program is:

Contents of the list at creation:

6 7 9 Head is: 6 Tail is: 9

Contents of the list after insertion of 8 at position 2:

6 8 7 9 Head is: 6 Tail is: 9

Contents of the list after insertion of 10 at position 4:

6 8 7 10 9 Head is: 6 Tail is: 9

Contents of the list after insertion of 12 at position 6:

6 8 7 10 9 12 Head is: 6 Tail is: 12

Contents of the list after attempted insertion of 14 at position 8:

6 8 7 10 9 12 Head is: 6 Tail is: 12

Contents of the list after insertion of 5 at position 1:

5 6 8 7 10 9 12 Head is: 5 Tail is: 12

Contents of the list after attempted insertion of 4 at position 0:

5 6 8 7 10 9 12 Head is: 5 Tail is: 12

Contents of the list after deletion of 6 at position 2:

5 8 7 10 9 12 Head is: 5 Tail is: 12

Contents of the list after deletion of 12 at position 6:

5 8 7 10 9 Head is: 5 Tail is: 9

Contents of the list after attempted deletion at position 10:

5 8 7 10 9 Head is: 5 Tail is: 9

Answer 1

C++ code : updated code is in bold text

intSLList.h

//=====================================================================

//           singly-linked list class to store integers

#ifndef INT_LINKED_LIST
#define INT_LINKED_LIST
#include<string>
#include<iostream>

using namespace std;

class IntSLLNode {
public:
   IntSLLNode() {
       next = 0;
   }
   IntSLLNode(int el, IntSLLNode *ptr = 0) {
       info = el; next = ptr;
   }
   int info;
   IntSLLNode *next;
};

class IntSLList {
public:
   IntSLList() {
       head = tail = 0;
   }
   ~IntSLList();
   int isEmpty() {
       return head == 0;
   }
   void addToHead(int);
   void addToTail(int);
   int deleteFromHead(); // delete the head and return its info;
   int deleteFromTail(); // delete the tail and return its info;
   void deleteNode(int);
   bool isInList(int) const;
   void printAll() const;

   // new added member function
   void insertByPosn(int el, int pos);
   void removeByPosn(int pos);

    IntSLList reverseList();

   //for testing purpose
   void printAll(string locn) const;
private:
   IntSLLNode *head, *tail;
};

#endif

//=====================================================================

insLList.cpp

//=====================================================================

#include"intSLList.h"

void IntSLList::insertByPosn(int el, int pos)
{
   // do nothing when position is zero or negative - do nothing
   // if (pos <= 0) return;

   // create new node and point tmp pointer to created node
   IntSLLNode *tmp = new IntSLLNode(el, 0);

   if (pos == 1)
   {
       //if linklist is empty. add first node to list
       //make head and tail both pointer to point only node
       if (head == 0)
       {
           head = tmp;
           tail = tmp;
       }
       // if linklist is not empty add old linklist after new node and
       // update head to point new node
       else
       {
           tmp->next = head;
           head = tmp;
       }
       // we can simply call addToHead function but i'm not sure is it allowed here
       // addToHead(el);
   }
   else if (pos>1)
   {
       IntSLLNode *find = head;
       int i;
       //move to node one before position
       for (i = 1; i < pos-1; i++)
       {
           if (find->next != 0) find = find->next;
           else break;
       }
       // pos is too large we have not reached to given position - do nothing
       //if (i != (pos - 1)) return;

       if (i == (pos-1))
       {
           tmp->next = find->next; // connect old "pos" node after new node    tmp --> "pos"node
           find->next = tmp;        // connect new node to "pos-1" node      "pos-1" node --> tmp --> "pos" node
           //pos-1 is last position then update to new pos element;
           if (find == tail)
           {
               tail = tmp;
           }
       }

   }
}

void IntSLList::removeByPosn(int pos)
{
   // list is empty or position is zero or negative - do nothing
   if (head == 0 || pos <= 0) return;

   // position is 1 then remove head node
   if (pos == 1)
   {
       IntSLLNode *tmp = head;
       head = head->next;
       delete(tmp);
       if (head == 0) tail = 0; // if updated list is empty than update tail
   }
   else
   {
       IntSLLNode *find = head;
       int i;
       //move to node one before position
       for (i = 1; i < pos - 1; i++)
       {
           if (find->next!= 0) find = find->next;
           else break;
       }
       // pos is too large we have not reached to given position - do nothing
       //if (i != (pos - 1)) return;

       if (i == (pos - 1))
       {
           //pos-1 is last position then nothing to update
           if (find == tail) return;
           else
           {
               //"pos" node is tail node then update tail node
               if (find->next == tail) tail = find;
               //"pos-1" node --> "pos" node --> "pos+1" node
               //"pos-1" node --> "pos+1" node
               IntSLLNode *tmp = find->next;
               find->next = find->next->next; // connect old "pos-1" node to "pos+1"node
               delete(tmp);
           }
       }
   }
}

IntSLList IntSLList::reverseList()
{
   IntSLList *reversed = new IntSLList();
   // list is empty
   if (head == 0) return (*reversed);
   // single element list
   IntSLLNode *tmp;

   // create head node for reversed list
   IntSLLNode *reversed_head = new IntSLLNode(head->info, 0);
   reversed->head = reversed_head;
   reversed->tail = reversed_head;

   // iterate from second element to last element
   for (tmp = head->next; tmp != 0; tmp = tmp->next)
   {
       // create a new node with next is pointing to head of list
       IntSLLNode *reversed_new = new IntSLLNode(tmp->info, reversed->head);
       // update head of list
       reversed->head = reversed_new;
   }
   this->~IntSLList(); // deleting old list
   return *reversed;    // return object of IntsLList
}

/******* following defination are just for compilation at my end
you can update with you own defination ***/

void IntSLList::printAll(string locn) const {
   cout << "Contents of the list " << locn << endl;
   for (IntSLLNode *tmp = head; tmp != 0; tmp = tmp->next)
       cout << tmp->info << " ";
   if (head != 0)
       cout << "Head is: " << head->info << " Tail is: " << tail->info << endl << endl;
}

void IntSLList::addToHead(int el)
{
   // create new node and point tmp pointer to created node
   IntSLLNode *tmp = new IntSLLNode(el, 0);
   //if linklist is empty. add first node to list
   //make head and tail both pointer to point only node
   if (head == 0)
   {
       head = tmp;
       tail = tmp;
   }
   // if linklist is not empty add old linklist after new node and
   // update head to point new node
   else
   {
       tmp->next = head;
       head = tmp;
   }
}
void IntSLList::addToTail(int el)
{
   // create new node and point tmp pointer to created node
   IntSLLNode *tmp = new IntSLLNode(el, 0);
   //if linklist is empty. add first node to list
   //make head and tail both pointer to point only node
   if (head == 0)
   {
       head = tmp;
       tail = tmp;
   }
   // if linklist is not empty add new node end of old linklist and
   // update tail to point new node
   else
   {
       tail->next = tmp;
       tail = tmp;
   }
}

int IntSLList::deleteFromHead() // delete the head and return its info;
{
   // empty list
   if (head == 0) return -1; // not specified what we need to return when it is empty

   int temp = head->info; // store info of head pointer
   head = head->next;      // move head pointer to next node
   if (head == 0) tail = 0;// if new list is empty then change tail pointer also

   return temp;
}
int IntSLList::deleteFromTail() // delete the tail and return its info;
{
   if (tail == 0) return -1;   // not specified what we need to return when it is empty
   int temp = tail->info;   // store info of tail pointer
   if (head == tail) // only one node
   {
       head = 0;
       tail = 0;
       return temp;
   }
   // start from head and find node whose next node is tail
   IntSLLNode *tmp;
   for ( tmp= head; tmp->next == tail; tmp = tmp->next);
   tmp->next = 0;    // remove current tail node;
   tail = tmp;       // update tail to new last node

   return temp;
}

void IntSLList::deleteNode(int el)
{
   //empty list
   if (head == 0) return;
   //single node list
   if (head->info == el)
   {
       head = 0;
       tail = 0;
       return;
   }

   // start from head and find node whose next node's info is el
   // as we are looking at next node so tmp pointer will only look for tail
   IntSLLNode *tmp;
   for (tmp = head; tmp != tail; tmp = tmp->next)
   {
       if (tmp->next->info == el)
       {
           //remove middle node by connecting directly to next to next node;
           tmp->next = tmp->next->next;
           return;
       }
   }

   //else not found

}

bool IntSLList::isInList(int el) const
{
   IntSLLNode *tmp;
   for (tmp = head; tmp != 0; tmp = tmp->next);
   {
       if (tmp->info == el) return true;   // element found
   }

   return false; // element not found
}

void IntSLList::printAll() const
{
   for (IntSLLNode *tmp = head; tmp != 0; tmp = tmp->next)
       cout << tmp->info << " ";
   if (head != 0)
       cout << "Head is: " << head->info << " Tail is: " << tail->info << endl << endl;
}

IntSLList::~IntSLList()
{
   IntSLLNode *tmp1,*tmp = head;
   while (tmp!=0)
   {
       tmp1 = tmp;
       tmp = tmp->next; // move to next node;
       delete(tmp1);    // delete previous node;
   }
   head = 0;
   tail = 0;
}

//=====================================================================

main.cpp

//=====================================================================

#include<iostream>
#include"intSLList.h"
using namespace std;

int main()

{

   IntSLList singly_linked_list = IntSLList();

   singly_linked_list.addToHead(9);
   singly_linked_list.addToHead(7);
   singly_linked_list.addToHead(6);
   singly_linked_list.printAll("at creation:");
   singly_linked_list.insertByPosn(8, 2);
   singly_linked_list.printAll("after insertion of 8 at position 2:");
   singly_linked_list.insertByPosn(10, 4);
   singly_linked_list.printAll("after insertion of 10 at position 4:");
   singly_linked_list.insertByPosn(12, 6);
   singly_linked_list.printAll("after insertion of 12 at position 6:");
   singly_linked_list.insertByPosn(14, 8);
   singly_linked_list.printAll("after attempted insertion of 14 at position 8:");
   singly_linked_list.insertByPosn(5, 1);
   singly_linked_list.printAll("after insertion of 5 at position 1:");
   singly_linked_list.insertByPosn(4, 0);
   singly_linked_list.printAll("after attempted insertion of 4 at position 0:");
   singly_linked_list.removeByPosn(2);
   singly_linked_list.printAll("after deletion of 6 at position 2:");
   singly_linked_list.removeByPosn(6);
   singly_linked_list.printAll("after deletion of 12 at position 6:");
   singly_linked_list.removeByPosn(10);
   singly_linked_list.printAll("after attempted deletion at position 10:");

   // added for reveresing linklist test
   IntSLList reversed = singly_linked_list.reverseList();
   reversed.printAll("after reversing singly_linked_list:");

   return (0);

}

//=====================================================================

compile: g++ main.cpp intSLList.cpp

run: ./a.out

output: