Solved

searchFromEnd function doubly linked list

Posted on 2004-10-17
1
338 Views
Last Modified: 2013-12-14
I'm trying to implement a template doubly linked list class. I almost have it, but I'm having truble with how to do a searchFromEnd function. Can someone please show me how this would be done? Here is my code so far....

------------------------------
Node.h

#ifndef NODE_H
#define NODE_H

//include files
#include <string>

//generic data type alias
typedef std::string Generic;

template <typename T>

//structure of a node
struct Node                                                
{
      //data piece of node
      Generic data;
      //pointer to the next node
      Node<T> *next;
      //pointer to the previous node
      Node<T> *previous;
};

//end define
#endif
-------------------------------------

LL.h

#ifndef LINKEDLIST_H
#define LINKEDLIST_H

//include files
#include "Node.h"
#include <iostream>

template <typename T>

//declaration of LinkedList class
class LinkedList
{
//public member functions
public:
      //constructor
      LinkedList();
      //copy constructor
      LinkedList(const LinkedList& list);
      //destructor
      ~LinkedList();

      void insertFront(const Generic &item);
      void searchFromEnd();
      void insertEnd(const Generic &item);
      void display(std::ostream &outStream = std::cout) const;
      void displayReverse(std::ostream &outStream = std::cout) const;
      void remove(const Generic &item);
      void deleteList();
      void removeFirstNode();

      int getLength() const;
      Generic getFirstValue() const;
      bool search(const Generic &item) const;
      bool empty() const;
      bool full() const;

//private data members
private:
      //first element in linked list
      Node *first;
      //last element in linked list
      Node *last;

};

//constructor
//called when the class instance is created
//sets up initial values for the class data members
//initial first pointer to NULL
template <typename T>
LinkedList<T>::LinkedList() : first(0)
{

}

//copy constructor
template <typename T>
LinkedList<T>::LinkedList(const LinkedList& list) : first(0), last(0)
{
      first = list.first;
      last = list.last;
}

//destructor
//called when the class instance is destroyed
template <typename T>
LinkedList<T>::~LinkedList()
{
      //cleans up leftover memory
      deleteList();
}

//insertFront
//accepts item, a Generic data type to insert into the list
//inserts the passed item into the very beginning of the list
template <typename T>
void LinkedList<T>::insertFront(const Generic &item)
{
      //create a pointer to a node
      Node *newNode;

      //allocate memory for the new node
      newNode = new Node;

      //set the newNode's value
      newNode->data = item;

      //point the new node
      //same node that is currently the beginning of the list
      newNode->next = first;

      //change the beginning of the list to point to the newNode
      first = newNode;
}

//insertEnd
//accepts item, a Generic data type to insert into the list
//inserts the passed item into the end of the list
template <typename T>
void LinkedList<T>::insertEnd(const Generic &item)
{
      //create pointers to a node
      Node *current = first;
      Node *newNode;

      //allocate memory for the newNode
      newNode = new Node;

      //initialize the node's members
      newNode->data = item;
      newNode->next = 0;

      //check to see if there are nodes in the list
      if (empty())
      {
            //set the beginning of the list to point at the new node
            first = newNode;
      }
      else
      {
            //loop through all nodes in the list
            while (current->next != 0)
            {
                  current = current->next;
            }

            //set the last node's next value to the new node
            current->next = newNode;
      }
}

//display
//accepts outStream, a file or cout stream to output data to
//always displays all of the data in the linked list
//either to a file or  to the screen
template <typename T>
void LinkedList<T>::display(ostream &outStream) const
{
      //create a pointer to a node
      Node *current = first;

      //loop through each node in the list
      while (current != 0)
      {
            //send data to the output stream
            outStream << current->data << endl;

            //move to the next node
            current = current->next;
      }
}

//displayReverse
//accepts outStream, a file or cout stream to output data to
//always displays all of the data in the linked list
//either to a file or  to the screen
template <typename T>
void LinkedList<T>::displayReverse(ostream &outStream) const
{
      //create a pointer to a node
      Node *current = last;

      //loop through each node in the list
      while (current != 0)
      {
            //send data to the output stream
            outStream << current->data << endl;

            //move to the next node
            current = current->previous;
      }
}

