Help with Linked Lists with digits

[DeadDrunk]

Ok, heres what I got so far. The problem I have is my loops for adding data are not adding what I'm expecting... Each node is like "00343068", etc. when it's suppose to be like 123

Also if anyone has any ideas on the sum and increment portion, it would be greatfull.

Header

class number
{
    public:
        number();    // constructor
        ~number();   // deconstructor
        // member functions
        void insert(int newValue);
        void Increment();
        void Copy(const number& Num);
        void Sum(int Num);
        void DisplayNumber();
        bool isEmpty() const;
        int getLength() const;
    private:
        struct digit
        {
            int Value;    // a digit value, 0-9
            struct digit* next;
        };
        typedef digit* ptrType;
        int size;
        digit *head;
        digit *find(int index) const;
};

Class Declaration

#include <iostream>
#include <cstddef>
#include <new>
#include "number.h"

using namespace std;


number::number() : size(0), head(NULL)
{
}
number::~number()
{
    while (!isEmpty())
        remove(NULL);
}
bool number::isEmpty() const
{
    return size == 0;
}
int number::getLength() const
{
    return size;
}
void number::DisplayNumber()
{
    digit *temp;
    temp = head;
    if (isEmpty() == 1){}
    else
    {
        while (temp!=NULL)
        {
            cout << temp << endl;
            temp = temp->next;
        }
    }

}
void number::insert(int newValue)
{
    int newLength = getLength() + 1;
    digit *newPtr = new digit;
    if (newPtr==NULL)
    { 
    cout << "Not enough memory!" << endl;
    }
    else
    {
    size = newLength;
    newPtr->Value = newValue;
    newPtr->next = head;
    head = newPtr;
    }
}
void number::Increment() // Increase a # by one. adding 1 to 1999, for example, requires changing all four digits to get 2000, and adding 1 to 9 requires making a new digit to get 10.
{

}
void number::Copy(const number& Num) // Copy one number to another
{
        head = new digit;
        head->Value = Num.head->Value;
        
        digit *newPtr = head;
        for (digit *origPtr = Num.head->next;
            origPtr != NULL;
            origPtr = origPtr->next)
        {
            newPtr = newPtr->next;
            newPtr->Value = origPtr->Value;
        }
        newPtr->next = NULL;
}
void number::Sum(int Num) // A method that takes two numbers and sums them.  Sample usage: N.Sum(M); (adds M to N).  Don't forget about a carry when the sum of two digits is greater than 10.
{
}

and Main

#include <iostream>
#include <string>
#include <cmath>
#include "number.h"

using namespace std;

int main()
{
    // Number M
    number M;
    for(int i=0; i<3; i++)
        M.insert(i);
    // Number N
    number N;
    for(int i=0; i<3; i++)
    N.insert(i);
    // End Number Creation
    M.DisplayNumber();
    N.DisplayNumber();
    M.Copy(N);
    M.DisplayNumber();
    N.DisplayNumber();
    return 0;
}

[Narue]

>Each node is like "00343068", etc. when it's suppose to be like 123
Those are addresses. You're printing the value of the node itself rather than the Value member:

cout << temp->Value << endl;

[DeadDrunk]

Thanks Narue that helps loads...

Now it appears that my copy function doesn't work... heres what I got.

void number::Copy(const number& Num) // Copy one number to another
{
        head = new digit;
        head->Value = Num.head->Value;
        
        digit *newPtr = head;
        for (digit *origPtr = Num.head->next;
            origPtr != NULL;
            origPtr = origPtr->next)
        {
            newPtr = newPtr->next;
            newPtr->Value = origPtr->Value;
        }
        newPtr->next = NULL;
}

Heres what I input
M = 4321
N = 1234
the I do M.Copy(N); and get :
M= 14
N = 1234

[Narue]

>head = new digit;
Why are you creating a new list? It strikes me that you want to use the existing nodes and just copy the data. I can also see other cases where the list being copied is shorter or longer than the destination list. As it is, you'll have intermittent memory issues because it looks like you're walking all over memory you don't own.

