doubly-linked list [was: Please Help me right now]

[ttdung]

Help me please!
I have a double linked list.
I want to reverse my list type double linked list.
please help me :confused:

[ttdung]

i have a double linked list.
I want to reverse my list, which is type double linked list.
please help me :WAVE:

[mr1yh1]

i wrote this for a "single linked list".
http://forum.ceviz.net/showthread.php?t=21605&page=2

this was the method which reverse list:
void reverse(){
Node *before = first ;
Node *current = first ->next ;
Node *further = current->next ;
before -> next = NULL ;
for ( ;further ; before=current ,
current=further , further= further-> next )
current->next = before ; // this does job

current->next = before ; // last element
current = first ;// change first and last
first = last ;// becos list reversed
last = current ;// current used as a temp node
}
};

[nspils]

You have a double linked list. I'd guess you have a pointer to the "head" of the list, and a pointer to the "tail".

So, to create a new list which is the reverse of your existing list, read from tail going forward to head, copying as you go to the new list. Make sure to change over your "forward" and "backward" links.

[ttdung]

Thank you very much!
I owe you a debt of gratitude.
Have a good time!
:WAVE:

[ttdung]

i wrote this for a "single linked list".
http://forum.ceviz.net/showthread.php?t=21605&page=2

this was the method which reverse list:
void reverse(){
Node *before = first ;
Node *current = first ->next ;
Node *further = current->next ;
before -> next = NULL ;
for ( ;further ; before=current ,
current=further , further= further-> next )
current->next = before ; // this does job

current->next = before ; // last element
current = first ;// change first and last
first = last ;// becos list reversed
last = current ;// current used as a temp node
}
};

i'm sorry. I don't understand this code (red color). Could you interpret for me.
thank you very much!

[jonnin]

for ( ;further ; before=current ,
current=further , further= further-> next )
current->next = before ; // this does job

for loops are of the form :
for(initial condition, compare, do this every time)
{
body;
}

a more normal example is
for(x = 0; x < 10; x++)
{
cout << x << endl;
}

which sets x to zero, loops until x = 10, adds 1 to x each time, and prints 0-9.

so back to it:

for (none)
so long as further is true (not = to zero in C++)
each time set before to current, current to further, further to next)

{
body of current->next is further
}

this is moderately poorly written code. There is NO good reason to stuff all that into the back end of the loop, but C allows it because its a nice, flexible language.


The same thing as a readable while loop would be

while (further != NULL)
{
current->next = before;
before=current;
current=further;
further= further-> next;
}

[ttdung]

I want to reverse my list type double linked list
This is my source code:
It's easy for every body:

void CDoubleLinkedList::ReverseList()
{
CNode *Temp1=m_pHead;
CNode *Temp2=m_pTail;
CNode *Temp3=NULL;
m_pHead=m_pTail=NULL;
for (int i=0;i<m_Size-1;i++)
{
Temp3=Temp1;
Temp1=Temp1->m_pNext;
Temp1->m_pPrev=NULL;
if (m_pHead==NULL)
{
m_pHead=new CNode(Temp3->m_Element,NULL,NULL);
m_pTail=m_pHead;
}
else
{
m_pHead = new CNode(Temp3->m_Element, m_pHead, NULL);
m_pHead->m_pNext->m_pPrev=m_pHead;
if (m_pHead->m_pNext->m_pNext != NULL)
m_pHead->m_pNext->m_pNext->m_pPrev = m_pHead->m_pNext;
if (m_pHead==m_pTail)
m_pTail=m_pHead->m_pNext;
}
delete Temp3;
Temp3=NULL;
}
m_pHead = new CNode(Temp2->m_Element, m_pHead, NULL);
m_pHead->m_pNext->m_pPrev=m_pHead;
if (m_pHead->m_pNext->m_pNext != NULL)
m_pHead->m_pNext->m_pNext->m_pPrev = m_pHead->m_pNext;
if (m_pHead==m_pTail)
m_pTail=m_pHead->m_pNext;
}

[mr1yh1]

@ttdung
believe me is not so easy ,
its a question from a professional interview,
this programmer shared it in that forum and we studied.
so study on it :
i needed 3 referance, walking and changing the list at the same time,
they move together and represents "successive nodes" in list.
if you use only 1 pointer and iterate it, you will fail...
i used before -> current -> further ..
its iterated as an "one step job" , at the right place iterations done..
not an objective critic " i wouldnt prefere to code in that style so its poorly written"

i modified my program for you,
its now a "very simple" double linked list..
reverse2() and show2() methods added..
reverse2() walk on the list in opposite direction, and do same as reverse() does , so second link( before ) reversed.
show2() does same as show() does in opposite direction.

becareful , this code is only showing a way to do it ,
it didnt written for double linked list originaly ,
it may be wrong or may need modifications

#include <iostream>
using namespace std;
class Node{
public:
Node *next;
Node *before; // added for double liked list
int data;
Node( int _data ) { before=NULL;next=NULL ; data=_data;};
};

class List{
Node *first ;
Node *last ;
public:
List(Node* _first) { first = _first; last = first ; }
~List () {
while ( first ) {
Node *temp = first->next;
delete first;
first = temp;
}
}

void add(Node* node) { last->next = node;
node->before = last ;// addded for double linked list
last = node; }

Node* begin() { return first ; };

void show (){
cout<<"\n walk on next....\n";
for( Node* i = begin(); i; i=i->next )
cout << i->data << "-" ;
show2();////!!!!!!
}
/////////////// added for double linked list
void show2 (){
cout<<"\n walk on before....\n";
for( Node* i = last; i; i=i->before )
cout << i->data << "-" ;
}

void reverse(){
Node *before = first ;
Node *current = first ->next ;
Node *further = current->next ;
before -> next = NULL ;
for ( ;further ; before=current ,
current=further , further= further-> next ){
current->next = before ;
}
current->next = before ;
current = first;
first = last ;
last = current ;
reverse2(); ///!!!!!!

};
////////////// addded for double linked list
void reverse2(){
Node *before = first ;
Node *current = first ->before ;
Node *further = current->before ;
before -> before = NULL ;
for ( ;further ; before=current ,
current=further , further= further->before ){
current->before = before ;
}
current->before = before ;
}
};

int main(){
List l ( new Node(1) );
for ( int i = 2 ; i <= 10 ; i++ )
l.add( new Node (i) );

cout<<"\n before reverse :";
l.show(); cout<<endl<<endl;

l.reverse();
cout<<"\n after reverse :\n";
l.show(); cout<<endl<<endl;

}

[ttdung]

mr1yh1
thank you very much! :D
have a good time