//remove
//accepts item, a Generic data type to search and remove from the list
//searches for the item passed to it and removes that node from the list
template <typename T>
void LinkedList<T>::remove(const Generic &item)
{
      //check if the list is empty
      if (!empty())
      {
            //create a pointer to a node
            Node *current = first;

            //check if first item is what is being searched for
            if (current->data == item)
            {
                  //set the first node to point to the second node
                  first = current->next;

                  //deallocate first node
                  delete current;
            }
            else
            {
                  //create a pointer to a node
                  Node *previous = current;

                  //move current to the next node
                  current = current->next;

                  //loop through nodes until data is found
                  //or end of file has been reached
                  while ( (current != 0) && (current->data != item) )
                  {
                        //move each pointer to the next node
                        current = current->next;
                        previous = previous->next;
                  }

                  //check if either previous or current is null
                  if ( (current != 0) && (previous != 0) )
                  {
                        //set the previous node to point to the node following current
                        previous->next = current->next;

                        //deallocate the node searched for
                        delete current;
                  }
            }
      }
}

//deleteList
//deallocates all nodes in the list
//sets the first pointer to NULL
template <typename T>
void LinkedList<T>::deleteList()
{
      //create pointers to a node
      Node *current = first;
      Node *previous;

      //loop through all nodes in the list
      while (current != 0)
      {
            //set previous to the current node
            previous = current;

            //set current to the next node
            current = current->next;

            //deallocate the previous node
            delete previous;
      }

      //reset beginning of list to NULL
      first = 0;
}

//getLength
//counts all nodes in the list and returns the count
template <typename T>
int LinkedList<T>::getLength() const
{
      //create a pointer to a node
      Node *current = first;

      //create an int variable to hold the total
      int total;

      //loop through all nodes in the list
      while (current != 0)
      {
            //increment total by 1 and move to next node
            ++total;
            current = current->next;
      }

      //return the total
      return total;
}

//search
//accepts item, a Generic data type that is searched for in the list
//searches each node in the list to see if its value matches the item passed
//a true or false is returned if the item was found or not
template <typename T>
bool LinkedList<T>::search(const Generic &item) const
{
      //create a pointer to a node
      Node *current = first;

      //create a flag to tell if the value was found
      bool found = false;

      //loop through each node until the end of the list or the value is found
      while ( (current != 0) && (current->data != item) )
      {
            //move to the next node
            current = current->next;
      }

      //if current is not null then the end of the list was not reached
      if (current != 0)
      {
            //value was found
            found = true;
      }

      //return the found flag
      return found;
}

//empty
//returns a true value if the list is empty
//false if the list has nodes in it
template <typename T>
bool LinkedList<T>::empty() const
{
      //return true if the first is NULL
      return (first == 0);
}

//full
//this will always return a false value
//this linked list version has virtually unlimited memory
template <typename T>
bool LinkedList<T>::full() const
{
      return false;
}

//removeFirstNode
//removes first node from the list
template <typename T>
void LinkedList<T>::removeFirstNode()
{
      //check if the list is empty
      if (!empty())
      {
            //create a pointer to a node
            Node *current = first;

            //point the beginning of the list to the second node
            first = current->next;

            //deallocate the memory for  current
            delete current;
      }
}

//getFirstValue
//returns the value of the first node in the list
template <typename T>
Generic LinkedList<T>::getFirstValue() const
{
      //this will not work if list is empty
      return first->data;
}

//end define
#endif



0
Comment
Question by:jandhb
1 Comment
 
LVL 9

Accepted Solution

by:
jhshukla earned 25 total points
ID: 12344857
do the same as search() with very minor modifications:
1. start from Node* last
2. use nodePtr->prev to iterate
0

Featured Post

Free Tool: SSL Checker

Scans your site and returns information about your SSL implementation and certificate. Helpful for debugging and validating your SSL configuration.

One of a set of tools we are providing to everyone as a way of saying thank you for being a part of the community.

Question has a verified solution.

If you are experiencing a similar issue, please ask a related question

Suggested Solutions

IntroductionThis article is the second in a three part article series on the Visual Studio 2008 Debugger.  It provides tips in setting and using breakpoints. If not familiar with this debugger, you can find a basic introduction in the EE article loc…
Go is an acronym of golang, is a programming language developed Google in 2007. Go is a new language that is mostly in the C family, with significant input from Pascal/Modula/Oberon family. Hence Go arisen as low-level language with fast compilation…
The viewer will learn how to pass data into a function in C++. This is one step further in using functions. Instead of only printing text onto the console, the function will be able to perform calculations with argumentents given by the user.
The viewer will learn how to user default arguments when defining functions. This method of defining functions will be contrasted with the non-default-argument of defining functions.

726 members asked questions and received personalized solutions in the past 7 days.

Join the community of 500,000 technology professionals and ask your questions.

Join & Ask a Question