[DeadDrunk]

Ok, I got the copy all sorted out.. thanks again.

Now, with my sum fuction (adding number 1 with number 2) I see theres an issue.. since the direction it goes in the list. How would I start from the back and move to the front?

Number 1 is 1555
number 2 is 1555
when there sumed it puts out 12011 because of the progression, instead of 3110

void number::Sum(const number& Num) // A method that takes two numbers and sums them.  Sample usage: N.Sum(M); (adds M to N).  Don't forget about a carry when the sum of two digits is greater than 10.
{
        digit *temp = head;
        digit *temp2 = Num.head;
        int mod = 0;
        if (isEmpty() == 1){}
        else
        {
            while (temp!=NULL)
            {
                if (temp->Value + temp2->Value + mod <= 9)
                {
                temp->Value = temp->Value + temp2->Value + mod;
                cout << temp->Value << endl;
                temp = temp->next;
                temp2 = temp2->next;
                mod = 0;
                }
                else
                {
                temp->Value = temp->Value + temp2->Value + mod - 10;
                cout << temp->Value << endl;
                temp = temp->next;
                temp2 = temp2->next;
                mod = 1;
                }
            }
            if (temp==NULL && mod ==1)
                insert(mod);
            }    
}

Also, heres the updated copy node code for anybody's reference

void number::Copy(const number& Num) // Copy one number to another
{
        digit *temp = head;
        digit *temp2 = Num.head;
        if (isEmpty() == 1){}
        else
        {
            while (temp!=NULL)
            {
                temp->Value = temp2->Value;
                temp = temp->next;
                temp2 = temp2->next;
            }
        }
}

[Narue]

>How would I start from the back and move to the front?
You have two choices, really. You can use recursion to fake it, or add another link to each node that points to the previous node. Since you build your list in reverse anyway, you can just walk it forward and the sum can just fall out of that. But then you have the issue of printing, which is the same problem. :) However, a double linked list can be tricky because you have to manage twice the pointers:

#include <iostream>

namespace JSW {
  struct node {
    int data_;
    node *prev_;
    node *next_;
  };

  node *add_front ( node *list, int data )
  {
    node *nn = new node;

    nn->data_ = data;

    // nn is the new head
    nn->prev_ = 0;
    nn->next_ = list;

    // Be sure to set the back link
    if ( list != 0 )
      list->prev_ = nn;
    
    return nn;
  }
}

int main()
{
  using namespace std;

  JSW::node *list = 0;
  JSW::node *last;

  // Build the list in reverse
  for ( int i = 0; i < 10; i++ )
    list = JSW::add_front ( list, i );

  cout<<"Forward traversal:\n";

  while ( list != 0 ) {
    cout<< list->data_;

    // Only print a link if one exists :-)
    if ( list->next_ != 0 )
      cout<<"->";

    // Save the last valid node since 'list' will become null
    last = list;
    list = list->next_;
  }

  cout<<"\nBackward traversal:\n";

  // Do the same thing in reverse using 'last'
  while ( last != 0 ) {
    cout<< last->data_;

    if ( last->prev_ != 0 )
      cout<<"->";

    last = last->prev_;
  }

  cout<<'\n';
}

[DeadDrunk]

Ok, I cannot get this to display backwards.

If anyone can help me figure out where I'm messing up

Here's my Insert code

void number::insert(int newValue)
{
    int newLength = getLength() + 1;
    digit *newPtr = new digit;
    if (newPtr==NULL)
    { 
    cout << "Not enough memory!" << endl;
    }
    else
    {
    size = newLength;
    newPtr->Value = newValue;
    newPtr->prev = 0;
    newPtr->next = head;
    head = newPtr;
    if (head!=NULL)
        head->prev = newPtr;    
    } 
}

and my display function

