Doubly Linked List -> main() {

# Makefile
#        It uses the C++ Compiler with all warnings and
#        full debugging; will create a single executable called 'main'
# ---------------------------------------------------------------
# the compiler
CPP = cxx
# compiler flags
CFLAGS = -L/usr/lib/cmplrs/cxx -DPOSIX_4D9  -g
# linker flags to link in the libraries libm.a and libtask.a
LFLAGS = -lm -ltask
#
RM = rm -f
# ----------------------------------------------------------------
# Explanation of macros:
#     $< is any dependent file which is out of file1
#     $* is the target's basename (without extension)
#     $@ is the target's fullname
#
# add suffix .cpp since it is not a default with make util
.SUFFIXES:      .cpp .o
#
# implicit rule for compilation only:
.cpp.o:
      ${CPP} -c ${CFLAGS} $<

OFILES=            main.o util.o

HFILES=            dlist.h util.h

# dependencies
#
default:      main      
#
main:           $(OFILES)
            ${CPP} ${CFLAGS} ${LFLAGS} $(OFILES) -o $@

main.o:            main.cpp dlist.h util.h

util.o:            util.cpp util.h

#
clean:
      ${RM} *.o
      ${RM} core
#
veryclean:      clean
      ${RM}  main  

#ifndef UTIL_H  
#define UTIL_H

#define NULL 0L

#define STDSCREEN 80        
#define DOWN 0                        
#define UP   1
#define END   0
#define START 1
#define FAIL    0
#define SUCCESS 1
#define MISS -1
#define HIT   1

enum Error_code {success,fail,range_error,underflow,overflow,fatal,
                not_present,duplicate_error,entry_inserted,entry_found,
                internal_error };

void clearScreen();
void clearTop();                      
void clearBelowTop();                
void goTop();                          
void topLine(const char * text = " "  );  
void bottomLin (char * text = " ");  
void hitAnyKey();                  
void flushInput();                  
void Warning(char *);                  
void Error(char *);                  
bool promptYesNo(char * prompt="");    
void EatWhiteSpace(void);            

#endif

/* filename: util.cpp
   Purpose: I/O and VT100 screen manipulation utility functions */

#include <iostream>
#include <ctype.h>
#include <stdlib.h>
#include "util.h"
 
void clearScreen (void) {

  cout << "\033[2J";          
  cout << "\033[;f";          

}

void clearTop()
 
  {cout << "\033[0;0f" << "\033[0K";}

void clearBelowTop()
 
  {cout << "\033[1;0f" << "\033[1B" << "\033[J";}

void goTop ()
 
  {cout << "\033[0;0f";}

void topLine(const char str[])
 
  {cout << "\033[0;0f" << "\033[0K" << str;}

void bottomLine (char * str)
 
  {cout << "\033[23;0Hf" << "\033[2K" << str;}

void hitAnyKey() {
   
   char ch;
   bottomLine ("Hit Enter to continue...");
   cin.get(ch);
   clearScreen();

}

void flushInput () {
   
   char buff[81];
   if (cin)
      cin.getline(buff,80);    

}

void Warning(char *message) {
 
   cerr << message;

}

void Error(char *message) {
 
   cerr << message;
   exit(1);

}

void EatWhiteSpace() {
 
    char ch;
    do {
      cin.get(ch);
    }
    while(isspace(ch));

    if(ch != EOF)
      cin.putback(ch);

}

bool promptYesNo(char * c) {
 
   char ch;
   cout << c << " [y|n]?";
   do {
      cin.get(ch);  
      tolower(ch);
      } while (ch != 'y' && ch != 'n');
   return (ch == 'y');

}

#ifndef DLIST_H
#define DLIST_H
#include <iostream>
#include <new>

template <class Entry_type>
class Node
{
 public:
    Node();
    Node(const Entry_type &);
    Entry_type entry;
    Node< Entry_type > *next;
    Node< Entry_type > *back;
};

template< class Entry_type >
Node< Entry_type >::Node()
{
  next = NULL;
  back = NULL;
}

template< class Entry_type >
Node< Entry_type >::Node( const Entry_type &usrEntry)
{
  next = NULL;
  back = NULL;
  entry = usrEntry;
}

template <class Entry_type>
class List {

 public:
   List();

/* needed to manage dynamic memory */
   List(const List &);
   ~List();
   void operator = (const List & copy);

/* standard general list operations */
   void clear();
   bool empty() const;
   bool full() const;
   int  size() const;
   void display() const;
   void display_rear() const;
   Entry_type retrieve(const int) const;
   void replace(const int, const Entry_type&);
   void insert(const int, const Entry_type&);
   void remove(const int);

private:
   Node< Entry_type > *head;
   Node< Entry_type > *rear;
   int count;
};

template< class Entry_type >
List< Entry_type >::List()
{
  head = NULL;
  rear = NULL;
  count = 0;
}

template< class Entry_type >
List< Entry_type >::List(const List & copy)
{
  Node< Entry_type > *currentPtr = copy.head;
  while ( (*currentPtr).next != NULL){
   insert(size()+1, (*currentPtr).entry);
   currentPtr = (*currentPtr).next;
  }
  insert(size()+1, (*currentPtr).entry);  
}

template< class Entry_type >
List< Entry_type >::~List()
{
  cout<<"Deleting list\n";
/*  if (!empty()){
    Node< Entry_type > *currentPtr = head;
//    Node< Entry_type > *temp;
    while (head != NULL){
      while ((*currentPtr).next != NULL )
      currentPtr = (*currentPtr).next;
      delete currentPtr;
      currentPtr = head;
    }
  }
*/
}

template< class Entry_type >
void List< Entry_type >::operator = (const List & copy)
{
  Node< Entry_type > *currentPtr = copy.head;
  while ( (*currentPtr).next != NULL){
   insert(size()+1, (*currentPtr).entry);
   currentPtr = (*currentPtr).next;
  }
  insert(size()+1, (*currentPtr).entry);  
}

template< class Entry_type >
void List< Entry_type >::clear()
{
  if (!empty()){
    Node< Entry_type > *currentPtr = head;
    while (head != NULL){
      while ((*currentPtr).next != NULL )
      currentPtr = (*currentPtr).next;
      delete currentPtr;
      currentPtr = head;
      delete head;
      head = NULL;
    }
  }
  count = 0;
}

template< class Entry_type >
bool List< Entry_type >::empty() const
{
  if (count == 0)
    return true;
  return false;
}

template< class Entry_type >
bool List< Entry_type >::full() const
{
  return false;
}

template< class Entry_type >
int List< Entry_type >::size() const
{
  return count;
}

template< class Entry_type >
void List< Entry_type >::display() const
{
  if (head == NULL)
    return;
  Node< Entry_type > *currentPtr = head;
  while ( (*currentPtr).next != NULL){
   cout<<(*currentPtr).entry;
   currentPtr = (*currentPtr).next;
  }
  cout<<(*currentPtr).entry;
  cout<<endl;
}

template< class Entry_type >
void List< Entry_type >::display_rear() const
{
  Node< Entry_type > *currentPtr = rear;
  while ( currentPtr != head){
   cout<<(*currentPtr).entry;
   currentPtr = (*currentPtr).back;
  }
  cout<<(*currentPtr).entry;
  cout<<endl;
}

template< class Entry_type >
Entry_type List< Entry_type >::retrieve(const int pos) const
{
  if (empty())
    throw "Underflow, cannot retrieve";
  if (pos > count)
    throw "Range Error, cannot retrieve";
  Node< Entry_type > *currentPtr = head;
  for (int i = 1; i < pos; i++)
    currentPtr = (*currentPtr).next;
  return (*currentPtr).entry;
}

template< class Entry_type >
void List< Entry_type >::replace(const int pos, const Entry_type &usrEntry)
{
  if (empty())
    throw "Underflow, cannot replace";
  if (pos > count)
    throw "Range Error, cannot replace";
  Node< Entry_type > *currentPtr = head;
  for (int i = 0; i < pos; i++)
    currentPtr = (*currentPtr).next;
  (*currentPtr).entry = usrEntry;
 
}

template< class Entry_type >
void List< Entry_type >::insert(const int pos, const Entry_type &usrEntry)
{
  if (full())
    throw "Overflow, cannot insert";
  if (pos > count+1)
    throw "Range Error, cannot insert";
  if (pos == 1)
    head = new Node< Entry_type>(usrEntry);

  else {
   Node< Entry_type > *currentPtr = head;
   Node< Entry_type > *newPtr = new Node< Entry_type >;
   for (int i = 1; i < pos-1; i++)
     currentPtr = (*currentPtr).next;
   (*newPtr).next = (*currentPtr).next;
   (*newPtr).entry = usrEntry;
   (*currentPtr).next = newPtr;
   (*newPtr).back = currentPtr;
   currentPtr = head;

   if ((*currentPtr).next != NULL){
    while ( (*(*currentPtr).next).next != NULL)
     currentPtr = (*currentPtr).next;
    rear = (*currentPtr).next;
   }
  }

 count++;
}

template< class Entry_type >
void List< Entry_type >::remove( const int pos)
{
  if (empty())
    throw "Underflow, cannot remove";
  if (pos > count)
    throw "Range Error, cannot insert";
  Node< Entry_type > *currentPtr = head;
  for (int i = 1; i < pos; i++)
    currentPtr = (*currentPtr).next;
  Node< Entry_type > *tempPtr = (*(*currentPtr).next).next;
  delete (*currentPtr).next;
  (*currentPtr).next = tempPtr;

  if ((*currentPtr).next != NULL){
   while ( (*(*currentPtr).next).next != NULL)
    currentPtr = (*currentPtr).next;
   rear = (*currentPtr).next;
  }
  count--;
}

#endif

/* Filename: main.cpp
   Project:  HW#5 Testing a dbly linked list */

#include <iostream>
#include "dlist.h"
#include "util.h"

void main()
{
   int data;
   //int i;
   List<int> the_list;
   the_list.insert(0,1);
   the_list.insert(1,2);
   the_list.insert(2,3);
   the_list.insert(3,4);
   the_list.insert(4,5);
   cout << "The List: \n";
   the_list.display();
   the_list.retrieve(data);
   cout << data << " retrieved at position 1" << endl;
   the_list.remove(0);
   the_list.remove(2);
   the_list.remove(4);
   the_list.remove(5);
   the_list.insert(2,2);
   the_list.insert(7,7);
   cout << "The_List after removing positions 0 2 5 and inserting 2,2: \n";
   the_list.display();
   
   List<int> new_list(the_list);
   new_list.insert(2,9);
   cout << "A copy of The_List after inserting 2,9: \n";
   new_list.display();

   cout << "A copy of The_List displayed in reverse:\n ";
   List<int> newer_list = the_list;
   newer_list.display_rear();
   cout << endl;
}

o.k. I made the changes to main and am still a little confused.

>>Regarding the core, you are not initializing the list properly. In your constructor you setting head to NULL and then you are trying to dereference that head in your insert function. The solution is to change your constructor of list so that head is allocated to some memory and then you assign values to it. Hope this solves your problem.

Here is my main with changes and new errors:

/* Filename: main.cpp
   Project:  HW#5 Testing a dbly linked list */

#include <iostream>
#include "dlist.h"
#include "util.h"

using namespace std;

int main() {
 
   int data;
   //int i;
   List<int> the_list;
   the_list.insert(0,1);
   the_list.insert(1,2);
   the_list.insert(2,3);
   the_list.insert(3,4);
   the_list.insert(4,5);
   cout << "The List: \n";
   the_list.display();
   //int data = 1;
   the_list.retrieve(data,1);
   cout << data << " retrieved at position 1" << endl;
   the_list.remove(0);
   the_list.remove(2);
   the_list.remove(4);
   the_list.remove(5);
   the_list.insert(2,2);
   the_list.insert(7,7);
   cout << "The_List after removing positions 0 2 5 and inserting 2,2: \n";
   the_list.display();
   
   List<int> new_list(the_list);
   new_list.insert(2,9);
   cout << "A copy of The_List after inserting 2,9: \n";
   new_list.display();

   cout << "A copy of The_List displayed in reverse:\n ";
   List<int> newer_list = the_list;
   newer_list.display_rear();
   cout << endl;
}

out:

[edeloss2@pegasus part1]$ make
cxx -c -L/usr/lib/cmplrs/cxx -DPOSIX_4D9  -g main.cpp
cxx: Error: main.cpp, line 23: too many arguments in function call
   the_list.retrieve(data,1);
--------------------------^
cxx: Warning: main.cpp, line 23: variable "data" is used before its value is set
   the_list.retrieve(data,1);
---------------------^
cxx: Info: 1 error detected in the compilation of "main.cpp".
make: *** [main.o] Error 1

I can't figure this one out...I am going to repost referencing this url.

o.k.  I am with you so far...I removed the extra const in the dlist.h and I am getting a core dump.

[edeloss2@pegasus part1]$ make veryclean
rm -f *.o
rm -f core
rm -f  main
[edeloss2@pegasus part1]$ make
cxx -c -L/usr/lib/cmplrs/cxx -DPOSIX_4D9  -g main.cpp
cxx -c -L/usr/lib/cmplrs/cxx -DPOSIX_4D9  -g util.cpp
cxx -L/usr/lib/cmplrs/cxx -DPOSIX_4D9  -g -lm -ltask main.o util.o -o main
[edeloss2@pegasus part1]$ main
Segmentation fault (core dumped)

what is meant by apprixmate space and time for each of the algorithms...is there a formula?...I am thinking that this is discrete mathematics which I have not taken yet.  How do you calculate????

o.k.  

but...what is causing the segmentation core dump?

>>Regarding the core, you are not initializing the list properly. In your constructor you setting head to NULL and then you are trying to dereference that head in your insert function. The solution is to change your constructor of list so that head is allocated to some memory and then you assign values to it. Hope this solves your problem.  pankaj tiwary  

I do not know how to do the suggested for the core dump...hence...fyi....I will be repeating cs classes.

Alex,

I am getting this error at line 86.

[edeloss2@pegasus part1]$ make
cxx -c -L/usr/lib/cmplrs/cxx -DPOSIX_4D9  -g main.cpp
cxx: Error: dlist.h, line 86: too many arguments in function call
          detected during instantiation of "List<Entry_type>::List(const
                    List<Entry_type> &) [with Entry_type=int]"
        append(count, currentPtr->entry);
