Singly Linked List: Member functions

Question

I am having a hard time trying to do these last functions in my singly linked list program :

    int size() const;
    const std::string& get(int index) const throw (EmptyException, OutOfBoundException);
    void remove(int index) throw (EmptyException, OutOfBoundException);
    bool remove(const std::string& e);
    bool removeAll(const std::string& e);

I dont quite know how to do these. Here is my code

StringNode.h

#ifndef STRING_NODE_H
#define STRING_NODE_H

#include <string>

// A node in string singly linked list
class StringNode {
private:
    // element value of a node
    std::string elem;

    // pointer to the next node in the list
    StringNode *next;

    // provide StringLinkedList access
    friend class StringLinkedList;
};

#endif

StringLinkedList.h

#ifndef STRING_LINKED_LIST_H
#define STRING_LINKED_LIST_H

#pragma warning(disable: 4290)

#include "StringNode.h"
#include "Exception.h"

String singly linked list class StringLinkedList { private: // pointer to the head of the list StringNode *head; StringNode *Tail; // size of the list int n;

public:
    // default constructor
    StringLinkedList();

    // destructor 
    ~StringLinkedList();

    // ## this function is provided ##
    // return the string representation of the list; each node is seperated
    // by "->"
    //  example: 
    //      "A->B->C" (without quotes)
    //          A is the head node, C is the tail
    //      "" (without quotes)
    //          empty list
    std::string toString();

    // return true if the list is empty, false otherwise
    bool empty() const;

    // return the number of nodes in the list
    //  note: take advantage of the private member we have, implement this
    //      running with O(1)
    int size() const;

    // return the element of front node
    const std::string& front() const throw (EmptyException);

    // return the element of back node
    const std::string& back() const throw (EmptyException);

    // return the element of a node at a specific index (index) of the list
    //  EmptyException is thrown if the list is empty
    //  The index should be in range of [0, n-1], which is 0 <= index <= (n-1)
    //  OutOfBoundException is thrown if index is out of that range
    const std::string& get(int index) const throw (EmptyException, OutOfBoundException);

    // add a new node with element e to the front of the list
    void addFront(const std::string& e);

    // add a new node with element e to the back of the list
    void addBack(const std::string& e);

    // insert a new node at a specific position (pos) of the list;
    //  the position should be in range of [0, n], which is 0 <= pos <= n. 
    //  OutOfBoundException is thrown if index is out of that range
    //  
    //  example: 
    //      A->B
    //          position can be inserted is 0 (before A), 1 (between
    //          A and B), 2 (after B); other positions will cause
    //          OutOfBoundException
    void insert(int pos, const std::string& e) throw (OutOfBoundException);

    // remove the front node from the list
    //  EmptyException is thrown if the list is empty
    void removeFront() throw (EmptyException);

    // remove the back node from the list
    //  EmptyException is thrown if the list is empty 
    void removeBack() throw (EmptyException);

    // remove a node at a specific index (index) of the list; the 
    //  index should be in range of [0, n-1], which is 0 <= index <= (n-1)
    //  OutOfBoundException is thrown if index is out of that range; 
    //  EmptyException is thrown if the list is empty.
    //  
    //  example: 
    //      A->B
    //          position can be removed is 0 (A), 1 (B); otherwise 
    //          position will cause OutOfBoundException
    void remove(int index) throw (EmptyException, OutOfBoundException);

    // remove the first node that has a matched element e, starting from 
    // the head node; return true if a match is found, false otherwise
    bool remove(const std::string& e);

    // remove the ALL elements that are matched e; return true if a match 
    // is found, false otherwise
    bool removeAll(const std::string& e);

    // reverse the order of the list
    //  example: 
    //      A->B->C->D
    //          after reverse(), D->C->B->A
    void reverse();
};

#endif

StringLinkedList.cpp

 #include "StringLinkedList.h"

// default constructor (COMPLETED)
StringLinkedList::StringLinkedList() 
    : head(NULL), n(0) { }