void number::DisplayNumber()
{
    digit *temp;
    digit *temp2;
    temp = head;
    temp2 = head;
    if (isEmpty() == 1){}
    else
    {
        cout << "\nFoward\n";
        while (temp!=NULL)
        {
            temp2 = temp;            
            cout << temp->Value;
            temp = temp->next;
            temp2 = temp2->prev;
        }
        //temp2 = head;
        cout << "\nBackwards\n";
        while (temp2!=NULL)
        {
            cout << temp2->Value;
            temp2 = temp2->prev;
        }
    }
}

[Narue]

>head = newPtr;
>if (head!=NULL)
> head->prev = newPtr;
The order for that is wrong. Look at it this way. This is what you want before setting head to newPtr:

0<-newPtr<->head<->...

But because you set head to newPtr before fixing head->prev, you get this:

0<-newPtr->head<->...

Notice the missing back link between newPtr and head. So the code should update the current head first, then set the new head:

if ( head != NULL )
  head->prev = newPtr;
head = newPtr;

>temp = temp->next;
>temp2 = temp2->prev;
You don't need the second statement. What you want is for temp2 to point to the node prior to temp. So along the line you know the current node and the last node that was looked at:

t   c
   |   |
~<-0<->1<->2<->3->~

       t   c
       |   |
~<-0<->1<->2<->3->~

           t   c
           |   |
~<-0<->1<->2<->3->~

               t  c
               |  |
~<-0<->1<->2<->3->~

The last one is important, and why the temporary pointer was used in the first place. When the current node is null, it has no link to the previous node, so you have to either save the previous node, or avoid getting to the null node in the first place. To save the previous node, you follow this logic:

c = head;

while ( c != NULL ) {
  /* Print c->Value */
  t = c; /* Save the current node */
  c = c->next; /* Go to the next node, now c is current and t is previous */
}

/* Now t points to the last node and you can walk back */
while ( t != NULL ) {
  /* Print t->Value */
  t = t->prev;
}

To avoid getting to the null node, you use this logic:

c = head;

/* Make sure the list isn't empty */
if ( c != NULL ) {
  /* All loop control is inside the body */
  for ( ; ; ) {
    /* Print c->Value */

    /* Terminate early at the last node */
    if ( c->next == NULL )
      break;

    c = c->next;
  }

  /* Now c points to the last node and you can walk back */
  while ( c != NULL ) {
    /* Print c->Value */
    c = c->prev;
  }
}

[DeadDrunk]

Cool thanks again Narue. Now I'm about 90% done... heres the next issue I'm having ( been beating my head all night)

When adding and the it has to add another number to the list (IE have 9999 and you add one it becomes 10000) I can't seem to figure out how to get the new 1 added in the right place... Here's my updated code. If I do head->prev is errors...

Heres one of the fuctions where I'm needing to add a new node

void number::Sum(const number& Num) // A method that takes two numbers and sums them.  Sample usage: N.Sum(M); (adds M to N).  Don't forget about a carry when the sum of two digits is greater than 10.
{
        digit *temp = head;
        digit *temp2 = Num.head;
        int mod = 0;
        if (isEmpty() == 1){}
        else
        {
            while (temp!=NULL)
            {
                if (temp->Value + temp2->Value + mod <= 9)
                {
                temp->Value = temp->Value + temp2->Value + mod;
                temp = temp->next;
                temp2 = temp2->next;
                mod = 0;
                }
                else
                {
                temp->Value = temp->Value + temp2->Value + mod - 10;
                temp = temp->next;
                temp2 = temp2->next;
                mod = 1;
                }
            }
            if (temp==NULL && mod ==1)
            {
                temp=head;
                temp = temp->next;
                int newLength = getLength() + 1;
                digit *newPtr = new digit;
                if (newPtr==NULL)
                {
                    cout << "Not enough memory!" << endl;
                }
                else
                {
                    size = newLength;
                    newPtr->Value = mod;
                    newPtr->prev = head;
                    newPtr->next = temp;
                    if (head!=NULL)
                        head->next = newPtr;
                    temp->prev = newPtr;
                }
            }
        }
}

HEADER

