create functions of moving linked nodes

[s021623]

@keskiverto @seeplus

Reverse the list you mean?
All I can see is with --num which means it used a decrement, maybe is suitable for reverse the numbers in order?

[s021623]

@seeplus

I checked that my functions 4,5, 7 to 9 are correct, only function 1, 3 and 6 are incorrect, function 1 can ascend the numbers in order but not in reverse order, function 3 was also incorrect since when I type 3 on the input it always 2-2-2-2 instead of 2-1-0.

As for function 6 I got 3-0-1-2 instead of 0-1-2-3 which is incorrect, meanwhile function 7 does it correctly as it does changed to 3-0-1 when function 6 was 3-0-1-2

Can you figure out?
Just let function 2, 4 , 5, 7to 9 remain unchanged since they are 100 % correct as I checked it and tested these correct functions


Here is function 3 for printing the reverse the printing node

void Print_Doubly_linked_list_reversely(Doubly_linked_list* headPtr)
{
    int i = 0
    while (headPtr -> GetNext() != 0)
    {
           headPtr = headPtr ->GetNext();
           i++;
     }
     while (i >= 0)
     {
             cout << "[" << headPtr -> GetNum() "]->";
             headPtr = headPtr -> GetPrev();
             i--;
      }
      cout << "Head" << endl;
      cout << endl;
 }
}

