So I am trying to debug my code to reverse a double-linked list. It runs correctly, but for some reason, when I try to assign the front -> next = front -> prev. It gives to next to NULL, which occurs because NULL is behind the first element of the linked list. I am trying to figure out a way to overcome this issue.
void List::reverse(Node *front) //front == head
{
cout << "Head: " << front << endl;
if(front == NULL)
{
cout << "Head is NULL" << endl;
return;
}
Node *temp = front->next;
cout << "Node *temp = front -> next: " << temp << endl;
front -> next = front -> prev;
cout << "front -> next = front -> prev: " << front->next << endl;
front -> prev = temp;
cout << "front -> prev = temp: " << front->prev << endl;
cout << "-------" << endl;
if(front->prev == NULL)
{
cout << "front->prev: " << front ->prev << endl;
cout << "ITS BEEN REVERSED" << endl;
return;
}
reverse(front->prev);
}
The error is front -> next = front -> prev
The List I'm using for an example is
["Hello", "Human", "test", "Boo"]
With the code above, this is what outputs within the console as I was debugging this.
Reverse Test Below:
--------------
Before Reversed: [Hello, Human, test, Boo]
Head: 0x55a98ae172c0
Node *temp = front -> next: 0x55a98ae17300
front -> next = front -> prev: 0
front -> prev = temp: 0x55a98ae17300
-------
Head: 0x55a98ae17300
Node *temp = front -> next: 0x55a98ae17340
front -> next = front -> prev: 0
front -> prev = temp: 0x55a98ae17340
-------
Head: 0x55a98ae17340
Node *temp = front -> next: 0x55a98ae17380
front -> next = front -> prev: 0
front -> prev = temp: 0x55a98ae17380
-------
Head: 0x55a98ae17380
Node *temp = front -> next: 0
front -> next = front -> prev: 0
front -> prev = temp: 0
-------
front->prev: 0
ITS BEEN REVERSED
---
After Reversed: [Hello]
--------------
I think everything else is pretty okay; I just dont know how to change the
front -> next = front -> prev
CodePudding user response:
It would help you understand what is going on if you draw out the state of your list on each step.
Your list looks like this upon entry to the initial call to reverse()
:
----------- ----------- ---------- ---------
| "Hello" [n] -> | "Human" [n] -> | "test" [n] -> | "Boo" [n] -> NULL
NULL <- [p] | <- [p] | <- [p] | <- [p] |
----------- ----------- ---------- ---------
^
head
front
front
is not NULL, so you swapfront->next
andfront-prev
, and now the list looks like this:
----------- ----------- ---------- ---------
| "Hello" [n] -> NULL | "Human" [n] -> | "test" [n] -> | "Boo" [n] -> NULL
- [p] | <------- [p] | <- [p] | <- [p] |
| ----------- ----------- ---------- ---------
| ^ ^
| head |
| front |
-------------------------
front->prev
is not NULL, so you execute reverse(front->prev)
.
front
is not NULL, so you swapfront->next
andfront-prev
, and now the list looks like this:
-------------------------------------
| |
\/ |
----------- ----------- | ---------- ---------
| "Hello" [n] -> NULL | "Human" [n] - | "test" [n] -> | "Boo" [n] -> NULL
- [p] | - [p] | <-- [p] | <- [p] |
| ----------- | ----------- ---------- ---------
| ^ | ^ ^ ^
| head | | front |
| --|-----------------
-------------------------
front->prev
is not NULL, so you execute reverse(front->prev)
.
front
is not NULL, so you swapfront->next
andfront-prev
, and now the list looks like this:
-------------------------------------
| -------------|----------------
\/ \/ | |
----------- ----------- | ---------- | ---------
| "Hello" [n] -> NULL | "Human" [n] - | "test" [n] - | "Boo" [n] -> NULL
- [p] | - [p] | - [p] | <-- [p] |
| ----------- | ----------- | ---------- ---------
| ^ | ^ | ^ ^ ^
| head | | | | front |
| --|--------------|-- |
------------------------- -------------------
front->prev
is not NULL, so you execute reverse(front->prev)
.
front
is not NULL, so you swapfront->next
andfront-prev
, and now the list looks like this:
------------------------------------- ----------------------------------
| --------------|--|------------- |
\/ \/ | \/ | |
----------- ----------- | ---------- | --------- |
| "Hello" [n] -> NULL | "Human" [n] - | "test" [n] - | "Boo" [n] -
- [p] | - [p] | - [p] | NULL <- [p] |
| ----------- | ----------- | ---------- ---------
| ^ | ^ | ^ ^ ^
| head | | | | | front
| --|--------------|-- |
------------------------- ------------------------
And finally, front->prev
is NULL, so you exit.
The above is a little messy, so let's re-draw it cleaner with the new arrows:
--------- ---------- ----------- -----------
| "Boo" [n] -> | "test" [n] -> | "Human" [n] -> | "Hello" [n] -> NULL
NULL <- [p] | <- [p] | <- [p] | <- [p] |
--------- ---------- ----------- -----------
^
head
Look, the nodes were reversed correctly!
However, notice anything wrong? When you try to printout the new list, you only see Hello
, because that is where head
is still pointing! You need to update head
to point at Boo
instead:
--------- ---------- ----------- -----------
| "Boo" [n] -> | "test" [n] -> | "Human" [n] -> | "Hello" [n] -> NULL
NULL <- [p] | <- [p] | <- [p] | <- [p] |
--------- ---------- ----------- -----------
^
head
If your List
class is maintaining both head
and tail
pointers, you can simply swap them:
void List::reverse(Node *front)
{
...
}
void List::reverse()
{
reverse(head);
Node *temp = head;
tail = head;
head = temp;
}
But, if you don't have a tail
pointer, then you will need to make reverse()
return the new head
pointer after its work is finished, eg:
Node* List::reverse(Node *front)
{
...
if(front == NULL)
{
...
return NULL;
}
...
if(front->prev == NULL)
{
...
return front;
}
return reverse(front->prev);
}
void List::reverse()
{
head = reverse(head);
}