Solved

searchFromEnd function doubly linked list

Posted on 2004-10-17
1
328 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

Is Your Active Directory as Secure as You Think?

More than 75% of all records are compromised because of the loss or theft of a privileged credential. Experts have been exploring Active Directory infrastructure to identify key threats and establish best practices for keeping data safe. Attend this month’s webinar to learn more.

Question has a verified solution.

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

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…
Basic understanding on "OO- Object Orientation" is needed for designing a logical solution to solve a problem. Basic OOAD is a prerequisite for a coder to ensure that they follow the basic design of OO. This would help developers to understand the b…
The goal of the tutorial is to teach the user how to use functions in C++. The video will cover how to define functions, how to call functions and how to create functions prototypes. Microsoft Visual C++ 2010 Express will be used as a text editor an…
The viewer will learn how to clear a vector as well as how to detect empty vectors in C++.

920 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

Need Help in Real-Time?

Connect with top rated Experts

12 Experts available now in Live!

Get 1:1 Help Now