// destructor 
StringLinkedList::~StringLinkedList()

{
    while(!empty()) removeFront();
}

// return the string representation of the list; each node is seperated by "->"
std::string StringLinkedList::toString() {
    // return blank if the list is empty
    if (head == NULL) 
        return "";

    // traverse to each node and append element of each
    // node to final output string
    std::string out = "";
    StringNode *node = head;
    while (node != NULL) {
        out += node->elem + "->";
        node = node->next;
    }

    // return final string without last "->"
    return out.substr(0, out.size()-2);
}
bool StringLinkedList::empty() const
{return head==NULL;}

const std::string& StringLinkedList::front() const throw (EmptyException)
{
    if(head==0)throw EmptyException("Empty head");
    return head->elem;
}
const std::string& StringLinkedList::back() const throw (EmptyException)
{
    if(tail==0)throw EmptyException("empty tail");
    return tail->elem;
}
void StringLikedList::addFront(const std::string& e)
{
    StringNode* v= new StringNode;
    v->elem=e;
    v->next=head;
    head=v;
}
void StringLinkedList::addBack(const std::string& e)
{
    StringNode* node=head;
    while(node->next!=NULL)
        node=node->next;
    StringNode* v=new StringNode;
    v->elem=e;
    v->next=NULL;
    node->next=v;
}
void StingLinkedList::removeFront() throw (EmptyException)
{
    if(head==0) throw EmptyException("empty");
    else
    {
        StringNode* remove;
        remove=head;
        if(head==tail)
        {
            head=NULL;
            tail=NULL;
        }
        else
        {
            head=head->next;
        }
        delete remove;
    }

}


void StringLinkedList::removeBack() throw (EmptyException)
{
    if (tail==0)throw EmptyException("empty");
    else
    {
        StringNode* remove;
        remove=tail;
        if(head==tail)
        {
            head=NULL;
            tail=NULL;
        }
        else 
        {
            StringNode* previousToTail=head;
            while(previousToTail->next !=tail)
                previousToTail=previousToTail->next;
            tail=previousToTail;
            tail->next=NULL;
        }
        delete remove;
    }
}
void StringLinkedList::reverse()
{
    StringNode* tempHead=head;
    StringNode* nodes=NULL;
    StringNode* nextNode=NULL:
    if (head==NULL)
        return;
    tail=head;
    nodes=head->next;
    while(nodes!=NULL)
    {
        nextNode=nodes;
        nodes=nodes->next;
        nextNode->next=tempHead;
        tempHead=nextNode;
    }
    head=tempHead;
    tail->next=NULL;
}

thanks for any help

Answer 1

You seem to have all the techniques needed already for these. Here's some pseudo-code.

size - essentially the same thing as your toString function, except that you count rather than build up a string (it's easier!).

int count = 0;
while (current != null) {
  count++;
  current = current->next;
}
return count;

get - same again, except that you stop short once you've located the right node

int cur_index = 0;
while ((current != null) && (cur_index < index)) {
  cur_index++;
  current = current->next;
}
// make sure we found it before you:
return current->data;

remove is a bit trickier. You first locate the node to be removed, than fix up the previous node's next pointer to skip over it.

prev = null;
while ((current != null) && (/* compare count or compare string */)) {
  /* update counter */
  prev = current;
  current = current->next;
}

Once that loop is over:

• if prev is still null, either the first element matched (index given is 0 or the item's string matched), or the list was empty. If the first element matched, you already have code to remove it.
• if current is null, you didn't find it.
• if prev and current are valid, you matched and need to remove current. Make prev->next point to current->next.

Remember to deallocate removed nodes. removeAll is the same as remove, except you don't stop once you've found a node to remove, and you'll have to think a bit about what (true/false) you need to return.

Always test with at least:

• an empty list
• a list with exactly one element
• a list with more than one element
• index 0, negative indexes, valid non-zero index, index beyond the list
• remove that will make the list empty, removeAll that will make the list empty
• remove and removeAll that won't make the list empty