Solved

searchFromEnd function doubly linked list

Posted on 2004-10-17
1
336 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: ZipGrep

ZipGrep is a utility that can list and search zip (.war, .ear, .jar, etc) archives for text patterns, without the need to extract the archive's contents.

One of a set of tools we're offering as a way to say 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

Title # Comments Views Activity
FMX enumerated colours 2 115
c++ getting the first 10 characters of a char* string 11 98
The line on IDE 4 91
Syntax Error 2 77
Programmer's Notepad is, one of the best free text editing tools available, simply because the developers appear to have second-guessed every weird problem or issue a programmer is likely to run into. One of these problems is selecting and deleti…
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 perform CRUD operations on a MySql database.
The viewer will learn how to use and create keystrokes in Netbeans IDE 8.0 for Windows.

856 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