Improve company productivity with a Business Account.Sign Up

x
?
Solved

searchFromEnd function doubly linked list

Posted on 2004-10-17
1
Medium Priority
?
359 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 100 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: Site Down Detector

Helpful to verify reports of your own downtime, or to double check a downed website you are trying to access.

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.

Are you are experiencing a similar issue? Get a personalized answer when you ask a related question.

Have a better answer? Share it in a comment.

Join & Write a Comment

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 use NetBeans IDE 8.0 for Windows to connect to a MySQL database. Open Services Panel: Create a new connection using New Connection Wizard: Create a test database called eetutorial: Create a new test tabel called ee…
The viewer will be introduced to the technique of using vectors in C++. The video will cover how to define a vector, store values in the vector and retrieve data from the values stored in the vector.

585 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