class number
{
    public:
        number();    // constructor
        ~number();   // deconstructor
        // member functions
        void insert(int newValue);
        void Increment();
        void IncrementB();
        void Copy(const number& Num);
        void Sum(const number& Num);
        void DisplayNumberF();
        void DisplayNumberB();
        bool isEmpty() const;
        int getLength() const;
    private:
        struct digit
        {
            int Value;    // a digit value, 0-9
            struct digit* next;
            struct digit* prev;
        };
        typedef digit* ptrType;
        int size;
        digit *head;
        digit *tail;
        digit *find(int index) const;
};

CLASS

#include <iostream>
#include <cstddef>
#include <new>
#include "number.h"

using namespace std;


number::number() : size(0), head(NULL)
{
}
number::~number()
{
    while (!isEmpty())
        remove(NULL);
}
bool number::isEmpty() const
{
    return size == 0;
}
int number::getLength() const
{
    return size;
}
void number::DisplayNumberF()
{
    digit *temp;
    digit *temp2;
    temp = head;
    temp2 = head;
    if (isEmpty() == 1){}
    else
    {
        while (temp!=NULL)
        {
            temp2 = temp;            
            cout << temp->Value;
            temp = temp->next;
        }            
        while (temp2!=NULL)
        {
            temp2 = temp2->prev;
        }        
    }
}
void number::DisplayNumberB()
{
    digit *temp;
    digit *temp2;
    temp = head;
    temp2 = head;
    if (isEmpty() == 1){}
    else
    {
        while (temp!=NULL)
        {
            temp2 = temp;
            temp = temp->next;
        }
        while (temp2!=NULL)
        {
            cout << temp2->Value;
            temp2 = temp2->prev;
        }
    }
}
void number::insert(int newValue)
{
    
    int newLength = getLength() + 1;
    digit *newPtr = new digit;
    if (newPtr==NULL)
    { 
    cout << "Not enough memory!" << endl;
    }
    else
    {
    size = newLength;
    newPtr->Value = newValue;
    newPtr->prev = 0;
    newPtr->next = head;
    if (head!=NULL)
        head->prev = newPtr;    
    head = newPtr;
    }
}
void number::Increment() // Increase a # by one. adding 1 to 1999, for example, requires changing all four digits to get 2000, and adding 1 to 9 requires making a new digit to get 10.
{
        digit *temp = head;
        int hold = 0;
        int mod = 0;
        if (isEmpty() == 1){}
        else
        {
            int checker = temp->Value + 1;
            if (checker <= 9)
            {
                temp->Value = temp->Value + 1;
            }
            else
            {
                mod = 1;
                while (mod!=0 && temp!=NULL)
                {
                    if (temp->Value + mod > 9)
                    {
                    hold = temp->Value + mod;
                    temp->Value = hold - 10;
                    temp = temp->next;
                    mod = 1;
                    }
                    else
                    {
                        temp->Value = temp->Value + mod;
                        mod = 0;
                    }

                }

            if (temp==NULL && mod ==1)
            {
                temp=head;
                temp = temp->next;
                int newLength = getLength() + 1;
                digit *newPtr = new digit;
                if (newPtr==NULL)
                {
                    cout << "Not enough memory!" << endl;
                }
                else
                {
                    size = newLength;
                    newPtr->Value = mod;
                    newPtr->prev = head;
                    newPtr->next = temp;
                    if (head!=NULL)
                        head->next = newPtr;
                    temp->prev = newPtr;
                }
            }
            }
        }
}
void number::IncrementB() // Increase a # by one. adding 1 to 1999, for example, requires changing all four digits to get 2000, and adding 1 to 9 requires making a new digit to get 10.
{
        digit *temp = head;
        int mod = 1;
        if (isEmpty() == 1){}
        else
        {
            while (temp!=NULL)
            {
                if (temp->Value + mod <= 9)
                {
                temp->Value = temp->Value + mod;
                temp = temp->next;
                mod = 0;
                }
                else
                {
                temp->Value = temp->Value + mod - 10;
                temp = temp->next;
                mod = 1;
                }
            }
            if (temp==NULL && mod ==1)
            {
                temp=head;
                temp = temp->next;
                int newLength = getLength() + 1;
                digit *newPtr = new digit;
                if (newPtr==NULL)
                {
                    cout << "Not enough memory!" << endl;
                }
                else
                {
                    size = newLength;
                    newPtr->Value = mod;
                    newPtr->prev = head;
                    newPtr->next = temp;
                    if (head!=NULL)
                        head->next = newPtr;
                    temp->prev = newPtr;
                }
            }
        }
}