----------------------^
cxx: Info: 1 error detected in the compilation of "main.cpp".
make: *** [main.o] Error 1

Alex, please check...there is something that I am still getting incorrect...

#ifndef DLIST_H
#define DLIST_H
#include <iostream>
#include <new>

template <class Entry_type>
class Node
{
 public:
    Node();
    Node(const Entry_type &);
    Entry_type entry;
    Node< Entry_type > *next;
    Node< Entry_type > *back;
};

template< class Entry_type >
Node< Entry_type >::Node()
{
  next = NULL;
  back = NULL;
}

template< class Entry_type >
Node< Entry_type >::Node( const Entry_type &usrEntry)
{
  next = NULL;
  back = NULL;
  entry = usrEntry;
}

template <class Entry_type>
class List {

 public:
   List();

/* needed to manage dynamic memory */
   List(const List &);
   ~List();
   void operator = (const List & copy);

/* standard general list operations */
   void clear();
   bool empty() const;
   // bool full() const;  makes no sense for linked lists
   int  size() const;
   void display() const;
   void display_rear() const;
   Entry_type retrieve(const int) const;
   void replace(const int, const Entry_type&);
   void insert(const int, const Entry_type&);
   void append(const Entry_type&);   // to insert at end
   void remove(const int);

private:
   Node< Entry_type > *head;
   Node< Entry_type > *rear;
   int count;
};