Doubly_linked_list *Create_Doubly_linked_list(int n)  // Create a doubly linked list. The integer assigned in a node of the list is its sequence (i.e., 0 is assigned in the first node, 1 is assigned in the second node, and so on.). Remember to assign the previous and next pointers properly.
{
    Doubly_linked_list *tempPtr=0,*firstPtr=0,*lastPtr=0; 
    int i = 0;
    do 
    {
       tempPtr = new Doubly_linked_list; tempPtr->SetNum(i);
       if (i == 0)
       {
         firstPtr = tempPtr; 
         lastPtr = tempPtr; 
         i++;
       }
       else 
      {
         lastPtr->SetNext(tempPtr);
         lastPtr = tempPtr;
          tempPtr -> SetPrev(lastPtr); //used for reverse numbers order
         i++;
      }
      while (i < n);
      return firstPtr;
}

Doubly_linked_list* Insert_node_at_back(Doubly_linked_list* ptr, Doubly_linked_list* firstPtr) //Insert a node at the back of a list
{
    Doubly_linked_list *prevPtr = 0, *currPtr = 0;
    currPtr = firstPtr; 
    while (currPtr != 0) 
{
    prevPtr = currPtr;
    currPtr = currPtr->GetNext(); 
}
    prevPtr->SetNext(ptr); // prevPtr = lastPtr
    return firstPtr;
}

I have compiled them completely

[seeplus]

OK, now that you're got a compilable program, now is the time to be introduced to the joys of the debugger. Knowing the debugger well is as important to the programmer as knowing how to code.

Within the debugger you should trace through your code and watch the contents of the variables. When the observed behaviour doesn't match that expected from the design, then you're found a problem. Fix that. Then repeat until the program works as expected.

[keskiverto]

Reverse the list you mean?
All I can see is with --num which means it used a decrement, maybe is suitable for reverse the numbers in order?

No.

Lets "run" that (my) code in our brains. Iteration decrements num and then Insert_node_at_front.
Lets say num is 3 and list is empty.
First iteration inserts 2 at the front. List is now head->[2]
Second iteration inserts 1 at the front. List is now head->[1]->[2]
Third iteration inserts 0 at the front. List is now head->[0]->[1]->[2]
There are no more iterations.

That did not "reverse" the list. That did add nodes to the list. That did "create" a list.

[s021623]

@seeplus

Yeah but I feel like the reverse list was wrong even I use "start with debugging", that diagnostic tool wasnt that helpful other than showing ms and kbs

Is there any change I should do for function 3 and 1?

Perhaps you can try my code and find out

[keskiverto]

Doubly_linked_list* Insert_node_at_back(Doubly_linked_list* ptr, Doubly_linked_list* firstPtr)
{
    Doubly_linked_list *prevPtr = 0, *currPtr = 0;
    currPtr = firstPtr; 
    while (currPtr != 0)
    {
        prevPtr = currPtr;
        currPtr = currPtr->GetNext(); 
    }
    prevPtr->SetNext(ptr);
    return firstPtr;
}

Lets try with the list is head->[2], lets add 1:

firstPtr = head;
ptr->GetNum() == 1
currPtr = firstPtr; // == head
prevPtr = currPtr; // == head == [2]
currPtr = currPtr->GetNext();  // == head->GetNext() == [2]->GetNext() == nullptr
// iteration stops
prevPtr->SetNext(ptr); // == [2].SetNext(ptr), same as: [2].nextPtr = &[1] 

Ok, now head points to [2] and [2] points to [1], just like the intention was.

Where does the [1].prevPtr point to? What do you get with head->GetNext()->GetPrev()?
You should call ptr->SetPrev() with something.


You could also reuse the idea that you have in Print_Doubly_linked_list_reversely() to reach the last node.


[EDIT]
Lets try with empty list.
firstPtr == nullPtr
Therefore, the currPtr is nullptr, loop is skipped and prevPtr remains nullptr. Function does:

    prevPtr->SetNext(ptr); // ERROR: prevPtr does not point to object
    return firstPtr; // returns nullptr 

[s021623]

@seeplus @JLBorges

I found out that line 75 to 78 has a problem of reversing the nodes, still struggle how to fix it because it was still printing 2-2-2-2 instead of 3-2-1-0
Here is the full code with everything compiled so you can try it out

Also reminder that the class and int main were given so you cannot change the class and int main

Please I still need some help right now

#include<iostream>
using namespace std;
using std::cout; // used to prevent ambigious error cout 
using std::cin;

class Doubly_linked_list // Use a class Doubly_linked_list to represent an object 
{
public:
    // constructor initialize the nextPtr
    Doubly_linked_list()
    {
        prevPtr = 0; // point to null at the beginning
        nextPtr = 0; // point to null at the beginning
    }

    // get a number
    int GetNum()
    {
        return number;
    }

    // set a number
    void SetNum(int num)
    {
        number = num;
    }

    // get the prev pointer
    Doubly_linked_list* GetPrev()
    {
        return prevPtr;
    }

    // set the prev pointer
    void SetPrev(Doubly_linked_list* ptr) 
    {
        prevPtr = ptr;
    }

    // get the next pointer
    Doubly_linked_list* GetNext()
    {
        return nextPtr;
    }

    // set the next pointer
    void SetNext(Doubly_linked_list* ptr) 
    {
        nextPtr = ptr;
    }

private:
    int number;
    Doubly_linked_list* prevPtr;
    Doubly_linked_list* nextPtr;
};


Doubly_linked_list* Create_Doubly_linked_list(int n)
{
    Doubly_linked_list* tempPtr = 0, *firstPtr = 0, *lastPtr = 0; 
    int i = 0;
    do
    {
        tempPtr = new Doubly_linked_list;
        tempPtr->SetNum(i);
        if (i == 0)
        {
            firstPtr = tempPtr;
            lastPtr = tempPtr;
            i++;
        }
        else
        {
            lastPtr->SetNext(tempPtr);
            lastPtr = tempPtr;
            tempPtr->SetPrev(lastPtr);
            i++;
        }
    } while (i < n);
    return firstPtr;

}

void Print_Doubly_linked_list(Doubly_linked_list* headPtr)
{
    while (headPtr != 0)
    {
        cout << "[" << headPtr->GetNum() << "]->";
        headPtr = headPtr->GetNext();
    }
    cout << "Null" << endl;
    cout << endl;
}

void Print_Doubly_linked_list_reversely(Doubly_linked_list* headPtr)
{
    int i = 0;
    while (headPtr->GetNext() != 0)
    {
        headPtr = headPtr->GetNext();
        i++;
    }
    while (i >= 0)
    {
        cout << "[" << headPtr->GetNum() << "]->";
        headPtr = headPtr->GetPrev();
        i--;
    }
    cout << "Head" << endl;
    cout << endl;
}


Doubly_linked_list* Insert_node_at_front(Doubly_linked_list*ptr, Doubly_linked_list*headPtr)
{
    Doubly_linked_list* tempPtr = 0;
    tempPtr = headPtr;
    headPtr = ptr;
    ptr->SetNext(tempPtr);
    return ptr;
}

Doubly_linked_list* Remove_node_at_front(Doubly_linked_list*headPtr) 
{
    Doubly_linked_list* tempPtr = 0;

    tempPtr = headPtr;
    headPtr = headPtr->GetNext();
    delete tempPtr;
    return headPtr;
}

Doubly_linked_list *Insert_node_at_back(Doubly_linked_list* headPtr, Doubly_linked_list* newptr)
{
    Doubly_linked_list *prevPtr = 0, *currPtr = 0;

    currPtr = headPtr;
    while (currPtr != 0)
    {
        prevPtr = currPtr;
        currPtr = currPtr->GetNext();
    }
    prevPtr->SetNext(newptr);
    return headPtr;
}

Doubly_linked_list* Remove_node_at_back(Doubly_linked_list* headPtr) //remove a node from the back of a list
{
    Doubly_linked_list* prevPtr = 0, * currPtr = 0;
    currPtr = headPtr;
    while (currPtr->GetNext() != 0)
    {
        prevPtr = currPtr;
        currPtr = currPtr->GetNext();
    }
    prevPtr->SetNext(0);
    delete currPtr;
    return headPtr;
}

Doubly_linked_list* Insert_node(int n, Doubly_linked_list* ptr, Doubly_linked_list* headPtr) // Insert a node before the node with a given value in a list
{
    Doubly_linked_list* prevPtr = 0, *currPtr = 0;
    currPtr = headPtr;
    while (currPtr->GetNum() != n)
    {
        prevPtr = currPtr;
        currPtr = currPtr->GetNext();
    }
    prevPtr -> SetNext(ptr);
    ptr -> SetNext(currPtr);
    return headPtr;
}

Doubly_linked_list* Remove_node(int n, Doubly_linked_list* headPtr) // Remove a node with a give value in a list
{
    Doubly_linked_list* prevPtr = 0, * currPtr = 0;

    currPtr = headPtr;
    while (currPtr->GetNum() != n)
    {
        prevPtr = currPtr;
        currPtr = currPtr->GetNext();

    }
    prevPtr->SetNext(currPtr->GetNext());
    delete currPtr;
    return headPtr;
}






int main()
{
    
    int num;
    Doubly_linked_list* headPtr; 
    Doubly_linked_list* newPtr;

    cout << "How many items you want to create? ";
    cin >> num; 

    headPtr = Create_Doubly_linked_list(num);
    Print_Doubly_linked_list(headPtr);
    Print_Doubly_linked_list_reversely(headPtr);
    newPtr = new Doubly_linked_list;
    newPtr->SetNum(num);

    
    cout << "Insert a node at the front of the list:" << endl;
    headPtr = Insert_node_at_front(newPtr, headPtr);
    Print_Doubly_linked_list(headPtr);
    Print_Doubly_linked_list_reversely(headPtr);

    
    cout << "Remove a node from the front of the list:" << endl;
    headPtr = Remove_node_at_front(headPtr);
    Print_Doubly_linked_list(headPtr);
    Print_Doubly_linked_list_reversely(headPtr);
    newPtr = new Doubly_linked_list;
    newPtr->SetNum(num);

    
    cout << "Insert a node at the end of the list:" << endl;
    headPtr = Insert_node_at_back(newPtr, headPtr);
    Print_Doubly_linked_list(headPtr);
    Print_Doubly_linked_list_reversely(headPtr);

    
    cout << "Remove a node from the back of the list:" << endl;
    headPtr = Remove_node_at_back(headPtr);
    Print_Doubly_linked_list(headPtr);
    Print_Doubly_linked_list_reversely(headPtr);

    
    cout << "Enter the number of a new node: ";
    cin >> num; 
    newPtr = new Doubly_linked_list;
    newPtr->SetNum(num);

    
    cout << "Choose a number to add a node before the node with such value : ";
    cin >> num;


    cout << "Insert a node before the node with the value " << num << " in the list:" << endl;
    headPtr = Insert_node(num, newPtr, headPtr);
    Print_Doubly_linked_list(headPtr); Print_Doubly_linked_list_reversely(headPtr);

    
    cout << "Choose a number to delete a node with such value : ";
    cin >> num;
    cout << "Remove a node with value " << num << " from the list:" << endl;
    headPtr = Remove_node(num, headPtr);
    Print_Doubly_linked_list(headPtr);
    Print_Doubly_linked_list_reversely(headPtr);
    return 0;
    


}

[keskiverto]

First observation. Lines 75-77:

            lastPtr->SetNext(tempPtr);
            lastPtr = tempPtr;
            tempPtr->SetPrev(lastPtr);

Lets say that last node in list before these lines is X.
The new node that tempPtr points to is Y.

Line 75: Set X.nextPtr = tempPtr. The X.next is Y. Fine.
Line 76: Set lastPtr = tempPtr. The lastPtr now points to Y. Fine.
Line 77: Set Y.prevPtr = tempPtr. The Y.prev points to Y. Error. It should point to X.

How about:

            lastPtr->SetNext(tempPtr);
            tempPtr->SetPrev(lastPtr);
            lastPtr = tempPtr;

This was in list creation. Your code in other functions may be ok or flawed, but if you test with broken list, then you can't tell.

[s021623]

@keskiverto @seeplus @JLBorges

Strange, when I fix the reverse order, I got an error and the insert front node wont work on the reverse list and forced to quit when I start but it only printed successfuly for ascending and reversing numbers orfer when I fix the reverse number order in line 75 to 77.

However when I didnt fix the reverse order, it looks fine especially Insert_Node and Remove_Node function other than the wrong printed reverse numbers.

I have no clue how could this happen but it is confirmed that Print_Doubly_linked_list and Print_Doubly_linked_list_reversly were correct and exactly does the functions as I wanted

[seeplus]

As I believe I have mentioned before - when a program doesn't 'work' as expected, then first use the debugger to debug your code against the design. Trace through the code and watch the variables. Once you find where the execution varies from the design/expected, then you have found an issue. Fix that issue. Then repeat until the program works as expected. Knowing how to use the debugger is a skill that all programs need to acquire - IMO sooner rather than later.

[dhayden]

I agree that your print functions work. So if they aren't printing the right thing, that means the list it self is messed up. Print_Doubly_linked_list() doesn't work, then the next pointers are wrong. If Print_Doubly_linked_list_reversely() doesn't work, then the prev pointers are wrong.

To quote from my post a month ago:

You never call SetPrev()! Review your code. Everywhere you call SetNext(), you probably need to make a corresponding call to SetPrev(). Also, for the list functions, you need to handle the case where the input list is empty.

[seeplus]

and if you haven't already done so, draw some diagrams showing the nodes, the links and the data and where various pointers are pointing. Then manually work through the code altering the diagram as per the code. When the diagram becomes not as expected, then you're found a code problem. This is the basic method I used when I was learning things like this back when at University. When I deal with pointers I still often draw diagrams - it really does help.

[dhayden]

Your Insert_at_back() declares the parameters in the wrong order. It should be
Doubly_linked_list *Insert_node_at_back(Doubly_linked_list* newptr, Doubly_linked_list* headPtr)

and not
Doubly_linked_list *Insert_node_at_back(Doubly_linked_list* headPtr, Doubly_linked_list*newptr)

By the way, you can reuse lots of code if you make this a circular linked list. This doesn't require changing the class at all. It just means that the last node points forward to the first node, and the first node points backward to the last one. So the "next" pointers for a cycle going in one direction and the "prev" pointers cycle in the other.

When it's coded as circular list, Insert_node_at_back() can be done by calling Insert_node_at_front!:

Doubly_linked_list *Insert_node_at_back(Doubly_linked_list* newPtr, Doubly_linked_list* headPtr)
{
    Insert_node_at_front(newPtr, headPtr);
    return newPtr->GetNext();
}

Draw this out on paper if you don't understand it. Note that I return newPtr->GetNext() intead of returning headPtr because of the special case where you're inserting into an empty list.