Solved

searchFromEnd function doubly linked list

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

Top 6 Sources for Identifying Threat Actor TTPs

Understanding your enemy is essential. These six sources will help you identify the most popular threat actor tactics, techniques, and procedures (TTPs).

Join & Write a Comment

When writing generic code, using template meta-programming techniques, it is sometimes useful to know if a type is convertible to another type. A good example of when this might be is if you are writing diagnostic instrumentation for code to generat…
Here is a helpful source code for C++ Builder programmers that allows you to manage and manipulate HTML content from C++ code, while also handling HTML events like onclick, onmouseover, ... Some objects defined and used in this source include: …
The viewer will learn how to use and create new code templates in NetBeans IDE 8.0 for Windows.
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.

746 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

9 Experts available now in Live!

Get 1:1 Help Now