void number::Copy(const number& Num) // Copy one number to another
{
        int LengthOfNode = getLength();
        int LengthOfCopyNode = Num.getLength();
        while (LengthOfNode < LengthOfCopyNode)
        {
            insert(1);
            LengthOfNode = LengthOfNode + 1;
        }
        digit *temp = head;
        digit *temp2 = Num.head;
        
        if (isEmpty() == 1){}
        else
        {
            while (temp2!=NULL)
            {
                temp->Value = temp2->Value;
                temp = temp->next;
                temp2 = temp2->next;
            }
            while (temp != NULL)
            {
                temp->prev->next = temp->next;
                temp = temp->next;
            }
        }
        
        
}

void number::Sum(const number& Num) // A method that takes two numbers and sums them.  Sample usage: N.Sum(M); (adds M to N).  Don't forget about a carry when the sum of two digits is greater than 10.
{
        digit *temp = head;
        digit *temp2 = Num.head;
        int mod = 0;
        if (isEmpty() == 1){}
        else
        {
            while (temp!=NULL)
            {
                if (temp->Value + temp2->Value + mod <= 9)
                {
                temp->Value = temp->Value + temp2->Value + mod;
                temp = temp->next;
                temp2 = temp2->next;
                mod = 0;
                }
                else
                {
                temp->Value = temp->Value + temp2->Value + mod - 10;
                temp = temp->next;
                temp2 = temp2->next;
                mod = 1;
                }
            }
            if (temp==NULL && mod ==1)
            {
                temp=head;
                temp = temp->next;
                int newLength = getLength() + 1;
                digit *newPtr = new digit;
                if (newPtr==NULL)
                {
                    cout << "Not enough memory!" << endl;
                }
                else
                {
                    size = newLength;
                    newPtr->Value = mod;
                    newPtr->prev = head;
                    newPtr->next = temp;
                    if (head!=NULL)
                        head->next = newPtr;
                    temp->prev = newPtr;
                }
            }
        }
}

MAIN

#include <iostream>
#include <string>
#include <cmath>
#include "number.h"

using namespace std;

void main()
{
    // Number S
    number S;
    S.insert(9);
    S.insert(9);
    S.insert(9);
    S.insert(9);
    // Number M
    number M;
    M.insert(5);
    M.insert(5);
    M.insert(5);
    M.insert(5);
    //Number N
    number N;
    N.insert(9);
    N.insert(8);
    N.insert(7);
    // End Number Creation
    
    cout << "S : ";            //
    S.DisplayNumberB();        //
    cout << endl << endl;    //
    cout << "N : ";            //
    N.DisplayNumberB();        //    Display
    cout << endl << endl;    //    Numbers
    cout << "M : ";            //
    M.DisplayNumberB();        //
    cout << endl << endl;    //

    S.Sum(M);

    cout << "S : ";            //
    S.DisplayNumberB();        //
    cout << endl << endl;    //
    cout << "N : ";            //
    N.DisplayNumberB();        //    Display
    cout << endl << endl;    //    Numbers
    cout << "M : ";            //
    M.DisplayNumberB();        //
    cout << endl << endl;    //
    
}

[Narue]

I'll answer your question with a question. When you add a new digit onto the front of the list, why doesn't it become the new head? My usual recommendation when working with list logic is to get a handful of change and play with it on your desk. Then match the code to the shuffles you do with the change.