template< class Entry_type >
List< Entry_type >::List()
{
  head = NULL;
  rear = NULL;
  count = 0;
}

template< class Entry_type >
List< Entry_type >::List(const List & copy)
{
    head = NULL;
    rear = NULL;
    count = 0;
    Node< Entry_type > *currentPtr = copy.head;
    // insert all at end
    while (currentPtr != NULL)
    {
        append(count, currentPtr->entry);
        currentPtr = currentPtr->next;
    }
}

template< class Entry_type >
List< Entry_type >::~List()
{
  cout<<"Deleting list\n";
  clear();
}

template< class Entry_type >
void List< Entry_type >::operator = (const List & copy)
{
    Node< Entry_type > *currentPtr = copy.head;
    // insert all nodes of list 'copy' at end
    while ( currentPtr != NULL)
    {
        append(currentPtr->entry);
        currentPtr = currentPtr->next;
    }
   
}

template< class Entry_type >
void List< Entry_type >::clear()
{
   Node< Entry_type > *currentPtr = head;
   Node< Entry_type > *prevPtr    = head;
   // delete all nodes in a loop and save next pointer before delete
   while (currentPtr != NULL)
   {
       prevPtr    = currentPtr;
       currentPtr = currentPtr->next;
       delete prevPtr;
   }
   head  = rear = NULL;
   count = 0;
}

