create functions of moving linked nodes

1
2

Doubly_linked_list *headPtr;
Print_Doubly_linked_list( headPtr );

What can you tell about function Print_Doubly_linked_list based on how you use it?
What parameter(s) does it take? What value does it return?

How would you print the numbers of a list?

@keskiverto

The google doc link has the output if you want to know about how does the numbers print it
https://docs.google.com/document/d/183YzOMouAQ42DgeS7J5x0x3zNc9OfQ6mlAfrTcq1HoU/edit

Last edited on

Right now I have to create the nine functions for the Int main to test the doubly linked nodes

OK. So what are your issues about doing these? What don't you understand? What are your C++ issues? What have you coded so far. We've not going to write these for you...

@seeplus
Oh you want the functions? Sorry for that as I almost forgot to put those functions that I am working on into the first page. Here are the functions that I am working for but couldnt figure out to implement the print nodes for the output especially the classes and the inputs.

I dont know how to print out the nodes on the output with the functions of Print_Doubly_linked_list(headPtr) and Print_Doubly_linked_list_reversely(headPtr) for printing the numbers in reverse order

Remove_node(num, headPtr) // Remove a node with a give value in a list
{
    Doubly_linked_list *prevPtr = 0, *currPtr = 0;
    currPtr = firstPtr; 
    while(currPtr->GetNum() != n) 
{
prevPtr = currPtr;
currPtr = currPtr->GetNext(); 
    
}
prevPtr->SetNext(currPtr->GetNext()); 
delete currPtr;
return firstPtr;
}



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

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

Insert_node_at_back(newPtr, headPtr) //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;
}

Remove_node_at_front(headPtr) // Remove a node from the front of a lis
{
    Doubly_linked_list *tempPtr = 0;
    tempPtr = firstPtr;
    firstPtr = firstPtr->GetNext(); 
    delete tempPtr;
    return firstPtr;
}

Insert_node_at_front(newPtr, headPtr) // Insert a node at the front of a list
{
    Doubly_linked_list *tempPtr = 0;
    tempPtr = firstPtr; 
    ptr firstPtr = ptr;
    ptr->SetNext(tempPtr);
    return ptr;
}

Last edited on

MikeyBoy (5631)

1. You would help yourself - and us - enormously by adopting a sensible indentation style. That way, you will be able to more easily see the flow of control through your code, and spot any errors.

2. Look at lines 1, 18, 31, 45, 58, 67. That's not the syntax for defining a function! Compare them with the function definitions in the code you posted in your OP.

Well you're attempted nos. 4) - 9) - not withstanding MikeyBoy's comments above - that code doesn't compile! But surely 1) would have been the first to be attempted - followed by 2) to display the list to check that 1) is working!

So before you start printing you need to first create the list. When coding, first design. Then code in small parts and get each part to compile OK and test OK before further coding. Don't just code the (nearly) whole program and then try to compile/debug.

As you're got the code for insert/delete, you should be able to code the list creation.

Last edited on

@seeplus
I still dont understand why does this cant even compile in which lines, I did follow these nodes actions which are similar but I think they arent able to compile, I will check it

Last edited on

As MikeyBoy stated above, the function definition statements are not correct. A return type is required and the type of the function parameters need to be specified.

Also just looking at Remove_node, what is firstPtr ??

dhayden (5798)

Do this one bit at a time. To begin, comment out lines 10-35 of the test program and get what's left working (i.e., create a list with one item and print it forwards and backwards).

When this works, move on to the next bit of code.

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

I figure it out how to do 1 and 3 but I dont know how to do no 2 of the function which requires to print the nodes in reverse.

I think no 4 to 9 functions concept wise they are correct of moving the nodes

Also it seems that it couldnt compile successfully and I feel like function no1 is kinda wrong since it looks like for singly linked list more than doubly linked list

Keep in mind do not modify the int main and the class since they are completely correct, ensure that the nine functions will run successfully


void Print_Doubly_linked_list(Doubly_linked_list *ptr) // Print a list.
{
   while (ptr != 0) 
  {
       cout << "[" << ptr->GetNum() << "]->";
       ptr = ptr->GetNext(); 
  }
  cout << "Null" << 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;
         i++;
      }
      while (i < n);
      return firstPtr;
}

Last edited on

function no1 is kinda wrong since it looks like for singly linked list more than doubly linked list

Correct. For a doubly linked list you also need to set the node prevPtr. You should be able to 'walk' the list from firstPtr forwards using nextPtr and from lastPtr backwards using prevPtr.

Walking the list 'backwards' is how you print the nodes in reverse.

@seeplus

Also what do you mean by set the node prevPtr in which line?

As for print the nodes reverse, is this correct

Print_Doubly_linked_list_reversely(Doubly_linked_list *ptr)
{
   while (ptr != 0) 
  {
       cout << "[" << ptr->GetNum() << "]->";
       ptr = ptr->GetPrev(); 
  }
  cout << "Head" << endl;
  cout << endl; 
}

Last edited on

Have you tried it? Your print shows number from given node and the proceeds to the next node and repeats.

Given {1, 3, 4, 8} and calling print() with node of 3 you will get:

[3]->[4]->[8]->Head

The reverse would surely be:

[3]->[1]->Head

Would it?

On double linked list each node has two links: to previous node and to next node. You need to set both correctly.

Have you had class constructors yet? It would be convenient to refactor/encapsulate all initialization of member variables into constructor.

Last edited on

Normally when you use doubly linked lists, you maintain a pointer to both the head and tail of the list. You also maintain forwards and backwards pointers in each node.

However, in this case in main(), you only have a pointer to the list head (headPtr).

Hence to print in reverse, you need to iterate the list forwards from headPtr using GetNext() until you reach the last node (like you would for forward display). Once you find the last node, then iterate backwards to the first node using GetPrev()

@seeplus

So if I have to reverse it, then I have to make it back to headPtr?

No. You don't reverse it. You iterate from the end (tail) of the list to the beginning (head) using GetPrev(). To get the tail you have to iterate from the head using Getnext() as you aren't saving a pointer to the tail and only have a pointer to the head.

In practice, this isn't how you would code a doubly-linked list - but I understand that you can't change what's been given.

You have class

class Something
{
public:
    // interface functions

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

Conceptually, that does look like a node. A list has (zero or more) nodes.

A single node is in practice a list when, and only when that list has exactly one node.
However, it could be easier to think "node" and "list" as different entities.

Operations on a list do something with the nodes.
Your "list" is a pointer and some standalone functions.
While standalone functions are fine, a list could be a class that has a pointer and some member functions too.

@keskiverto

Oh but this task wont allow me to modify the int main and the class since both were given in the task, which means I have to work on the member functions.

The only thing I think it was completely wrong were Print_Doubly_linked_list_reversely and Doubly_linked_list *Create_Doubly_linked_list

Last edited on