template< class Entry_type >
bool List< Entry_type >::empty() const
{
    return (count == 0);
}

template< class Entry_type >
int List< Entry_type >::size() const
{
   return count;
}

template< class Entry_type >
void List< Entry_type >::display() const
{
  Node< Entry_type > *currentPtr = head;
  while (currentPtr != NULL){
   cout<<currentPtr->entry << ' '; // add space character
   currentPtr = currentPtr->next;
  }
  cout<<endl;
}

template< class Entry_type >
void List< Entry_type >::display_rear() const
{
  Node< Entry_type > *currentPtr = rear;
  while ( currentPtr != NULL){
    cout<<currentPtr->entry << ' ';  // add space character
    currentPtr = currentPtr->back;  
  }
  cout<<endl;
}

template< class Entry_type >
Entry_type List< Entry_type >::retrieve(const int pos) const
{
    // that covers underflow as well
    if (pos >= count)
        throw "Range Error, cannot retrieve";
    Node< Entry_type > *currentPtr = head;
    for (int i = 0; i < pos; i++)
       currentPtr = currentPtr->next;
    return currentPtr->entry;
}

template< class Entry_type >
void List< Entry_type >::replace(const int pos, const Entry_type &usrEntry)
{
   if (pos > count)
     throw "Range Error, cannot replace";
  Node< Entry_type > *currentPtr = head;
  for (int i = 0; i < pos; i++)
    currentPtr = currentPtr->next;
  currentPtr->entry = usrEntry;
 
}

template< class Entry_type >
void List< Entry_type >::insert(const int pos, const Entry_type &usrEntry)
{
    if (pos > count)
        throw "Range Error, cannot insert";
    if (pos == 0 && count == 0)
    {
        head = new Node< Entry_type>(usrEntry);
        head->next = head->back = NULL;
        rear = head;
    }
    else {
        Node< Entry_type > *currentPtr = head;
        Node< Entry_type > *newPtr = new Node< Entry_type >;
        for (int i = 0; i < pos-1; i++)
            currentPtr = currentPtr->next;
        if (pos == 0)
        {
            head = newPtr;
            head->next = currentPtr;
            head->back = NULL;
            rear = head;
        }
        else
        {
           
            newPtr->next = currentPtr->next;
            newPtr->entry = usrEntry;
            currentPtr->next = newPtr;
            newPtr->back = currentPtr;

            if (pos == count)
                rear = newPtr;

        }
    }
   
    count++;
}

template< class Entry_type >
void List< Entry_type >::append(const Entry_type &usrEntry)
{
    insert(count, usrEntry);
}

template< class Entry_type >
void List< Entry_type >::remove( const int pos)
{
  if (empty())
    throw "Underflow, cannot remove";
  if (pos >= count)
    throw "Range Error, cannot insert";
  Node< Entry_type > *currentPtr = head;
  for (int i = 0; i < pos; i++)
    currentPtr = currentPtr->next;
  Node< Entry_type > *nextPtr = currentPtr->next;
  Node< Entry_type > *backPtr = currentPtr->back;
  delete currentPtr;
  if (pos == 0)
  {
      head = nextPtr;
      head->back = NULL;
  }
  else
  {
      backPtr->next = nextPtr;
      if (nextPtr != NULL)
          nextPtr->back = backPtr;

  }
  if (pos == count - 1)
      rear = backPtr;

  count--;
}

#endif

out:

[edeloss2@pegasus part1]$ make
cxx -c -L/usr/lib/cmplrs/cxx -DPOSIX_4D9  -g main.cpp
cxx: Error: dlist.h, line 86: too many arguments in function call
          detected during instantiation of "List<Entry_type>::List(const
                    List<Entry_type> &) [with Entry_type=int]"
        append(count, currentPtr->entry);
----------------------^
cxx: Info: 1 error detected in the compilation of "main.cpp".
make: *** [main.o] Error 1

Del, i would recommend you to check the differences between the current implementation and the version you posted above.

You'll see that the current version is much simpler, not using constructions like

  (*(*currentPtr).next).next

that requires at least a minimum of 2 nodes (or it crashes). Also, the while loops now check the pointers directly

   not:  while ((*currentPtr).next != NULL) ...  
   but:  while (currentPtr != NULL) ...

You also should try to make the number of cases as small as possible. Then, it's easier to check for remaining cases whether all variables are initialized and correctly set.

Regards, Alex

Thank you Alex.  Del